紧缩算法伪代码

Question

我目前正尝试理解DEFLATE算法的工作原理。我知道它是LZ77和Huffman编码的组合。我已经学习了这两个算法的工作原理，但我目前不知道它们如何在DEFLATE中使用或集成。

是否有DEFLATE算法的伪代码？我一直在搜索，但不幸的是，我看到的都是解释，没有精确的算法/伪代码可用于压缩。

非常感谢您的帮助。

顺便说一下，我已经检查了以下网站： http://www.zlib.net/feldspar.html http://www.gzip.org/algorithm.txt 我还检查了RFC 1951文档

例如，我有字符串“DEFLATE INFLATE”，如何使用DEFLATE进行压缩？

- bless1204

Answer 1

"

“DEFLATE INFLATE”是一个非常短的字符串，因此将使用固定的哈夫曼编码进行编码。压缩数据的反汇编结果如下：

"

last
fixed
literal 'DEFLATE IN
match 5 8
end

这意味着一个单一的固定块，它是最后一个块，“DEFLATE IN”字面字节和一个字符串匹配八个字节回溯五个字节，复制“FLATE”。

固定的霍夫曼码编码了字面字节、匹配长度和距离，以及标记块结束的结尾码。字面、长度和结尾码在一个霍夫曼码中。如果解码出一个长度，那么就会跟随一个来自它自己的霍夫曼码的距离码。

除了 RFC 1951 完整详细地解释了 deflate 格式之外，您还可以查看 zlib 发行版中旨在通过成为简单、完整和注释齐全的解压器而无歧义地记录 deflate 格式的 puff.c 代码。

您还可以使用 infgen.c 对 deflate 压缩的结果进行反汇编（例如使用 gzip）以获得更多见解。

你需要先阅读RFC文档，可能需要查看并理解puff.c和infgen.c的例子，来了解deflate格式。只有这样，你才能开始思考使用压缩器创建deflate流的方法。

如果你无法理解RFC 1951，则可能需要深入研究霍夫曼编码和LZ77算法。

- Mark Adler

Answer 2

如wikipedia所述：

一个Deflate流由一系列块组成。每个块之前都有一个3位头，位的含义如下：

第一位：流中最后一个块的标记：

1: this is the last block in the stream.
0: there are more blocks to process after this one.

第二位和第三位：用于此块类型的编码方法：

00: a stored/raw/literal section, between 0 and 65,535 bytes in length.
01: a static Huffman compressed block, using a pre-agreed Huffman tree.
10: a compressed block complete with the Huffman table supplied.
11: reserved, don't use.

00 --> LZ77
在LZ77中，编码为（距离，长度）的重复字符串。

01, 10 --> Huffman
在01的Huffman编码中，哈夫曼树是预先约定的（将在压缩和解压缩中进行硬编码）。

在10的Huffman编码中，以下是重新创建树和压缩数据所需的信息。

- NetVipeC