c# - 如何使用霍夫曼编码查找文件的压缩比

Question

我使用Huffman 编码 压缩了一个二进制文件。现在我试图找到压缩效率。

在我的二进制文件中，我有符号(一串 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 个我不知道为什么？)

压缩后我得到了这样的编码

symbol : 0 Code : 1
symbol : 1 Code : 00
symbol : 2 Code : 011
symbol : 3 Code : 010

有人能告诉我如何使用这些信息得到这个二进制文件的霍夫曼压缩效率吗？ (我尝试在谷歌上搜索，但没有二进制文件的样本，它们有一些浮点类型的频率，我无法理解如何将它们与我的二进制文件相关联)。非常感谢。执行此操作的算法 (c/c++/c#) 也很受欢迎。

Answer 1

给定你的符号表:

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 得到字节数，然后四舍五入。这将告诉您编码数据有多少字节。

您还必须存储 Huffman 表，在本例中您可以用 8 个字节来存储。实际上，9 个字节，因为您必须存储大小。存储霍夫曼树的一般情况稍微复杂一些。