霍夫曼编码

Question

在什么情况下，哈夫曼编码会使字符串无法压缩？是当所有字符的出现频率/概率相等时吗？如果是这样，怎样才能证明这是正确的？

- DillPixel

Answer 1

你可以计算一组符号的简单零阶熵，这将告诉你是否有可能只使用霍夫曼编码进行有效压缩。 (我希望stackoverflow拥有像math.stackexchange.com一样的TeX格式化功能。我无法在此处编写像样的方程式。)

计算出你所拥有的不同符号数，称之为n，其中符号编号为1..n。计算每个符号的概率，即每个符号出现的次数除以序列的长度，并称其为p（k）。然后，使用零阶编码的最佳平均比特数为：-sum(p(k)log(p(k)),k=1..n)/log(2)。然后，你可以将结果与log(n)/log(2)进行比较，如果所有概率相等（1/n），则答案将是多少。你也可以将结果与例如8进行比较，如果你当前将符号存储为每个字节（在这种情况下n <= 256）。

一个霍夫曼编码的比特数等于或多于熵值。您还需要考虑如何将霍夫曼编码传达给接收方。您需要一些描述编码的头部，这将需要更多的位数。算术编码或范围编码可以比霍夫曼编码更接近熵值，特别是对于非常长的序列。

通常情况下，仅使用霍夫曼编码无法产生非常令人满意的压缩效果。在对100M字符英文文本测试文件enwik8进行快速测试后，熵约为每个符号五位比特，对文本进行霍夫曼编码也是如此。霍夫曼（或算术或范围）编码需要与输入数据的高阶模型结合使用。这些模型可以是简单的字符串匹配，例如在deflate或LZMA中使用的LZ77，Burrows-Wheeler变换或预测通过部分匹配。在这种情况下，LZ77压缩器（gzip）每个符号不到三位比特。

我忍不住要包含一张玻尔兹曼墓碑的图片，上面刻着他的公式，将熵与概率联系起来，基本上就是上面的公式。

- Mark Adler

Answer 2

简而言之，哈夫曼编码将更有可能出现的二进制组合赋予较小的位数编码，而将不太可能出现的组合赋予较长的编码。如果所有组合的概率相等，则没有实际优势，因为由于同样概率的长编码，短编码所带来的压缩效果会被抵消。

- Anirudh Ramanathan

Answer 3

我能想到的有两个因素：

• 如果元素有相似的概率，那么很难进行压缩
• 如果你试图压缩小输入（比如短文本），那么附加Huffman查找表（即字典——你需要解码压缩文件，对吧？）的开销可能会使最终大小甚至比原始输入还要大。

- emesx