zlib - DEFLATE (zlib, gzip) 格式使用的编码动态霍夫曼树的最大大小是多少？

Question

https://www.ietf.org/rfc/rfc1951.txt 的“3.2.7. 使用动态霍夫曼代码压缩(BTYPE=10)”部分描述了压缩期间使用的动态哈夫曼树的编码。可能出现在 DEFLATE 比特流中的这种编码的霍夫曼树表示的最大大小(以比特为单位)是多少？用外部引用支持特定图形的额外要点;-)。

这是一个更好地理解 DEFLATE 属性的理论问题。但当然它有实际应用，例如，“应该使用多大的缓冲区来保证解码哈夫曼树？”

Answer 1

可以根据您已经提供的引用轻松计算动态块头长度的上限。从 RFC 1951，第 3.2.7 节，我们可以将这些位相加:

3 + 5 + 5 + 4 + 19 * 3 + (286 + 30) * 7 = 2286 位 = 285.75 字节。

(有关详细信息，请参阅下面的计算说明。)

在实践中，您永远不会看到接近 286 字节的长度。更典型的长度是 60 到 90 个字节。

这是来自 linux 的 gzip 源分发的动态头块长度的直方图，linux-3.1.6.tar.gz :



他们看起来并不都一样。这是 Archive.pax.gz 的另一个(应用程序分发):



双峰形状可能是可执行文件与文本。可执行文件对所有文字字节值进行编码，从而产生更大的动态 header 来描述所有这些值的代码。

计算注意事项:

我故意没有为符号 16、17 或 18 添加可能的额外位，因为使用这些代码中的任何一个，包括它们的额外位，都会减少 header 的长度，而不是增加它。 16 符号将用 9 位替换 21 到 42 位，17 符号将用 10 位替换 21 到 70 位，而 18 符号将用 14 位替换 77 到 966 位(假设所有符号都是 7 位) .

即使不使用 16、17 和 18，仍然有 19 个初始代码长度，因为它们是最先存储的。

我将文字/长度代码长度限制为 286，将距离代码长度限制为 30，因为兼容的充气机将拒绝高于此值的值。

2286 是可能的最低上限，因为在 deflate 格式中没有将 header 构造为最佳的约束。可以构造码长code，例如，将长度4、5、8、9都设为7位码，然后仅使用长度列表中的那些来构造完整的文字/长度和距离代码。代码长度代码也必须是完整的，但这可以通过将较短的代码分配给未使用的长度来实现。

简而言之，可以构造一个完全有效的动态块头，其长度为 2286 位。事实上，这是一个(有很多方法可以做到这一点):

ed fd 01 e0 38 70 1c 28 a7 fc 7e bf df ef f7 fb
fd 7e bf df ef f7 fb fd 7e bf df ef f7 fb fd 7e
bf df ef f7 fb fd 7e bf df ef f7 fb fd 7e bf df
ef f7 fb fd 7e bf df ef f7 fb fd 7e bf df ef f7
fb fd 7e bf df ef f7 fb fd 7e bf df ef f7 fb fd
7e bf df ef f7 fb fd 7e bf df ef f7 fb fd 7e bf
df ef f7 fb fd 7e bf df ef f7 fb fd 7e bf df ef
f7 fb fd 7e bf df ef f7 fb fd 7e bf df ef f7 fb
fd 7e bf df ef f7 fb fd 7e bf df ef f7 fb fd 7e
bf df ef f7 fb fd 7e bf df ef f7 fb fd 7e bf df
ef f7 fb fd 7e bf df ef f7 fb fd 7e bf df ef f7
fb fd 7e bf df ef f7 fb fd 7e bf df ef f7 fb fd
7e bf df ef f7 fb fd 7e bf df ef f7 fb fd 7e ff
ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
ff ff ff ff f9 7c bf df ef f7 fb fd 7e bf df ef
f7 fb fd 7e bf df ef f7 fb fd 7e bf df ef 23

这是一个以十六进制表示的有效且完整的 deflate 流。它由一个单独的动态块组成，标记为最后一个块，带有一个 2286 位的动态头和一个 9 位的块结束码，总共 2295 位，四舍五入为 287 字节。它解压缩到零字节而没有错误。