在 zlib 中，当字母表的霍夫曼代码长度超过最大代码长度 (15) 时会发生什么?

Question

in 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

所以在文字/长度字母表中，最大霍夫曼代码长度为 285-1=284 但在 zlib 中，最大代码长度为 15。

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

Answer 1

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

2. 不，zlib 不会失败。它一直在发生。zlib 实现应用了普通的霍夫曼算法，之后如果最长的代码超过 15 位，它将继续修改代码以强制它们全部为 15 位或更少。

256 符号字母表的最大可能霍夫曼代码大小为 255 位，而不是 256 位。最后两个符号的长度相同，为 255。

不过，您不会遇到输入会导致代码这么长的情况。您需要大约 3x10⁵³个符号的最小输入大小才能获得 255 位长的代码。我想你没有足够的内存来做这件事。

无论如何，zlib 通常将放气块限制为 16384 个符号。对于该数字，最大霍夫曼代码长度为 19。这来自类似斐波那契(卢卡斯)的概率序列，而不是你的二次方。(留给读者练习。