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(应用程序分发):

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

计算说明:

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

即使不使用16,17和18,仍然有19个初始代码长度,因为它们首先被存储.

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

2286是可能的最低上限,因为在deflate格式中没有约束将头构造为最佳.可以构造代码长度代码,例如,长度为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个字节.它解压缩到零字节,没有错误.