Question

利用哈夫曼编码进行压缩压缩率一般达到多少？

自己编程用利用哈夫曼树对文件进行压缩的时候，压缩率只有80%~90%（而且不包括字典大小）。请问利用哈夫曼编码进行文件压缩的压缩率都是这么高吗？还是我的编程出错呢？
另外同样的文件（文件为2094KB的dat文件、426KB的ppt）我用winrar压缩压缩率却分别为29%、40%，是不是现在压缩软件用的压缩算法比利用哈夫曼编码的算法更加有效呢？

Answer 1

哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。

例如：用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 

2.61/3=0.87=87% 

其平均码长是等长码的87%，所以平均压缩率为13%。 

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

压缩率，描述压缩文件的效果名，是文件压缩后的大小与压缩前的大小之比，例如：把100m的文件压缩后是90m，压缩率为90/100*100%=90%，压缩率一般是越小越好，但是压得越小，解压时间越长。

扩展资料

哈夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。

参考资料来源：百度百科-哈夫曼编码

参考资料来源：百度百科-压缩率

Answer 2

哈夫曼编码压缩率很低的
举个例子：用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：
4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61
2.61/3=0.87=87%
其平均码长是等长码的87%。
所以平均压缩率为13%。
所以应该是你算法有问题……

追问

用n位二进行数进行的等长编码平均长度为n，则根据哈夫曼树编码的最短编码平均长度最小是1，故压缩率最小为1/n。所以上述压缩率最小应该为33.33333……%。
另外压缩率不是应该是压缩后的文件大小除以原文件大小吗（也就是说压缩率数值越小压缩得越好）？你算出来的压缩率不是应该为87%吗（也就是说和我算的80%~90%差不多）？

追答

哈夫曼树编码的最短编码平均长度最少是1,但是上面那个例子的平均码长就是2.61啊，若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的平均码长为：从根结点到该结点之间的路径长度与该结点的权的乘积的和呀

Answer 3

我一开始也有一样的问题，后来发现哈夫曼编码是认为文件各字符是独立同分布的，不考虑其相关性，而通常对文件压缩时其前后是有很强的关联性的，所以可以达到更低的压缩率，更高的压缩比

Answer 4

哈夫曼算法是最好的无损算法，无损。