DEFLATE和固定Huffman编码

Question

我正在尝试实现一个压缩器并且需要决定是否使用静态哈夫曼编码或者创建动态哈夫曼编码。

静态编码长度与什么有关？

（RFC中包含的表格如下） Lit Value Bits --------- ---- 0 - 143 8 144 - 255 9 256 - 279 7 280 - 287 8

我认为静态编码更偏向于纯ASCII文本，但它好像更倾向于RLE长度的压缩。

选择何时使用静态编码的好的启发式方法是什么？

我想从一组输入数据的样本中构建概率分布并计算与从静态编码派生的概率的距离（也许是EMD？）。

- dvd

Answer 1

我想，代码的创作者可能从压缩数据中取了大量的文字和长度样本，可能包括可执行文件和文本，并在大数据集上找到典型的代码长度。 然后使用所示表格进行近似。 然而，作者已经去世多年，因此我们永远无法确定。

您不需要启发式算法。 一旦您完成了查找匹配字符串的工作，计算动态和静态表示块中的比特数就会变得非常快。 然后只需选择较小的一个。 如果相等，则选择静态的（解码速度更快）。

- Mark Adler

---

那个作者是谁？是Phil Katz吗？ - mwfearnley

正确。菲尔·卡茨。 - Mark Adler

Answer 2

关于选择静态代码长度，我不清楚其合理性，但在其中存在少量的非理性。

在您提供的表中，最大的静态代码编号为287，但是DEFLATE规范只允许使用285以下的代码，这意味着有无效的代码长度被分配给了两个代码。（而且甚至不是最长的代码！）同样，在距离代码的表格中，有32个代码已经被分配了长度，但只有30个是有效的。

因此，可以进行一些简单的改进。但是，如果没有关于数据的先前知识，通常不可能产生更加高效的内容。表格的“平坦度”（没有超过9位的代码）将最坏情况的性能降低到每字节无法解压缩数据增加1个额外位。

我认为对于分组背后的主要原理是通过保持组大小为8的倍数，可以通过查看5个最高有效位来确定代码属于哪个组，这也告诉您其长度以及立即添加的值，以获得代码值本身。

00000 00   .. 00101 11     7 bits  + 256   -> (256..279)
00110 000  .. 10111 111    8 bits  -  48   -> (  0..144)
11000 000  .. 11000 111    8 bits  +  78   -> (280..287)
11001 0000 .. 11111 1111   9 bits  - 256   -> (144..255)

理论上，你可以设置一个包含32个条目的查找表来快速读取代码，但这是一个不常见的情况，可能不值得进行优化。

实际上只有两种情况（有些重叠），其中固定哈夫曼块可能最有效：

• 当输入字节数非常小的时候，静态哈夫曼比未压缩更高效，因为未压缩使用32位头，而固定哈夫曼只需7位页脚，再加上每字节1位潜在开销。

• 当输出大小很小时（即数据较小且易于压缩），静态哈夫曼比动态哈夫曼更高效——因为动态哈夫曼会使用额外的空间来存储头信息。（实际最小头部大小难以计算，但我认为至少需要64位，可能更多。）

尽管如此，从开发者角度来看，我发现它们实际上是有用的，因为可以轻松地使用静态哈夫曼块来实现与Deflate兼容的函数，并从那里迭代改进以获得更高效的算法。

- mwfearnley