LZ77压缩算法详解

1、gzip 、zlib以及图形格式png,使用的压缩算法都是 deflate 算法。从gzip的源码中，我们了解到了 defalte 算法的原理和实现。 我阅读的 gzip 版本为 gzip-1.2.4 。下面我们将要对 deflate 算法做一个分析和说明。 首先简单介绍一下基本原理，然后详细的介绍实现。 1 gzip 所使用压缩算法的基本原理 gzip对于要压缩的文件，首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用Huffman编码的 方法(实际上 gzip 根据情况， 选择使用静态 Huffman 编码或者动态 Huffman 编码，详细内容在实现中说明) 进行压缩。所以明白了

2、 LZ77算法和Huffman编码的压缩原理，也就明白了 gzip的压缩原理。我们来对LZ77 算法和 Huffman 编码做一个简单介绍。 1.1 LZ77 算法简介 这一算法是由 Jacob Ziv 和 Abraham Lempel 于 1977 年提出，所以命名为 LZ77。 1.1.1 LZ77 算法的压缩原理 如果文件中有两块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后一块的内容。所 以我们可以用(两者之间的距离，相同内容的长度)这样一对信息，来替换后一块内容。由于(两者之间 的距离，相同内容的长度)这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。 下面

3、我们来举一个例子。 有一个文件的内容如下 其中有些部分的内容，前面已经出现过了，下面用 () 括起来的部分就是相同的部分。 (.)nease(.net) 我们使用 ( 两者之间的距离，相同内容的长度 ) 这样一对信息，来替换后一块内容。 (22.13) nease(23,4) (22.13) 中， 22为相同内容块与当前位置之间的距离，13为相同内容的长度。 (23,4) 中， 23为相同内容块与当前位置之间的距离，4为相同内容的长度。 由于(两者之间的距离，相同内容的长度)这一对信息的大小，小于被替换内容的大小，所以文件得到了 压缩。 1.1.2 LZ77 使用滑动窗口寻找匹配串 LZ77算

