霍夫曼编码

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

霍夫曼代码每个符号将具有与该熵相等或更多的比特.您还需要考虑如何将霍夫曼代码传达给接收器.您将需要某种描述代码的标头,这将占用更多位.算术或范围代码可以比霍夫曼代码更接近熵,特别是对于非常长的序列.

通常,霍夫曼代码本身不会产生非常令人满意的压缩.对100M字符英文文本测试文件enwik8的快速测试给出了每符号约5位的熵,以及文本的霍夫曼编码.霍夫曼(或算术或范围)编码需要与输入数据的高阶模型结合使用.这些模型可以是简单的字符串匹配,如用于deflate或LZMA的LZ77,Burrows-Wheeler变换或部分匹配预测.LZ77压缩器,在这种情况下为gzip,每符号少于3位.

我无法抗拒地包括一张玻尔兹曼墓碑的图片,其上刻有将熵与概率联系起来的公式,基本上就是上面的公式.

Answer 2

简而言之,霍夫曼编码将较小的比特长度代码分配给更可能的二进制组合,将较长的代码分配给不太可能的二进制组合.如果所有这些都具有相同的可能性,您将发现没有真正的优势,因为由于更短的代码导致的压缩由于同样可能更长的代码而丢失.

Answer 3

我想到了两个因素:

• 如果你有相似的元素概率,那么很少有压缩
• 如果你试图压缩一个小输入(比如一个短文本),那么附加一个Huffman查找表(也就是字典 - 你需要解码你的压缩文件,不是吗？)的开销就可以达到最终的大小比原来的输入还要大.