huffman-code - 如何从 DEFLATE 重建动态霍夫曼树

Question

此问题与 RFC-1951 的第 3.2.7 节有关，重建动态哈夫曼树。

每个代码由一系列代码长度定义，以便给定位长度的所有代码都具有字典序连续值。

例如，这是一个 rgb(255,0,0) 50x50 png，其中 IDAT 是来自 DEFLATE 的动态 Huf​​fman 树。

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 header 。

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

接下来的 14 位描述了 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 位是……

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 次。按照排列表的顺序(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]...

...现在定义了符号。接下来解码位以构建动态霍夫曼树……