在 zlib 中，当字母的霍夫曼代码长度超过最大代码长度（15）时会发生什么？

Question

在https://www.rfc-editor.org/rfc/rfc1951

Note that in the "deflate" format, the Huffman codes for the
     various alphabets must not exceed certain maximum code lengths.

最大代码长度定义为 15。

霍夫曼码长度超过15会怎样？

来自https://cs.stackexchange.com/questions/75542/maximum-size-of-huffman-codes-for-an-alphabet-containing-256-letters 256 个符号字母表的最大可能代码大小为 256 位。考虑当最频繁的符号频率为 1/2 时的情况，下一个最频繁的符号频率为 1/4，然后是 1/8

所以在 literal/length 字母表中最大霍夫曼码长度是 285-1=284 但在 zlib 中最大代码长度是 15.

1. 为什么选择 15 作为最大代码长度？
2. 如果代码长度超过 15，zlib 会失败吗？

Answer 1

1. 我们不确定为什么 Phil Katz 选择 15，但这可能有助于在 16 位处理器中快速实现。

2. 不，zlib 不会失败。它一直在发生。 zlib 实现应用普通的霍夫曼算法，之后如果最长的代码长于 15 位，则进行 modify the codes to force them all to 15 bits or less.

请注意，生成 256 位长代码的示例需要一组 2²⁵⁶ ~= 10⁷⁷ 个符号为了到达那些频率。我认为你没有足够的内存。

无论如何，zlib 通常将 deflate 块限制为 16384 个符号。对于那个数字，最大霍夫曼代码长度是 19。它来自斐波那契概率序列，而不是你的 2 的幂。 （留作 reader 的练习。）