动态霍夫曼：位打包清晰度

Question

我只是想知道是否有动态霍夫曼位打包的好例子。我不太了解 RFC 材料中有关位打包的内容。我在 Stack Overflow 上找到了很多静态霍夫曼的很好的例子，但是动态的例子似乎很缺乏。

在 RFC 1951 第 3.1.1 节中

             * Data elements are packed into bytes in order of
               increasing bit number within the byte, i.e., starting
               with the least-significant bit of the byte.
             * Data elements other than Huffman codes are packed
               starting with the least-significant bit of the data
               element.
             * Huffman codes are packed starting with the most-
               significant bit of the code.

我对

Huffman Codes

和

Data Elements other than Huffman Codes.

之间数据打包的逆转感到困惑，

Huffman Codes

和

Data Elements other than Huffman Codes

的构成是什么。

codelengths, hlit, hclen, hdist, actual compressed data

属于哪一组？谢谢。

Answer 1

这只是我对https://www.rfc-editor.org/rfc/rfc1951的解释。 按照我的理解，第一个要点描述了位缓冲区输出；位缓冲区清空到位流中的方式。第二和第三位处理缓冲区输入。

示例：5 位数据元素 11110 后跟 4 位霍夫曼码 0001

存储在位缓冲区中： 01111 0001

存储在反向位缓冲区中（这更有意义）： 1000 11110

打包成字节： 00011110xxxxxxx1

编辑：如果这是不清楚的部分，“霍夫曼代码”在计算机科学中具有特殊含义，指的是/可以从树中读取的实际代码。任何其他名为霍夫曼的东西，比如“霍夫曼代码长度”都是元数据，而不是代码。

显然，这种打包位顺序是为了使用逻辑和移位操作进行最简单的解码。元数据采用正确的位顺序进行消费。霍夫曼编码是相反的。这样，解码就可以在构成代码的所有位都进入位缓冲区之前开始。

Answer 2

压缩数据中的文字/长度和距离代码以及动态头中的代码长度代码都是霍夫曼代码并且被反转（代码的最高有效位进入当前正在组装的字节的最低有效未使用位，因此在）。这三个都是 deflate 格式的霍夫曼代码。格式中的其他所有内容，包括其中一些代码后面的额外位，都按其自然顺序打包（最低有效位进入下一个最低有效未使用位）。

Answer 3

如果有帮助： https://github.com/leok7v/sqz/blob/main/huffman.h （非常幼稚的实现）