1. 1
    2
    3
    4
    		 
    hash table: {}
    abcabcdabcde
    ^
    output: a
    		 

  2. 1
    2
    3
    4
    		 
    hash table: {"abc":[0],"bca":[1],"cab":[2]}
    abcabcdabcde
       ^
    output: abc<3,3>
    		 

  3. 1
    2
    3
    4
    		 
    hash table: {"abc":[0,3],"bca":[1],"cab":[2],"bcd":[4],"cda":[5],"dab":[6]}
    abcabcdabcde
           ^
    output: abc<3,3>d<4,4>
    		 

1
2
 
|-------search-------+------lookahead-----|
                     ^
 

1
2
3
4
 
hash table: {"abc":[0],"bcb":[1],"cbc":[2],"bcd":[3],"cda":[4],"dab":[5]}
abcbcdabcda
      ^
output: abcbcd<6,3>

character times
a 1
b 4
c 4
d 3
e 1

character code
a 000
b 10
c 11
d 01
e 001

  • code extra distance code extra distance code extra distance
    0 0 1 10 4 33-48 20 9 1025-1536
    1 0 2 11 4 49-64 21 9 1537-2048
    2 0 3 12 5 65-96 22 10 2049-3072
    3 0 4 13 5 97-128 23 10 3073-4096
    4 1 5,6 14 6 129-192 24 11 4097-6144
    5 1 7,8 15 6 193-256 25 11 6145-8192
    6 2 9-12 16 7 257-384 26 12 8193-12288
    7 2 13-16 17 7 385-512 27 12 12289-16384
    8 3 17-24 18 8 513-768 28 13 16385-24576
    9 3 25-32 19 8 769-1024 29 13 24577-32768

  • code extra length(s) code extra length(s) code extra length(s)
    257 0 3 267 1 15,16 277 4 67-82
    258 0 4 268 1 17,18 278 4 83-98
    259 0 5 269 2 19-22 279 4 99-114
    260 0 6 270 2 23-26 280 4 115-130
    261 0 7 271 2 27-30 281 5 131-162
    262 0 8 272 2 31-34 282 5 163-194
    263 0 9 273 3 35-42 283 5 195-226
    264 0 10 274 3 43-50 284 5 227-257
    265 1 11,12 275 3 51-58 285 0 258
    266 1 13,14 276 3 59-66

character code
a 110
b 00
c 01
d 10
e 111

code meaning
0-15 表示长度 0 至 15
16 前面的长度重复 3 到 6 次. 接下来的两位指示具体重复多少次, 这与 3.2 节中的长度和距离编码类似.
17 长度 0 重复 3 至 10 次. 接下来的 3 位指示具体重复多少次.
18 长度 0 重复 11 至 138 次. 接下来的 7 位指示具体重复多少次.

name length description
BFINAL 1 位 标识是否是最后一个区块
BTYPE 2 位 标识类型. 00 : 未压缩; 01 : 静态 Huffman 编码压缩; 10 : 动态 Huffman 编码压缩; 11 : 保留

name length description
LEN 2 位 区块数据长度
NLEN 2 位 LEN 的补码
DATA LEN 字节 有效数据

name length description
HLIT 5 位 长度/字符编码的最大值减 257. 因为并不是所有的长度编码都被使用, 因此这里标记最大的长度/字符编码(长度与普通字符共用同一编码空间).
HDIST 5 位 距离编码最大值减 1. 原理同上.
HCLEN 4 位 3.2.3 节中的 k 减 4. 标识使用了神秘数组中的前几个编码.
编码后的长度序列的 Huffman 编码表 (HCLEN + 4) * 3 位 如 3.2.3 节所述的 “k 个数字”. 因为长度序列编码只有 19 个, 因此每个数字 3 位就够了.
长度/字符编码的 Huffman 编码表 变长 根据上述 Huffman 编码表编码的长度序列, 用于表示长度/字符编码的 Huffman 编码表.
距离编码的 Huffman 编码表 变长 根据上述 Huffman 编码表编码的长度序列, 用于表示距离编码的 Huffman 编码表.
DATA 变长 有效压缩数据
256 结束标记 变长 标识区块的结束