Deflate：顶级 HCLEN 的代码长度 > 7 位？
Deflate: code lengths of > 7 bits for top-level HCLEN?
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），也手工建树，上面table中的一些符号（即3和17）产生8位长的霍夫曼码.生成的树对我来说看起来不错，有 19 个叶节点和 18 个内部节点。
那么，有没有一种特殊的方法来计算用于 DEFLATE 的霍夫曼码？
是的。 deflate 使用长度限制的霍夫曼代码。您需要 modified Huffman algorithm that limits the length, or an algorithm that shortens a Huffman code that has exceeded the length. (zlib does the latter.)
除了代码长度代码限制为 7 位外，literal/length 和距离代码也限制为 15 位。将霍夫曼算法应用于压缩过程中遇到的频率集时，超过这些限制的情况并不少见。
尽管您的示例不是该代码的有效或可能的频率集。这是一个产生 9 位霍夫曼代码的有效示例，然后需要将其压缩为 7 位：
3 0 0 5 5 1 9 31 58 73 59 28 9 1 2 0 6 0 0
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），也手工建树，上面table中的一些符号（即3和17）产生8位长的霍夫曼码.生成的树对我来说看起来不错，有 19 个叶节点和 18 个内部节点。 那么，有没有一种特殊的方法来计算用于 DEFLATE 的霍夫曼码？
是的。 deflate 使用长度限制的霍夫曼代码。您需要 modified Huffman algorithm that limits the length, or an algorithm that shortens a Huffman code that has exceeded the length. (zlib does the latter.)
除了代码长度代码限制为 7 位外，literal/length 和距离代码也限制为 15 位。将霍夫曼算法应用于压缩过程中遇到的频率集时，超过这些限制的情况并不少见。
尽管您的示例不是该代码的有效或可能的频率集。这是一个产生 9 位霍夫曼代码的有效示例，然后需要将其压缩为 7 位：
3 0 0 5 5 1 9 31 58 73 59 28 9 1 2 0 6 0 0