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) 时的答案，以查看不相等的概率可以为您带来多少 yield 。您还可以将结果与例如 8 进行比较，如果您当前将每个符号存储为一个字节(在这种情况下 n <= 256)。

霍夫曼码每个符号的比特数将等于或多于该熵。您还需要考虑如何将霍夫曼码传送给接收器。您将需要某种描述代码的 header ，这将占用更多位。算术或范围代码可以比霍夫曼代码更接近熵，尤其是对于非常长的序列。

一般来说，霍夫曼代码本身不会产生非常令人满意的压缩。 100M字符英文文本测试文件快速测试enwik8给出每个符号大约 5 位的熵，文本的霍夫曼编码也是如此。霍夫曼(或算术或范围)编码需要与输入数据的高阶模型结合使用。这些模型可以是简单的字符串匹配，如 deflate 或 LZMA 中使用的 LZ77、Burrows-Wheeler 变换或通过部分匹配进行预测。 LZ77 压缩器，在本例中为 gzip，每个符号少于 3 位。

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