我有一个二进制文件，我知道其中每个符号出现的次数。如果我要使用霍夫曼算法压缩它，我需要预测压缩文件的长度。我只对假设的输出长度感兴趣，而不是对单个符号的代码感兴趣，因此构建霍夫曼树似乎是多余的。
作为一个例子，我需要得到类似
“包含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 是文件中不同符号的数量。这渐进地不错，但需要为树节点分配内存，并且做了很多工作，在我的例子中这些工作都被浪费了。
最佳答案
压缩文件中每个符号的平均位数的下限只不过是所有符号的熵H = -sum(p(x)*log(p(x)))输入中的 x。 P(x) = freq(x)/(文件大小)。使用此压缩长度(下限)= 文件大小*H。这是文件压缩大小的下限。但不幸的是，在大多数情况下无法实现最佳熵，因为位是整数而不是分数，因此在实际情况下需要构造哈夫曼树以获得正确的压缩大小。但最佳压缩大小可用于获得可能的压缩量上限，并决定是否使用霍夫曼。
关于algorithm - 无需构建树即可预测霍夫曼压缩率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24172313/