3

需要一些帮助来了解 DEFLATE 编码是如何工作的。我知道这是 LZSS 算法和霍夫曼编码的结合。

因此，让我们编码例如“Deflate Late”。Params: [Search buffer: 8kb and Look-ahead buffer 4kb] 那么LZSS算法的输出是“Deflate<5, 4>” 下一步使用静态huffman编码来减少冗余。这是我的问题，我不知道应该如何用霍夫曼对这对 <5, 4> 进行编码。

[已编辑]

D 000
f 001
l 010
a 011
t 100
_ 101
e 11

好吧，根据这张表，字符串“Deflate”写为 000 11 001 010 011 100 11 101。下一步让我们对 (5, 4) 对进行编码。《Data Compression - The Complete Reference》一书中长度为4的固定前缀码为258，后跟距离为5的固定前缀码（Code 4 + 1 Extra bit）。

这可以概括为：

长度 4 -> 258 -> 0000010
距离 5 -> 4 + 1 个额外位 -> 00100|0

因此，编码的字符串写为 [header: 1 01] 000 11 001 010 011 100 11 101 0000010 001000 [end-of-block: 0000000]，但是如果我创建一棵霍夫曼树，它就不再是静态霍夫曼了，正确的？

再会

4

1 回答 1

13 
D 000
f 001
l 010
a 011
t 100
_ 101
e 11

不是 Deflate 静态代码。静态文字/长度代码都是 7、8 或 9 位，距离代码都是 5 位。您询问了静态代码。

'Deflate Late' 以静态 deflate 格式编码为文字 'Deflate' 和长度为 4、距离 5 的十六进制匹配是：

73 49 4d cb 49 2c 49 55 00 11 00

分解如下（首先从每个字节的最低有效部分读取位）：

011 - 01 means fixed code, 1 means last block
00101110 - D
10101001 - e
01101001 - f
00111001 - l
10001001 - a
00100101 - t
10101001 - e
00001010 - space
0100000 - length 4
00100 - distance 5 or 6 depending on one extra bit
0 - extra bit -> distance 5
0000000 - end code
0 - fill bit to byte boundary
于 2013-07-01T23:24:39.013 回答