zlib - 在 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-letters256 个符号字母表的最大可能代码大小为 256 位。考虑当最频繁的符号频率为 1/2，下一个最频繁的符号频率为 1/4，然后是 1/8 的情况

所以在文字/长度字母表中，最大霍夫曼代码长度是 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 block 限制为 16384 个符号。对于该数字，最大霍夫曼代码长度为 19。它来自类似斐波那契(Lucas)的概率序列，而不是您的 2 的幂。 (留作读者练习。)