时间戳

首页 > 解决方案 > Deflate：顶级HCLEN的代码长度> 7位？

gzip - Deflate：顶级HCLEN的代码长度> 7位？

问题描述

RFC 1951 指定块中的第一级编码包含 HCLEN 3 位值，这些值对下一级霍夫曼码的长度进行编码。由于这些是 3 位值，因此下一级的代码不能超过 7 位（111二进制）。但是，似乎有一些极端情况（至少使用“经典”算法来构建霍夫曼代码，使用优先级队列）显然会生成 8 位代码，当然不能对其进行编码。

我想出的一个例子如下（这表示由 RLE 编码产生的 19 个可能的符号，0-15 加上 16、17 和 18）：

symbol | frequency
-------+----------
0      | 15
1      | 14
2      | 6
3      | 2
4      | 18
5      | 5 
6      | 12
7      | 26
8      | 3
9      | 20
10     | 79
11     | 94
12     | 17
13     | 7
14     | 8
15     | 4
16     | 16
17     | 1 
18     | 13

根据各种在线计算器（例如https://people.ok.ubc.ca/ylucet/DS/Huffman.html），以及手工构建树，上表中的一些符号（即 3 和 17）产生 8 -位长的霍夫曼码。生成的树对我来说看起来不错，有 19 个叶节点和 18 个内部节点。那么，有没有一种特殊的方法来计算用于 DEFLATE 的 Huffman 码？

标签： gziphuffman-codedeflate

解决方案

是的。deflate 使用长度有限的霍夫曼代码。您需要修改后的限制长度的霍夫曼算法，或缩短超出长度的霍夫曼代码的算法。（zlib是后者。）

除了代码长度代码被限制为 7 位之外，文字/长度和距离代码被限制为 15 位。在将 Huffman 算法应用于压缩期间遇到的频率集时，超出这些限制并不少见。

尽管您的示例不是该代码的有效或可能的频率集。这是一个产生 9 位霍夫曼代码的有效示例，然后需要将其压缩为 7 位：

3 0 0 5 5 1 9 31 58 73 59 28 9 1 2 0 6 0 0

推荐阅读