4、法使用滑动窗口 的方法，来寻找文件中的相同部分，也就是匹配串。我们先对这里的串做一个说 明，它是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强 调的是它在文件中的位置，它的长度随着匹配的情况而变化。 LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口(在当前处理字节之 前，并且紧挨着当前处理字节） ，随着处理的字节不断的向后滑动，就象在阳光下，飞机的影子滑过大地一 样。对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。 窗口中的每个串指， 窗口中每个字节开始的串。 如果当前处理字节开始的串

5、在窗口中有匹配串， 就用（ 之间 的距离，匹配长度 ） 这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。 如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。 处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任 何内容，被处理的字节就会不做改动的输出。随着处理的不断向后，窗口越来越多的滑入文件，最后整个 窗口滑入文件，然后整个窗口在文件上向后滑动，直到整个文件结束。 1.1.3使用LZ77算法进行压缩和解压缩 为了在解压缩时，可以区分“没有匹配的字节”和“（之间的距离，匹配长度）对”，我们还需要在每个

6、“没有匹配的字节”或者“ （之间的距离， 匹配长度） 对”之前， 放上一位，来指明是“没有匹配的字节”， 还是“（之间的距离，匹配长度）对”。我们用0表示“没有匹配的字节”，用 1 表示“（之间的距离，匹 配长度）对”。 实际中，我们将固定（之间的距离，匹配长度）对中的，“之间的距离”和“匹配长度”所使用的位数。 由于我们要固定“之间的距离”所使用的位数，所以我们才使用了固定大小的窗口，比如窗口的大小为 32KB,那么用15位（2T5=32K）就可以保存0-32K范围的任何一个值。实际中，我们还将限定最大的匹配 长度，这样一来，“匹配长度”所使用的位数也就固定了。 实际中，我们还将设定一个最小

7、匹配长度，只有当两个串的匹配长度大于最小匹配长度时，我们才认为是 一个匹配。 我们举一个例子来说明这样做的原因。 比如， “距离”使用 15位， “长度”使用 8位，那么“（之 间的距离， 匹配长度）对”将使用 23位，也就是差 1位3个字节。如果匹配长度小于 3个字节的话， 那么用“（之 间的距离，匹配长度）对”进行替换的话，不但没有压缩，反而会增大，所以需要一个最小匹配长度。 压缩： 从文件的开始到文件结束，一个字节一个字节的向后进行处理。用当前处理字节开始的串，和滑动窗口中 的每个串进行匹配，寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串，就先输出一个标 志位，表明下面是一个

8、 （之间的距离，匹配长度 ） 对，然后输出 （ 之间的距离，匹配长度 ） 对，然后从刚才 处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就先输出一 个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，然后继续处理当前处理 字节的下一个字节。 解压缩： 从文件开始到文件结束， 每次先读一位标志位， 通过这个标志位来判断下面是一个 （之间的距离， 匹配长度 ） 对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距 离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就

9、读 出一个字节，然后输出这个字节。 我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对 于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。 1.2 Huffman 编码简介 1.2.1 Huffman 编码的压缩原理 我们把文件中一定位长的值看作是符号，比如把 8位长的 256种值，也就是字节的 256种值看作是符号。 我们 根据这些符号在文件中出现的频率，对这些符号重新编码。对于出现次数非常多的，我们用较少的位来表 示，对于出现次数非常少的，我们用较多的位来表示。这样一来，文件的一些部分位数变少了，一些部分 位数变多了，

10、由于变小的部分比变大的部分多，所以整个文件的大小还是会减小，所以文件得到了压缩。 1.2.2 Huffman 编码使用 Huffman 树来产生编码 要进行 Huffman 编码，首先要把整个文件读一遍，在读的过程中，统计每个符号（我们把字节的256种值看 作是256种符号）的出现次数。然后根据符号的出现次数，建立Huffman树，通过Huffman树得到每个符号 的新的编码。对于文件中出现次数较多的符号，它的 Huffman 编码的位数比较少。对于文件中出现次数较 少的符号，它的 Huffman 编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。 建立 Huffman 树： 把所有

11、符号看成是一个结点，并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的 树。 每次从所有树中找出值最小的两个树，为这两个树建立一个父结点，然后这两个树和它们的父结点组成一 个新的树，这个新的树的值为它的两个子树的值的和。如此往复，直到最后所有的树变成了一棵树。我们 就得到了一棵 Huffman 树。 通过 Huffman 树得到 Huffman 编码： 这棵 Huffman 树，是一棵二叉树，它的所有叶子结点就是所有的符号，它的中间结点是在产生Huffman 树 的过程中不断建立的。 我们在 Huffman 树的所有父结点到它的左子结点的路径上标上 0，右子结点的路径上 标上

12、1。 现在我们从根节点开始，到所有叶子结点的路径，就是一个0和1的序列。我们用根结点到一个叶子结点路 径上的 0和1的序列，作为这个叶子结点的Huffman 编码。 我们来看一个例子。 有一个文件的内容如下 abbbbccccddde 我们统计一下各个符号的出现次数， a b c d e 1 4 4 3 1 建立 Huffman 树的过程如图： 2. b c a e b c a e 通过最终的 Huffman 树，我们可以得到每个符号的 Huffman 编码。 a 为 110 b 为 00 c 为 01 d 为 10 e 为 111 我们可以看到， Huffman 树的建立方法就保证了，出现次

13、数多的符号，得到的 Huffman 编码位数少，出现 次数少的符号，得到的 Huffman 编码位数多。 各个符号的 Huffman 编码的长度不一，也就是变长编码。对于变长编码，可能会遇到一个问题，就是重新 编码的文件中可能会无法如区分这些编码。 比如， a 的编码为 000，b 的编码为 0001 ，c 的编码为 1，那么当遇到 0001时，就不知道 0001代表 ac ，还是代 表 b 。出现这种问题的原因是 a 的编码是 b 的编码的前缀。 由于 Huffman 编码为根结点到叶子结点路径上的 0和1的序列，而一个叶子结点的路径不可能是另一个叶子 结点路径的前缀，所以一个 Huffma

14、n 编码不可能为另一个 Huffman 编码的前缀，这就保证了 Huffman 编码 是可以区分的。 1.2.3 使用 Huffman 编码进行压缩和解压缩 为了在解压缩的时候，得到压缩时所使用的 Huffman 树，我们需要在压缩文件中，保存树的信息，也就是 保存每个符号的出现次数的信息。 压缩： 读文件， 统计每个符号的出现次数。 根据每个符号的出现次数， 建立 Huffman 树， 得到每个符号的 Huffman 编码。将每个符号的出现次数的信息保存在压缩文件中，将文件中的每个符号替换成它的 Huffman 编码， 并输出。 解压缩： 得到保存在压缩文件中的，每个符号的出现次数的信息。根

15、据每个符号的出现次数，建立 Huffman 树，得 到每个符号的 Huffman 编码。将压缩文件中的每个 Huffman 编码替换成它对应的符号，并输出。 2 gzip 所使用压缩算法的实现 我们将 gzip 的实现分成很多个部分，一个个来说明，这样做的原因见本文最后一部分。 gzip 中所使用的各种实现技巧的出处或者灵感， gzip 的作者在源码的注释中进行了说明。 2.1 寻找匹配串的实现 为一个串寻找匹配串需要进行大量的匹配工作， 而且我们还需要为很多很多个串寻找匹配串。 所以 gzip 在 寻找匹配串的实现中使用哈希表来提高速度。 要达到的目标是，对于当前串，我们要在它之前的窗口中，

16、寻找每一个匹配长度达到最小匹配的串，并找 出匹配长度最长的串。 在 gzip 中，最小匹配长度为 3 ，也就是说，两个串，最少要前3 个字节相同，才能算作匹配。为什么最小 匹配长度为 3，将在后面说明。 gzip 对遇到的每一个串， 首先会把它插入到一个“字典”中。 这样当以后有和它匹配的串， 可以直接从“字 典”中查出这个串。 插入不是乱插，查也不是乱查。插入的时候，使用这个插入串的前三个字节，计算出插入的“字典”位置， 然后把插入串的开始位置保存在这个“字典”位置中。 查出的时候， 使用查出串的前三个字节， 计算出“字 典”位置，由于插入和查出使用的是同一种计算方法，所以如果两个串的前三个

17、字节相同的话，计算出的 “字典”位置肯定是相同的，所以就可以直接在该“字典”位置中，取出以前插入时，保存进去的那个串 的开始位置。于是查出串，就找到了一个串，而这个串的前三个字节和自己的一样（其实只是有极大的可 能是一样的，原因后面说明） ，所以就找到了一个匹配串。 如果有多个串，他们的前三个字节都相同，那么他们的“字典”位置，也都是相同的，他们将被链成一条 链，放在那个“字典”位置上。所以，如果一个串，查到了一个“字典”位置，也就查到了一个链，所有 和它前三个字节相同的串，都在这个链上。 也就是说，当前串之前的所有匹配串被链在了一个链上，放在某个“字典”位置上。而当前串使用它的前 三个字节，

18、进行某种计算，就可以得到这个“字典”位置（得到了“字典”位置之后，它首先也把自己链 入到这个链上） ，也就找到了链有它的所有匹配串的链， 所以要找最长的匹配， 也就是遍历这个链上的每一 个串，看和哪个串的匹配长度最大。 下面我们更具体的说明，寻找匹配串的实现。 我们前面所说的“字典”，是一个数组，叫做head （为什么叫 head, 后面进行说明） 。 我们前面所说的“字典”位置，放在一个叫做ins_h 的变量中。 我们前面所说的链，是在一个叫做 prev 的数组中。 插入： 当前字节为第 strstart 个字节。通过第 strstart,strstart+1,strstart+2,这三个字

19、节，使用一个设计 好的哈希函数算出 ins_h ，也就是插入的位置。 然后将当前字节的位置， 即 strstart ，保存在 headins_h 中。 注意由 strstart,strstart+1,strstart+2, 这三个字节 （也就是 strstart 开始处的串的头三个字节， 也就 是当前字节和之后的两个字节）确定了 ins_h。headins_h中保存的又是strstart ,也就是这个串开始的 位置。 判断是否有匹配： 当前串的前三个字节， 使用哈希函数算出 ins_h ，这时如果 headins_h 的值不为空的话， 那么 headins_h 中的值，便是之前保存在这里的另一

20、个串的位置，并且这个串的前三个字节算出的 ins_h ，和当前串的前 三个字节算出的 ins_h 相同。也就是说有可能有匹配。如果 headins_h 的值为空的话，那么肯定没有匹 配。 gzip 所使用的哈希函数： gzip 所使用的哈希函数，用三个字节来计算一个 ins_h ，这是由于最小匹配为三个字节。 对于相同的三个字节，通过哈希函数得到的 ins_h 必然是相同的。 而不同的三个字节，通过哈希函数有可能得到同一个 ins_h ，不过这并不要紧， 当 gzip 发现 headins_h 不空后，也就是说有可能有匹配串的话，会对链上的每一个串进行真正的串的比 较。 所以一个链上的串，只是

21、前三个字节用哈希函数算出的值相同，而并不一定前三个字节都是相同的。但是 这样已经很大的缩小了需要进行串比较的范围。 我们来强调一下，前三个字节相同的串，必然在同一个链上。在同一个链上的，不一定前三个字节都相同。 不同的三个字节有可能得到同一个结果的原因是，三个字节，一共24位，有2A24种可能值。而三个字节的 哈希函数的计算结果为15位，有2T5种可能值。也就是说2A24种值，与2T5种值进行对应，必然是多对一 的，也就是说，必然是有多种三个字节的值，用这个哈希函数计算出的值都是相同的。 而我们使用哈希函数的理由是，实际上，我们只是在一个窗口大小的范围内（后面将会看到）寻找匹配串， 一个窗口的

22、大小范围是很有限的，能出现的三个字节的值组合情况也是很有限的，将远远小于2A24，使用 合适的哈希函数是高效的。 前三个字节相同的所有的串所在的链： headins_h 中的值，有两个作用。一个作用，是一个前三个字节计算结果为ins_h 的串的位置。另一个 作用，是一个在 prev 数组中的索引， 用这个索引在 prev 中，将找到前一个前三个字节计算结果为 ins_h 的串的位置。即 prevheadins_h 的值（不为空的话）为前一个前三个字节计算结果为 ins_h 的串的位 置。 prev 的值，也有两个作用。一个作用，是一个前三个字节计算结果为ins_h 的串的位置。另一个作用， 是

23、一个在 prev 数组中的索引， 用这个索引在 prev 中，将找到前一个前三个字节计算结果为 ins_h 的串 的位子哈。即 prev 的值（不为空的话）为前一个三个字节计算结果为ins_h 的串的位置。 直到 prev 为空，表示链结束。 我们来举一个例子，串， 0abcd abce,abcf_abcg 当处理到 abcg 的 a 时，由 abcg 的 abc 算出 ins_h 这时的 headins_h 中为 11 ，即串 abcf abcg 的开始位置。 这时的 prev11 中为 6 ，即串 abce abcf abcg 的开始位置。 这时的 prev6 中为 1 ，即串 abcd

24、abce abcf abcg 的开始位置。 这时的 prev1 中为 0 。表示链结束了。 我们看到所有头三个字母为 abc 的串，被链在了一起，从 head 可以一直找下去，直到找到 0 。 链的建立： gzip 在每次处理当前串的时候，首先用当前串的前三个字节计算出 ins_h ，然后，就要把当前的串也插入 到相应的链中， 也就是把当前的串的位置， 保存到 headins_h 中， 而此时， headins_h 中（不空的话） 为前一个串的开始位置。所以这时候需要把前一个串的位置，也就是原来的 headins_h 放入链中。于是 把现在的 headins_h 的值，用当前串的位置做索引，保

25、存到 prev 中。然后再把 headins_h 赋值为 当前串的位置。 如果当前串的位置为 strstart 的话，那么也就是 prevstrstart = headins_h; headins_h = strstart; 就这样，每次把一个串的位置加入到链中，链就形成了。 现在我们也就知道了，前三个字节计算得到同一 ins_h 的所有的串被链在了一起， headins_h 为链头， prev 数组中放着的更早的串的位置。 head 数组和 prev 数组的名字，也正反应了他们的作用。 链的特点： 越向前（ prev ）与当前处理位置之间的距离越大。比如，当前处理串，算出了 ins_h ，而

26、且 headins_h 中的值不空，那么 headins_h 就是离当前处理串距离最近的一个可能的匹配串，并且顺着 prev 向前所 找到的串，越来距离越远。 匹配串中的字节开始的串的插入： 我们说过了，所有字节开始的串，都将被插入“字典”。对于确定了的匹配串，匹配串中的每个字节开始 的串，仍要被插入“字典”，以便后面串可以和他们进行匹配。 注意： 对于文件中的第 0字节，情况很特殊，它开始的串的位置为0。所以第 0串的前三个字节计算出 ins_h 之后， 在 headins_h 中保存的位置为 0。而对是否有可能有匹配的判断，就是通过headins_h 不为 0，并且 headins_h 的

27、值为一个串的开始位置。所以第 0字节开始的串，由于其特殊性，将不会被用来匹配，不过 这种情况只会出现在第 0个字节，所以通常不会造成影响，即使影响，也会极小。 例如，文件内容为 jiurl jiurl 找到的匹配情况如下， 所括部分 jiurl jiurl 2.2 懒惰啊匹配( lazy match ) 对于当前字节开始的串，寻找到了最长匹配之后， gzip 并不立即决定使用这个串进行替换。而是看看这个 匹配长度是否满意， 如果匹配长度不满意， 而下一个字节开始的串也有匹配串的话， 那么 gzip 就找到下一 个字节开始的串的最长匹配，看看是不是比现在这个长。这叫懒惰啊匹配。如果比现在这个长的

28、话，将不 使用现在的这个匹配。如果比现在这个短的话，将确定使用现在的这个匹配。 我们来举个例子，串 0abc bcde abcde 处理到第 10字节时，也就是 abcde 的 a 时，找到最长匹配的情况如下， 所括部分。 0abc bcde abcde 这时，再看看下一个字节，也就是第11字节的情况，也就是abcde的b，找到最长匹配的情况如下，所 括部分。 0abc bcde abcde 发现第二次匹配的匹配长度大，就不使用第一次的匹配串。我们也看到了如果使用第一次匹配的话，将错 过更长的匹配串。 在满足懒惰啊匹配的前提条件下，懒惰啊匹配不限制次数，一次懒惰啊匹配发现了更长的匹配串之后，仍

29、 会再进行懒惰啊匹配，如果这次懒匹配，发现了更长的匹配串，那么上一次的懒匹配找到的匹配串就不用 了。 进行懒惰啊匹配是有条件的。进行懒惰啊匹配必须满足两个条件，第一，下一个处理字节开始的串，要有 匹配串，如果下一个处理字节开始的串没有匹配串的话，那么就确定使用当前的匹配串，不进行懒匹配。 第二，当前匹配串的匹配长度， gzip 不满意，也就是当前匹配长度小于 max_lazy_match (max_lazy_match 在固定的压缩级别下，有固定的值) 。 讨论： 我们可以看到了做另外一次尝试的原因。如果当前串有匹配就使用了的话，可能错过更长匹配的机会。使 用懒惰啊匹配会有所改善。 不过从我简

30、单的分析来看，使用懒惰啊匹配对压缩率的改善似乎是非常有限的。 2.3大于64KB的文件，窗口的实现 窗口的实现： 实际中，当前串（当前处理字节开始的串）只是在它之前的窗口中寻找匹配串的，也就是说只是在它之前 的一定大小的范围内寻找匹配串的。有这个限制的原因，将在后面说明。 gzip 的窗口大小为 WSIZE， 32KB。 内存中有一个叫 window的缓冲区，大小为2个窗口的大小，也就是64KB文件的内容将被读到这个window 中，我们在window上进行LZ77部分的处理，得到结果将放在其他缓冲区中。 gzip 对 window 中的内容，从开始处开始，一个字节一个字节的向后处理。有一个指

31、针叫strstart （其 实是个索引），指向当前处理字节，当当前处理字节开始的串没有匹配时，不做改动的输出当前处理字节， strstart 向后移动一个字节。当当前处理字节开始的串找到了匹配时，输出（匹配长度，相隔距离）对， strstart 向后移动匹配长度个字节。我们把 strstart 到 window 结束的这部分内容，叫做 lookahead buffer ，超前查看缓冲区。这样叫的原因是，在我们处理当前字节的时候，就需要读出之后的字节来进行 串的匹配。在一个变量 lookahead 中，保存着超前查看缓冲区所剩的字节数。 lookahead ，最开始被初始化 为整个读入内容的大小

32、，随着处理的进行， strstart 不断后移，超前查看缓冲区不断减小， lookahead 的 值也不断的减小。 我们需要限制查找匹配串的范围为一个窗口的大小 （这么做的原因后面说明） ，也就是说，只能在当前处理 字节之前的32KB的范围内寻找匹配串。而，由于处理是在2个窗口大小，也就是64KB大小的缓冲区中进行 的，所以匹配链上的串与当前串之间的距离是很有可能超过32KB的。那么gzip是如何来实现这个限制的 呢？ gzip 通过匹配时的判断条件来实现这个限制。当当前串计算 ins_h ，发现 headins_h 值不为空时 （headins_h 为一个串的开始位置） ，说明当前串有可能有

33、匹配串，把这个值保存在 hash_head 中。这时 就要做一个限制范围的判断， strstart - hash_head = 窗口大小， strstart-hash_head 是当前串和最近 的匹配串之间的距离， （注意前面说过，链头和当前串的距离最近，越向前（ prev ）与当前处理位置之间的 距离越大），也就是说要判断当前串和距离最近的匹配串之间的距离是否在一个窗口的范围之内。如果不是 的话，那么链上的其他串肯定更远，肯定更不在一个窗口的范围之内，就不进行匹配处理了。如果是在一 个窗口的范围之内的话，还需要在链上寻找最长的匹配串，在和每个串进行比较的时候，也需要判断当前 串和该串的距离是

34、否超过一个窗口的范围，超过的话，就不能进行匹配。 实际中， gzip 为了使代码简单点，距离限制要比一个窗口的大小还要小一点。 小于64KB的文件： 初始化的时候，会首先从文件中读64KB的内容到window中。对于小于64KB的文件，整个文件都被读入 到window中。在window上进行LZ77的处理，从开始直到文件结束。 大于64KB的文件： 每处理一个字节都要判断lookahead MIN_LOOKAHEAD，也就是 window中还没有处理的字节是否还够 MIN_LOOKAHEA，D 如果不够的话，就会导致 fill_window（） ，从文件中读内容到 window 中。由于我们一

35、 次最大可能使用的超前查看缓冲区的大小为，最大匹配长度(258个字节，后面进行说明)加上最小匹配长 度，也就是下一个处理字节开始的串，可以找到一个最大匹配长度的匹配，发生匹配之后，还要预读一个 最小匹配长度来计算之后的 ins_h 。 不管是大于64KB的文件，还是小于64KB的文件，随着处理的进行，最终都要到文件的结束，在接近文件结 束的时候，都会出现lookahead MIN_LOOKAHEAD对于这种情况，fill_window()读文件，就再读不出 文件内容了，于是 fill_window() 会设置一个标志 eofile ，表示文件就要结束了，之后肯定会接着遇到 lookahead

36、MIN_LOOKAHEAD ，不过由于设置了 eofile 标志，就不会再去试图读文件到 window 中了。 压缩开始之前的初始化，会从文件中读入64KB的内容到window中，窗口大小为32KB,也就是读入2窗的 内容到window中。我们把第一窗的内容叫做w1_32k，第二窗的内容叫做 w2_32k 压缩不断进行，直到lookahead MIN_LOOKAHEAD,也就是处理到了 64KB内容的接近结束部分，也就是如 果再处理，超前查看缓冲区中的内容就可能不够了。由于 lookahead MIN_LOOKAHEAD ，将执行 fill_window() 。 fill_window() 判

37、断是否压缩已经进行到了 2窗内容快用完了，该把新的内容放进来了。如果是的话， fill_window() 把第二窗的内容 w2_32k ，复制到第一窗中，第一窗中的内容就被覆盖掉了，然后对 match_start,strstart 之类的索引，做修正。 然后更新匹配链的链头数组，head，从头到尾过一遍，如果这个头中保存的串的位置，在w2_32k中，就 对这个串的位置做修正。 如果这个头中保存的串的位置，在w1_32k中，就不要了，设为空，因为第一窗的内容我们已经覆盖掉了。 然后更新prev数组，从头到尾过一遍，如果某项的内容，在w2_32k中，就做修正。如果这项的内容， 在 w1_32k 中

38、，就不要了，设为空，因为第一窗的内容我们已经覆盖掉了。 最后fill_window()从文件中再读出一窗内容，也就是读出32KB的内容，复制到第二个窗中，注意第二个 窗口中原来的内容，已经被复制到了第一个窗口中。 就这样，一窗窗的处理，直到整个文件结束。 分析： 到第二窗文件内容也快要处理完的时候，才会从文件中读入新的内容。而这时，第一窗中的所有串，对于 当前处理字节和之后的字节来说，已经超出了一个窗口的距离，当前处理字节和之后的字节不能和第一窗 的串进行匹配了，也就是说第一窗的内容已经没有用了。所有插入字典的第一窗的串也已经没有用了。所 以覆盖第一窗的内容是合理的，将字典中第一窗的串的开始位

39、置都设为空也是合理的。 将第二窗的内容复制到第一窗中，那么第二窗在字典中的所有索引都需要做相应的修正。 由于第二窗的内容已经复制到了第一窗中， 所以我们可以将新的内容读入到第二窗中， 新的内容之前的 32KB 的内容，就是原来的第二窗中的内容。而这时，做过修正的字典中，仍然有原来第二窗中所有串的信息， 也就是说，新的内容，可以继续利用前面一个窗口大小的范围之内的串，进行压缩，这也是合理的。 2.4 其他问题 1 现在来说明一下，为什么最小匹配长度为3个字节。这是由于， gzip 中， （匹配长度，相隔距离 ）对中， 匹配长度的范围为3-258，也就是256种可能值，需要8bit来保存。相隔距离

40、的范围为0-32K，需要15bit 来保存。所以一个 （匹配长度，相隔距离 ）对需要23位，差一位 3个字节。如果匹配串小于 3个字节的话，使 用（ 匹配长度，相隔距离 ）对进行替换，不但没有压缩，反而还会增大。所以保存 （匹配长度，相隔距离 ） 对 所需要的位数，决定了最小匹配长度至少要为3个字节。 最大匹配长度为 258的原因是，综合各种因素，决定用 8位来保存匹配长度，8位的最大值为 255。实际中， 我们在 （ 匹配长度，相隔距离 ）对中的“匹配长度”保存的是，实际匹配长度-最小匹配长度，所以 255对应 的实际匹配长度为 258。 在进行匹配时，会对匹配长度进行判断，保证到达最大匹配

41、长度时，匹配就停止。也就是说，即使有两个 串的相同部分超过了最大匹配长度，也只匹配到最大匹配长度。 保存相隔距离所用的位数和窗口大小是互相决定的，综合两方面各种因素，确定了窗口大小，也就确定了 保存相隔距离所使用的位数。 2.5 gzip 的 LZ77 部分的实现要点 gzip 的 LZ77 部分的实现主要在函数 defalte（） 中。 所使用的缓冲区 window 用来放文件中读入的内容。 l_buf ，d_buf , flag_buf 用来放 LZ77压缩得到的结果。 l_buf 中的每个字节是一个没有匹配的字节，或者是一个匹配的对中的匹配长度-3。 l_buf 共用了 inbuf 。

42、d_buf 中的每个 unsigned short ，是一个匹配的对中的相隔距离。 flag_buf 中每位是一个标志，用来指示 l_buf 中相应字节是没有匹配的字节，还是一个匹配的对中的 匹配长度 -3。 prev ， head 用来存放字典信息。实际上 head 为宏定义 prev+WSIZE 。 初始化过程中，调用 lm_init（） 。 lm_init（） 中，从输入文件中读入 2个窗口大小，也就是 64KB的内容到 window中。lookahead 中为返回 的读入字节数。使用 window中的头两个字节，UPDATE_HASH初始化ins_h。 deflate（）中，一个处理循

43、环中，首先 INSERT_STRING把当前串插入字典，INSERT_STRING是一个宏，作 用就是用哈希函数计算当前串的 ins_h ，然后把原来的 headins_h 中的内容，链入链中（放到 prev 中）， 同时把原来的 headins_h 保存在 hash_head 变量中，用来后面进行匹配判断，然后把当前串的开始位置， 保存在 headins_h 中。 判断hash_head中保存的内容不为空，说明匹配链上有内容。调用longest_match （）寻找匹配链上的最 长匹配。 hash_head 中保存的内容为空，说明当前字节开始的串，在窗口中没有匹配。 由于使用了 lazy m

44、atch ，使得判断的情况更复杂。 匹配串的输出，或者是没有匹配的字节的输出，都是调用函数 ct_tally() 。 对于匹配串，输出之后，还需要为匹配串中的每个字节使用INSERT_STRING把匹配串中每个字节开始的 串都插入到字典中。 ct_tally() 中，把传入的 没有匹配的字节 或者是匹配长度 -3 放到 l_buf 中，然后为以后的 Huffman 编码做统计次数的工作， 如果传入的是匹配情况， 传入的参数中会有相隔距离， 把相隔距离保存在 d_buf 中。根据传入的参数，可以判断是哪种情况，然后设置一个变量中相应的标志位，每8个标志位，也就是够 一个字节，就保存到 flag_

45、buf 中。还有一些判断，我们将在后面进行说明。 2.6 分块输出 LZ77 压缩的结果放在， l_buf ， d_buf ， flag_buf 中。 对于LZ77的压缩结果，可能使用一块输出或者分成多块输出(LZ77压缩一定的部分之后，就进行一次块 输出，输出一块) 。块的大小不固定。 输出的时候，会对LZ77的压缩结果，进行Huffman编码，最终把Huffman编码的结果输出到 outbuf缓冲 区中。 进行 Huffman 编码，并输出的工作，在 flush_block() 中进行。 在ct_tally()中进行判断，如果满足一些条件的话，当从ct_tally()中返回之后，就会对现有

46、的LZ77的 结果，进行 Huffman 编码，输出到一个块中。 在整个文件处理结束，deflate。函数要结束的时候，会把LZ77的结果，进行Huffman编码，输出到一个 块中。 在 ct_tally() 中，每当 l_buf 中的字节数(每个字节是一个没有匹配的字节或者一个匹配长度)增加 0 x1000,也就是4096的时候。将估算压缩的情况，以判断现在结束这个块是否比较好，如果觉得比较好， 就输出一个块。如果觉得不好，就先不输出。 而当l_buf满了的时候，或者 d_buf满了的时候，将肯定对现有的LZ77压缩的结果，进行 Huffman编 码，输出到一个块中。 决定输出一块的话， 会

47、只针对这一块的内容， 建立 Huffman 树，这一块内容将会被进行 Huffman 编码压缩， 并被输出到 outbuf 中。如果是动态 Huffman 编码，树的信息也被输出到 outbuf 中。输出之后，会调用 init_block() ，初始化一个新块，重新初始化一些变量，包括动态树的结点被置 0，也就是说，将为新块将 来的 Huffman 树重新开始统计信息。 输出块的大小是不固定的，首先在进行 Huffman 编码之前，要输出的内容的大小就是不固定，要看情况， 进行 Huffman 编码之后，就更不固定了。 块的大小不固定，那么解压缩的时候，如何区分块呢。编码树中有一个表示块结束的

48、结点，EOB在每次输 出块的最后，输出这个结点的编码，所以解压缩的时候，当遇到了这个结点就表明一个块结束了。 每个块最开始的 2位，用来指明本块使用的是哪种编码方式， 00表示直接存储， 01表示静态 Huffman 编码， 10表示动态 Huffman 编码。接下来的 1位，指明本块是否是最后一块， 0 表示不是， 1表示是最后一块。 输出一个块，对现在字典中的内容没有影响，下一个块，仍将用之前形成的字典，进行匹配。 2.7 静态 Huffman 编码与动态 Huffman 编码 静态 Huffman 编码就是使用 gzip 自己预先定义好了一套编码进行压缩， 解压缩的时候也使用这套编码，

49、这 样不需要传递用来生成树的信息。 动态 Huffman 编码就是使用统计好的各个符号的出现次数，建立 Huffman 树，产生各个符号的 Huffman 编 码，用这产生的 Huffman 编码进行压缩，这样需要传递生成树的信息。 gzip 在为一块进行 Huffman 编码之前， 会同时建立静态 Huffman 树，和动态 Huffman 树， 然后根据要输出 的内容和生成的 Huffman 树，计算使用静态 Huffman 树编码， 生成的块的大小， 以及计算使用动态 Huffman 树编码，生成块的大小。然后进行比较，使用生成块较小的方法进行 Huffman 编码。 对于静态树来说，不需要传递用来生成树的那部分信息。动态树需要传递这个信息。而当文件比较小的时 候，传递生成树的信息得不