encoding - 使用静态霍夫曼码进行 DEFLATE 编码

Question

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

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

[编辑]

000
001
010
011
吨 100
_ 101
11

好吧，根据这张表，字符串“Deflate”被写为 000 11 001 010 011 100 11 101。下一步让我们对 (5, 4) 进行编码。根据《数据压缩-完整引用》一书，长度为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]，但是如果我创建一个霍夫曼树，它不再是一个静态的哈夫曼对？

再会

Answer 1

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