如何从 DEFLATE 重建动态霍夫曼树
How to rebuild the dynamic Huffman tree from DEFLATE
这个问题是关于 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 产生这个 header:
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 header。
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
这些值描述了动态霍夫曼树的哪些内容？
接下来，一次读取三个位并进行排列table...发现长度为...
Lengths: [4, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2]（puff.c 的第 697 行）
这些长度是用来定义文字的吗？
What do these values describe about the dynamic Huffman tree?
他们并没有真正告诉你关于树的太多信息，而是在动态 header.
的后续位中描述了每种代码类型的符号数量。
接下来提供eighteen个码长code lengths（每个三位），接着是286个literal/length码然后是sixteen[=24] =]距离编码，全部使用编码长度编码。
Are these lengths used to define the literals?
没有。 three-bit 长度用于代码长度代码。您需要构建该代码只是为了阅读以下 literal/length 和距离代码长度，它们本身是使用该代码压缩的。
这在 RFC 1951 的第 3.2.7 节中有描述：
"For even greater compactness, the code length sequences themselves are compressed using a Huffman code."
header 包含 Deflate Literal (0-255)、长度 (256-285) 和距离代码 (0-29) 的位长度。如果您知道它们的位长度，您可以按照 RFC1951 第 3.2.2 节中的算法重建树。查找以 "Count the number of codes for each code length..."
开头的步骤
但是，位长度值也使用 0 到 7 位使用霍夫曼编码。需要先破解开头的HCLEN table，算法同上。第 3.2.7 节对此进行了解释。
为什么要对 header 进行两次编码？使动态霍夫曼 header 变小。
更多信息...接下来的 14 位是...
5 Bits of HLIT, the Literal/Length codes - 257 (257 - 286)
5 Bits of HDIST, the Distance codes - 1 (1 - 32)
4 Bits of HCLEN, the Code Length codes - 4 (4 - 19)
From the example:
HLIT => 29 + 257 = 286, HDIST => 15 + 1 = 16, HCLEN => 14 + 4 = 18
现在收集 3 位值 HCLEN 次。按照排列顺序 t table（来自 RFC-1951 的第 13 页。）
permuted ordering: [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
From the example:
HCLEN is 18 => 18*3 = 54-bits.
lengths: [ 4 2 4 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 ]
接下来解压缩这些三位值。此解包提供了有关如何构建动态霍夫曼树的说明……“为了更加紧凑，代码长度序列本身使用霍夫曼代码进行了压缩。”
To unpack the triple-bit values: (examples below)
1. Count the number occurrences of the values.
2. Determine the offset, the count plus the previous offset.
3. Determine the symbols.
A symbol is placed at the offset value, which is found at a length value.
After placing a symbol, increment the offset.
From the example:
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
COUNT: [ 13 0 3 1 2 0 0 0 0 0 0 0 0 0 0 0 ] //the occurrences of lengths.
i.e, 0 occurs 13 times, 1 occurs 0 times, 2 occurs 3 times...
OFFSET: [ x 0 0 3 4 6 6 6 6 6 6 6 6 6 6 6 ] //the count plus the previous offset.
i.e, o[2] = 0 + 3, o[3] = 3 + 1, o[4] = 4 + 0...
SYMBOL: [ 1 4 18 17 0 2 ] //use length to index offset to place symbol
i.e, if i=1, s[off[len[i]]] = s[off[len[2]]] => s[off[0]] => s[0] = 1, increment off[0]...
...符号现已定义。接下来解码位以构建动态哈夫曼树…
这个问题是关于 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 产生这个 header:
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 header。
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
这些值描述了动态霍夫曼树的哪些内容？
接下来，一次读取三个位并进行排列table...发现长度为...
Lengths: [4, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2]（puff.c 的第 697 行）
这些长度是用来定义文字的吗？
What do these values describe about the dynamic Huffman tree?
他们并没有真正告诉你关于树的太多信息，而是在动态 header.
的后续位中描述了每种代码类型的符号数量。接下来提供eighteen个码长code lengths（每个三位），接着是286个literal/length码然后是sixteen[=24] =]距离编码，全部使用编码长度编码。
Are these lengths used to define the literals?
没有。 three-bit 长度用于代码长度代码。您需要构建该代码只是为了阅读以下 literal/length 和距离代码长度，它们本身是使用该代码压缩的。
这在 RFC 1951 的第 3.2.7 节中有描述：
"For even greater compactness, the code length sequences themselves are compressed using a Huffman code."
header 包含 Deflate Literal (0-255)、长度 (256-285) 和距离代码 (0-29) 的位长度。如果您知道它们的位长度，您可以按照 RFC1951 第 3.2.2 节中的算法重建树。查找以 "Count the number of codes for each code length..."
开头的步骤但是，位长度值也使用 0 到 7 位使用霍夫曼编码。需要先破解开头的HCLEN table，算法同上。第 3.2.7 节对此进行了解释。
为什么要对 header 进行两次编码？使动态霍夫曼 header 变小。
更多信息...接下来的 14 位是...
5 Bits of HLIT, the Literal/Length codes - 257 (257 - 286)
5 Bits of HDIST, the Distance codes - 1 (1 - 32)
4 Bits of HCLEN, the Code Length codes - 4 (4 - 19)
From the example:
HLIT => 29 + 257 = 286, HDIST => 15 + 1 = 16, HCLEN => 14 + 4 = 18
现在收集 3 位值 HCLEN 次。按照排列顺序 t table（来自 RFC-1951 的第 13 页。）
permuted ordering: [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
From the example:
HCLEN is 18 => 18*3 = 54-bits.
lengths: [ 4 2 4 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 ]
接下来解压缩这些三位值。此解包提供了有关如何构建动态霍夫曼树的说明……“为了更加紧凑，代码长度序列本身使用霍夫曼代码进行了压缩。”
To unpack the triple-bit values: (examples below)
1. Count the number occurrences of the values.
2. Determine the offset, the count plus the previous offset.
3. Determine the symbols.
A symbol is placed at the offset value, which is found at a length value.
After placing a symbol, increment the offset.
From the example:
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
COUNT: [ 13 0 3 1 2 0 0 0 0 0 0 0 0 0 0 0 ] //the occurrences of lengths.
i.e, 0 occurs 13 times, 1 occurs 0 times, 2 occurs 3 times...
OFFSET: [ x 0 0 3 4 6 6 6 6 6 6 6 6 6 6 6 ] //the count plus the previous offset.
i.e, o[2] = 0 + 3, o[3] = 3 + 1, o[4] = 4 + 0...
SYMBOL: [ 1 4 18 17 0 2 ] //use length to index offset to place symbol
i.e, if i=1, s[off[len[i]]] = s[off[len[2]]] => s[off[0]] => s[0] = 1, increment off[0]...
...符号现已定义。接下来解码位以构建动态哈夫曼树…