algorithm - 在不构建树的情况下预测霍夫曼压缩比

Question

我有一个二进制文件，我知道其中每个符号出现的次数。如果我要使用霍夫曼算法压缩它，我需要预测压缩文件的长度。我只对假设的输出长度感兴趣，对单个符号的代码不感兴趣，因此构建哈夫曼树似乎是多余的。
作为一个例子，我需要得到类似
“包含 4 个 a、5 个 b 和 10 个 c 的 38 位二进制字符串可以压缩到 28 位。”，除了文件和字母表的大小都很大更大。

基本问题是:不建树能行吗？

查看贪心算法:http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
这棵树似乎可以在 n*log(n) 时间内构建，其中 n 是文件中不同符号的数量。这渐近地不错，但需要为树节点分配内存，并且做了很多工作，在我的例子中这些工作是浪费的。

Answer 1

压缩文件中每个符号平均位数的下限不过是所有符号的熵 H = -sum(p(x)*log(p(x))) x 输入。 P(x) = freq(x)/(文件大小)。使用此 compressed length(lower bound) = filesize*H。这是文件压缩大小的下限。但不幸的是，在大多数情况下无法实现最佳熵，因为位是整数而不是分数，因此在实际情况下，需要构建霍夫曼树以获得正确的压缩大小。但最佳压缩大小可用于获得可能的压缩量的上限，并决定是否使用哈夫曼。