string - 霍夫曼编码

Question

霍夫曼编码在什么条件下使字符串不可压缩？是不是所有字符都以相同的频率/概率出现？如果是这样，怎么能证明这是真的呢？

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的快速测试给出了每个符号约 5 位的熵，文本的 Huffman 编码也是如此。霍夫曼（或算术或范围）编码需要与输入数据的高阶模型结合使用。这些模型可以是简单的字符串匹配，例如在 deflate 或 LZMA 中使用的 LZ77、Burrows-Wheeler 变换或通过部分匹配进行预测。LZ77 压缩器，在本例中为 gzip，每个符号获得的位少于 3 位。

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

Answer 2

In a nutshell, Huffman encoding assigns smaller bit-length codes to more probable binary combinations and longer ones to the less probable ones. If all are equally likely, you will find there is no real advantage because the compression due to shorter codes is lost due to equally likely longer codes.

Answer 3

我想到了两个因素：

• 如果你有相似的元素概率，那么压缩将是可能的
• 如果您尝试压缩一个小的输入（例如，一个短文本），那么附加 Huffman 查找表（也称为字典 - 您需要解码压缩文件，不是吗？）的开销可以使最终大小甚至比原始输入还要大。