我有一个二进制文件，我知道其中每个符号出现的次数。如果我要使用霍夫曼算法压缩它，我需要预测压缩文件的长度。我只对假设的输出长度感兴趣，而不对单个符号的代码感兴趣，因此构建霍夫曼树似乎是多余的。
作为一个例子，我需要得到类似的东西
“包含 4 个 a、5 个 b 和 10 个 c 的 38 位二进制字符串可以压缩到 28 位。”，但文件和字母表大小都大得多。
基本问题是：是否可以在不构建树的情况下完成？
看看贪心算法：http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
看来树可以在 n*log(n) 时间内构建，其中 n 是文件中不同符号的数量。这渐进地不错，但需要为树节点分配内存，并且做了很多工作，在我的例子中这些工作都被浪费了。
压缩文件中每个符号的平均位数的下限只不过是熵H = -sum(p(x)*log(p(x)))对于输入中的所有符号 x。P(x) = freq(x)/(filesize)。使用这个compressed length(lower bound) = filesize*H。这是文件压缩大小的下限。但不幸的是，在大多数情况下无法实现最佳熵，因为位是整数而不是分数，因此在实际情况下需要构造哈夫曼树以获得正确的压缩大小。但最佳压缩大小可用于获得可能的压缩量的上限，并决定是否使用霍夫曼。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
