DEFLATE算法中Huffman树传输、codelength含义及游程压缩相关疑问

codelength的准确含义与0值说明 #

codelength（码长）指的是Huffman树中每个字母表符号对应的编码比特长度。DEFLATE标准约定了Huffman树的生成规则：解码端只要拿到所有符号的码长序列，就能按照码长从小到大、同码长按符号序号从小到大的规则，自动重构出和编码端完全一致的Huffman树，不需要额外传输树的结构信息，这也是DEFLATE高效的核心设计之一。

码长取值为0，代表对应符号在当前待压缩的块中从未出现过，不需要为其分配任何编码位，解码时可以直接判定该符号不存在。文档中提到的「末尾码长为0可以省略」也是基于这个逻辑：如果字母表尾部连续多个符号的码长都是0，说明这些符号全部没有用到，传输时可以直接截断序列不传递这部分0值，解码端只要拿到约定的字母表总长度，自动在尾部补0即可，进一步节省传输空间。

codelength序列的游程压缩逻辑 #

因为codelength序列中通常会存在大量连续的相同值（最常见的是连续的0，对应大量未使用的符号），所以DEFLATE会先对codelength序列做一次游程编码压缩，再对压缩后的序列做Huffman编码，进一步降低头信息的体积。
具体规则如下：

• 原始codelength的取值范围是0_{15，DEFLATE额外定义了3个游程控制符，将序列的取值范围扩展到0}18：
  • 0~15：直接代表当前符号的codelength为对应数值，无特殊逻辑
  • 16：重复前一个位置的codelength值，重复次数为后续3个额外比特的数值加3，重复范围是3~6次
  • 17：重复codelength=0，重复次数为后续3个额外比特的数值加3，重复范围是3~10次
  • 18：重复codelength=0，重复次数为后续7个额外比特的数值加11，重复范围是11~138次

举个实际示例：如果原始codelength序列为[0,0,0,0,0,0,4,4,4,4]，经过游程编码后会变成[17, 3, 4, 16, 1]，其中：

• 17 + 3（3比特的额外值）= 重复6个0
• 4代表当前符号码长为4
• 16 + 1（3比特的额外值）= 重复上一个码长4共4次

游程编码完成后，会为这个0~18的符号序列生成一棵专用的Huffman树，用这棵树对序列做编码，再把编码结果和对应的额外比特拼接起来，就得到了最终要传输的Huffman树头信息。解码端会先解码这棵小的Huffman树，还原出完整的codelength序列，再用codelength序列重构出用来解实际压缩数据的Huffman树。

内容的提问来源于stack exchange，提问作者rayanJ