Deflate算法伪码

Question

我目前正在尝试了解DEFLATE算法是如何工作的。我知道它是LZ77和霍夫曼编码的结合。我已经研究了这两个是如何工作的，但我目前不知道它们是如何在DEFLATE中使用或集成的。

是否存在DEFLATE算法的伪代码？我一直在寻找它，但不幸的是，我看到的都是解释，没有确切的算法/伪代码来处理deflate。

非常感谢你的帮助。

顺便说一句，我已经查看了这个站点：http://www.zlib.net/feldspar.html http://www.gzip.org/algorithm.txt我还查看了RFC 1951文档。

例如，我有一个字符串"DEFLATE INFLATE“，它将如何使用DEFLATE进行压缩？

Answer 1

"DEFLATE DEFLATE“是一个非常短的字符串，因此将使用固定的霍夫曼编码进行编码。压缩数据的反汇编会产生以下结果：

last
fixed
literal 'DEFLATE IN
match 5 8
end

这意味着一个固定的块，这是最后一个块，文字字节"DEFLATE IN"，和一个字符串匹配八个字节返回五个字节，这复制了"FLATE“。

固定的霍夫曼编码编码文字字节和匹配长度和距离，以及标记块结束的结束代码。文字、长度和结束代码在一个霍夫曼代码中。如果一个长度被解码，那么后面跟着一个距离码，距离码来自它自己的霍夫曼码。

除了RFC1951，它完整而详细地解释了deflate格式，您还可以查看zlib发行版中的puff.c代码，该代码的目的是明确地记录deflate格式，因为它是一个简单、完整且注释良好的充气器。

您还可以使用生成上述示例的infgen.c来分解压缩结果(例如，使用gzip)以获得更深入的了解。

您首先需要通过阅读RFC、阅读和理解puff.c以及使用infgen.c查看示例来理解deflate格式。只有到那时，你才能开始考虑用压缩器创建放气流的方法。

如果您不了解RFC1951，那么您可能需要首先更深入地学习霍夫曼代码和LZ77。

Answer 2

与wikipedia中的一样

Deflate流由一系列块组成。每个块前面都有一个3位的报头，这些位的含义是：

First bit:流中最后一个块标记：

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

霍夫曼01，10 -->

对于LZ77，它是重复字符串的编码(距离，长度)。

在霍夫曼的情况下，霍夫曼树是预先约定的(将在压缩和解压缩中硬编码)。

在10 Huffman的情况下，以下是重新创建树的信息，然后是压缩数据。