如何从 DEFLATE 重建动态哈夫曼树

Question

这个问题是关于RFC-1951的第 3.2.7 节，重建动态霍夫曼树。

每个代码由代码长度序列定义，使得给定位长度的所有代码都具有字典顺序连续的值。

例如，这里是一个 rgb(255,0,0) 50x50 png，其中 IDAT 是来自 DEFLATE 的动态哈夫曼树。

0000024: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx  CIDATx
000002a: xxxxxxxx 11101101 11001111 00110001 00010001 00000000  ...1..
0000030: 00000000 00001000 00000000 10100001 11101111 01011111  ....._
0000036: 01011010 00110011 10111000 01111010 00001100 00000100  Z3.z..
000003c: 10100000 10101001 11111001 00100000 00010001 00010001  ... ..
0000042: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000048: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000004e: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000054: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000005a: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000060: 00010001 00010001 00010001 00010001 00010001 10010001  ......
0000066: 10001011 00000101 10110000 00110011 01110101 10010110  ...3u.
000006c: 01111001 11000101 00011100 10110001 00000000 00000000  y.....
0000072: 00000000 00000000 01001001 01000101 01001110 01000100  ..

infgen生成此标头：

last
dynamic
litlen 0 2
litlen 255 4
litlen 256 4
litlen 274 4
litlen 283 4
litlen 285 1
dist 3 1
dist 15 1

...目标是了解重建动态树的位和过程...

---

前三位描述 DEFLATE 标头。

101 <- last block bit, tree type is dynamic. 

接下来的十四位描述 HLIT、HDIST 和 HCLEN。

11101 <- HLIT,  29 + 257 = 286 
01111 <- HDIST, 15 + 1 = 16
1110 <- HCLEAN, 14 + 4 = 18

这些值描述了动态霍夫曼树的什么？

---

接下来，一次读取三位并遵循排列表......发现长度是......

Lengths: [4, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2]（puff.c第 697 行）

这些长度是否用于定义文字？

Answer 1

更多信息...接下来的 14 位是...

\n\n

5 Bits of HLIT, the Literal/Length codes - 257 (257 - 286)\n5 Bits of HDIST, the Distance codes - 1        (1 - 32)\n4 Bits of HCLEN, the Code Length codes - 4     (4 - 19)\n\nFrom the example:\n  HLIT => 29 + 257 = 286, HDIST => 15 + 1 = 16, HCLEN => 14 + 4 = 18\n

\n\n

现在收集 3 位值 HCLEN 次。遵循排列表的顺序（RFC-1951 第 13 页。）

\n\n

permuted ordering: [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]\n\nFrom the example: \n   HCLEN is 18 => 18*3 = 54-bits.\n   lengths: [ 4 2 4 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 ]\n

\n\n

接下来解压这些三位值。此解包提供了有关如何构造动态霍夫曼树\xe2\x80\xa6 \xe2\x80\x9c为了获得更大的紧凑性，代码长度序列本身使用霍夫曼代码进行压缩。\xe2\x80\x9d

\n\n

To unpack the triple-bit values: (examples below)\n  1. Count the number occurrences of the values.\n  2. Determine the offset, the count plus the previous offset.\n  3. Determine the symbols. \n     A symbol is placed at the offset value, which is found at a length value. \n     After placing a symbol, increment the offset.\n\n\nFrom the example: \n    LENGTHS: [ 4 2 4 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 ] //the three-bits from HCLEN\n    COUNT: [ 13 0 3 1 2 0 0 0 0 0 0 0 0 0 0 0 ] //the occurrences of lengths.\n      i.e, 0 occurs 13 times, 1 occurs 0 times, 2 occurs 3 times...\n    OFFSET: [ x 0 0 3 4 6 6 6 6 6 6 6 6 6 6 6 ] //the count plus the previous offset.\n      i.e, o[2] = 0 + 3, o[3] = 3 + 1, o[4] = 4 + 0...\n    SYMBOL: [ 1 4 18 17 0 2 ] //use length to index offset to place symbol\n      i.e, if i=1, s[off[len[i]]] = s[off[len[2]]] => s[off[0]] => s[0] = 1, increment off[0]...\n

\n\n

...符号现已定义。接下来解码位以构建动态霍夫曼树\xe2\x80\xa6

\n

Answer 2

这些值描述了动态霍夫曼树的什么？

它们并没有真正告诉您有关树的更多信息，而是在动态标头的后续位中描述了每种类型代码的多少个符号。

接下来提供十八个代码长度代码长度（每个三个比特），随后是286个文字/长度代码，然后是十六个距离代码，全部使用代码长度代码进行编码。

这些长度是否用于定义文字？

不是。三位长度是代码长度代码。您需要构建该代码只是为了读取以下文字/长度和距离代码长度，这些长度本身是使用该代码压缩的。

RFC 1951 的第 3.2.7 节对此进行了描述：

“为了更加紧凑，代码长度序列本身使用霍夫曼代码进行压缩。”