如何使用霍夫曼编码找到文件的压缩比
本文关键字:文件 压缩比 何使用 霍夫曼 编码 | 更新日期: 2023-09-27 17:57:21
我用Huffman encoding
压缩了一个binary file
。现在我正在尝试找到compression efficiency
.
在我的二进制文件中,我有符号(一堆0和1)和频率(符号的重复)。假设我有:
symbol :0 freq : 173
symbol :1 freq : 50
symbol :2 freq : 48
symbol :3 freq : 45
文件大小为 (173+50+48+45)*8= 2528
(如果我计算大小的方式是正确的?如果我错了,请纠正我。(在调试时我得到 2536)(还有8个我不知道为什么?
压缩后我像这样encoding
symbol : 0 Code : 1
symbol : 1 Code : 00
symbol : 2 Code : 011
symbol : 3 Code : 010
有人可以告诉我如何使用这些信息获得这个二进制文件的霍夫曼压缩效率吗?(我尝试在谷歌上搜索,但没有二进制文件样本,它们具有一定的浮点类型频率,我无法理解如何将它们与我的二进制文件联系起来)。非常感谢.算法(c/c ++/c#)来做到这一点也值得赞赏。
给定您的符号表:
symbol : 0 Code : 1
symbol : 1 Code : 00
symbol : 2 Code : 011
symbol : 3 Code : 010
您的字节计数:
symbol :0 freq : 173
symbol :1 freq : 50
symbol :2 freq : 48
symbol :3 freq : 45
然后,将每个符号的出现次数乘以该符号的位数。例如,符号 0 需要 1 位进行编码,因此位数为 173。你有:
(1 * 173) + (2 * 50) + (3 * 48) + (3 * 45)
该计数以位为单位。除以 8 得到字节数,然后四舍五入。这将告诉您编码数据的字节数。
您还必须存储霍夫曼表,在这种情况下,您可以使用 8 个字节来存储。实际上,9字节,因为您必须存储大小。存储霍夫曼树的一般情况更为复杂。
有了霍夫曼表后,您可以通过将每个符号的位编码长度乘以该符号的频率来计算压缩图像的大小(以位为单位)。
最重要的是,您需要添加霍夫曼树本身的大小,这当然需要解压缩。
因此,例如,压缩长度将是
173 * 1 + 50 *2 + 48 * 3 + 45 * 3 = 173 + 100 + 144 + 135 = 552 位 ~= 70 字节。
表格的大小取决于您的表示方式。
2 * 50) + (3 * 48) + (3 * 45))/(173+50+48+45) = 1.746 位熵率 = Plog2P 的总和 = 1.439 位