几种压缩算法实现原理详解

小灰灰 2022-08-08 11:51 189阅读 0赞

gzip 、zlib以及图形格式png，使用的压缩算法都是deflate算法。从gzip的源码中，我们了解到了defalte算法的原理和实现。我阅读的gzip版本为 gzip-1.2.4。下面我们将要对deflate算法做一个分析和说明。首先简单介绍一下基本原理，然后详细的介绍实现。  
  
**1 gzip 所使用压缩算法的基本原理**  
  
gzip 对于要压缩的文件，首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用Huffman编码的方法（实际上gzip根据情况，选择使用静态Huffman编码或者动态Huffman编码，详细内容在实现中说明）进行压缩。所以明白了LZ77算法和Huffman编码的压缩原理，也就明白了gzip的压缩原理。我们来对LZ77算法和Huffman编码做一个简单介绍。  
  
1.1 LZ77算法简介  
  
这一算法是由Jacob Ziv 和 Abraham Lempel 于 1977 年提出，所以命名为 LZ77。  
  
1.1.1 LZ77算法的压缩原理  
  
如果文件中有两块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后一块的内容。所以我们可以用（两者之间的距离，相同内容的长度）这样一对信息，来替换后一块内容。由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。  
  
下面我们来举一个例子。  
  
有一个文件的内容如下  
http://jiurl.yeah.net http://jiurl.nease.net  
  
其中有些部分的内容，前面已经出现过了，下面用()括起来的部分就是相同的部分。  
http://jiurl.yeah.net (http://jiurl.)nease(.net)  
  
我们使用 (两者之间的距离，相同内容的长度) 这样一对信息，来替换后一块内容。  
http://jiurl.yeah.net (22,13)nease(23,4)  
  
(22,13)中，22为相同内容块与当前位置之间的距离，13为相同内容的长度。  
(23,4)中，23为相同内容块与当前位置之间的距离，4为相同内容的长度。  
由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。  
  
1.1.2 LZ77使用滑动窗口寻找匹配串  
  
LZ77算法使用"滑动窗口"的方法，来寻找文件中的相同部分，也就是匹配串。我们先对这里的串做一个说明，它是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化。  
  
LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节），随着处理的字节不断的向后滑动，就象在阳光下，飞机的影子滑过大地一样。对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指，窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串，就用(之间的距离，匹配长度) 这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。  
  
处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任何内容，被处理的字节就会不做改动的输出。随着处理的不断向后，窗口越来越多的滑入文件，最后整个窗口滑入文件，然后整个窗口在文件上向后滑动，直到整个文件结束。  
  
1.1.3 使用LZ77算法进行压缩和解压缩  
  
为了在解压缩时，可以区分“没有匹配的字节”和“（之间的距离，匹配长度）对”，我们还需要在每个“没有匹配的字节”或者“（之间的距离，匹配长度）对”之前，放上一位，来指明是“没有匹配的字节”，还是“（之间的距离，匹配长度）对”。我们用0表示“没有匹配的字节”，用1表示“（之间的距离，匹配长度）对”。  
  
实际中，我们将固定（之间的距离，匹配长度）对中的，“之间的距离”和“匹配长度”所使用的位数。由于我们要固定“之间的距离”所使用的位数，所以我们才使用了固定大小的窗口，比如窗口的大小为32KB，那么用15位（2^15=32K）就可以保存0-32K范围的任何一个值。实际中，我们还将限定最大的匹配长度，这样一来，“匹配长度”所使用的位数也就固定了。  
  
实际中，我们还将设定一个最小匹配长度，只有当两个串的匹配长度大于最小匹配长度时，我们才认为是一个匹配。我们举一个例子来说明这样做的原因。比如，“距离”使用15位，“长度”使用8位，那么“（之间的距离，匹配长度）对”将使用23位，也就是差1位3个字节。如果匹配长度小于3个字节的话，那么用“（之间的距离，匹配长度）对”进行替换的话，不但没有压缩，反而会增大，所以需要一个最小匹配长度。  
  
压缩：  
从文件的开始到文件结束，一个字节一个字节的向后进行处理。用当前处理字节开始的串，和滑动窗口中的每个串进行匹配，寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串，就先输出一个标志位，表明下面是一个(之间的距离，匹配长度) 对，然后输出(之间的距离，匹配长度) 对，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就先输出一个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，然后继续处理当前处理字节的下一个字节。  
  
解压缩：  
从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个(之间的距离，匹配长度) 对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。  
  
我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。  
  
  
1.2 Huffman编码简介  
1.2.1 Huffman编码的压缩原理  
  
我们把文件中一定位长的值看作是符号，比如把8位长的256种值，也就是字节的256种值看作是符号。我们根据这些符号在文件中出现的频率，对这些符号重新编码。对于出现次数非常多的，我们用较少的位来表示，对于出现次数非常少的，我们用较多的位来表示。这样一来，文件的一些部分位数变少了，一些部分位数变多了，由于变小的部分比变大的部分多，所以整个文件的大小还是会减小，所以文件得到了压缩。  
  
1.2.2 Huffman编码使用Huffman树来产生编码  
  
要进行Huffman编码，首先要把整个文件读一遍，在读的过程中，统计每个符号（我们把字节的256种值看作是256种符号）的出现次数。然后根据符号的出现次数，建立Huffman树，通过Huffman树得到每个符号的新的编码。对于文件中出现次数较多的符号，它的Huffman编码的位数比较少。对于文件中出现次数较少的符号，它的Huffman编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。  
  
建立Huffman树：  
把所有符号看成是一个结点，并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树。  
  
每次从所有树中找出值最小的两个树，为这两个树建立一个父结点，然后这两个树和它们的父结点组成一个新的树，这个新的树的值为它的两个子树的值的和。如此往复，直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树。  
  
通过Huffman树得到Huffman编码：  
  
这棵Huffman树，是一棵二叉树，它的所有叶子结点就是所有的符号，它的中间结点是在产生Huffman树的过程中不断建立的。我们在Huffman树的所有父结点到它的左子结点的路径上标上0，右子结点的路径上标上1。  
  
现在我们从根节点开始，到所有叶子结点的路径，就是一个0和1的序列。我们用根结点到一个叶子结点路径上的0和1的序列，作为这个叶子结点的Huffman编码。  
  
我们来看一个例子。  
  
有一个文件的内容如下  
abbbbccccddde  
  
我们统计一下各个符号的出现次数，  
a b c d e  
1 4 4 3 1  
  
建立Huffman树的过程如图：

![2011092909392629.jpg][]

通过最终的Huffman树，我们可以得到每个符号的Huffman编码。  
  
a 为 110  
b 为 00  
c 为 01  
d 为 10  
e 为 111  
  
我们可以看到，Huffman树的建立方法就保证了，出现次数多的符号，得到的Huffman编码位数少，出现次数少的符号，得到的Huffman编码位数多。  
  
各个符号的Huffman编码的长度不一，也就是变长编码。对于变长编码，可能会遇到一个问题，就是重新编码的文件中可能会无法如区分这些编码。  
比如，a的编码为000，b的编码为0001，c的编码为1，那么当遇到0001时，就不知道0001代表ac，还是代表b。出现这种问题的原因是a的编码是b的编码的前缀。  
由于Huffman编码为根结点到叶子结点路径上的0和1的序列，而一个叶子结点的路径不可能是另一个叶子结点路径的前缀，所以一个Huffman编码不可能为另一个Huffman编码的前缀，这就保证了Huffman编码是可以区分的。  
  
1.2.3 使用Huffman编码进行压缩和解压缩  
  
为了在解压缩的时候，得到压缩时所使用的Huffman树，我们需要在压缩文件中，保存树的信息，也就是保存每个符号的出现次数的信息。  
  
压缩：  
  
读文件，统计每个符号的出现次数。根据每个符号的出现次数，建立Huffman树，得到每个符号的Huffman编码。将每个符号的出现次数的信息保存在压缩文件中，将文件中的每个符号替换成它的Huffman编码，并输出。  
  
解压缩：  
  
得到保存在压缩文件中的，每个符号的出现次数的信息。根据每个符号的出现次数，建立Huffman树，得到每个符号的Huffman编码。将压缩文件中的每个Huffman编码替换成它对应的符号，并输出。  
  
**2 gzip 所使用压缩算法的实现**  
  
我们将gzip的实现分成很多个部分，一个个来说明，这样做的原因见本文最后一部分。  
gzip 中所使用的各种实现技巧的出处或者灵感，gzip 的作者在源码的注释中进行了说明。  
  
2.1 寻找匹配串的实现  
  
为一个串寻找匹配串需要进行大量的匹配工作，而且我们还需要为很多很多个串寻找匹配串。所以 gzip 在寻找匹配串的实现中使用哈希表来提高速度。  
  
要达到的目标是，对于当前串，我们要在它之前的窗口中，寻找每一个匹配长度达到最小匹配的串，并找出匹配长度最长的串。  
  
在 gzip 中，最小匹配长度为3，也就是说，两个串，最少要前3个字节相同，才能算作匹配。为什么最小匹配长度为3，将在后面说明。  
  
gzip 对遇到的每一个串，首先会把它插入到一个“字典”中。这样当以后有和它匹配的串，可以直接从“字典”中查出这个串。  
  
插入的时候，使用这个插入串的前三个字节，计算出插入的“字典”位置，然后把插入串的开始位置保存在这个“字典”位置中。查出的时候，使用查出串的前三个字节，计算出“字典”位置，由于插入和查出使用的是同一种计算方法，所以如果两个串的前三个字节相同的话，计算出的“字典”位置肯定是相同的，所以就可以直接在该“字典”位置中，取出以前插入时，保存进去的那个串的开始位置。于是查出串，就找到了一个串，而这个串的前三个字节和自己的一样（其实只是有极大的可能是一样的，原因后面说明），所以就找到了一个匹配串。  
  
如果有多个串，他们的前三个字节都相同，那么他们的“字典”位置，也都是相同的，他们将被链成一条链，放在那个“字典”位置上。所以，如果一个串，查到了一个“字典”位置，也就查到了一个链，所有和它前三个字节相同的串，都在这个链上。  
  
也就是说，当前串之前的所有匹配串被链在了一个链上，放在某个“字典”位置上。而当前串使用它的前三个字节，进行某种计算，就可以得到这个“字典”位置（得到了“字典”位置之后，它首先也把自己链入到这个链上），也就找到了链有它的所有匹配串的链，所以要找最长的匹配，也就是遍历这个链上的每一个串，看和哪个串的匹配长度最大。  
  
下面我们更具体的说明，寻找匹配串的实现。  
  
我们前面所说的“字典”，是一个数组，叫做head\[\]（为什么叫head,后面进行说明）。  
我们前面所说的“字典”位置，放在一个叫做ins\_h的变量中。  
我们前面所说的链，是在一个叫做prev\[\]的数组中。  
  
插入：  
  
当前字节为第 strstart 个字节。通过第strstart,strstart+1,strstart+2,这三个字节，使用一个设计好的哈希函数算出ins\_h，也就是插入的位置。然后将当前字节的位置，即strstart，保存在head\[ins\_h\]中。  
注意由 strstart,strstart+1,strstart+2,这三个字节（也就是strstart开始处的串的头三个字节，也就是当前字节和之后的两个字节）确定了ins\_h。head\[ins\_h\]中保存的又是strstart，也就是这个串开始的位置。  
  
判断是否有匹配：  
  
当前串的前三个字节，使用哈希函数算出ins\_h，这时如果head\[ins\_h\]的值不为空的话，那么head\[ins\_h\]中的值，便是之前保存在这里的另一个串的位置，并且这个串的前三个字节算出的ins\_h，和当前串的前三个字节算出的ins\_h相同。也就是说有可能有匹配。如果head\[ins\_h\]的值为空的话，那么肯定没有匹配。  
  
gzip所使用的哈希函数：  
  
gzip 所使用的哈希函数，用三个字节来计算一个ins\_h，这是由于最小匹配为三个字节。  
  
对于相同的三个字节，通过哈希函数得到的ins\_h必然是相同的。  
而不同的三个字节，通过哈希函数有可能得到同一个ins\_h，不过这并不要紧，  
当gzip发现head\[ins\_h\]不空后，也就是说有可能有匹配串的话，会对链上的每一个串进行真正的串的比较。  
  
所以一个链上的串，只是前三个字节用哈希函数算出的值相同，而并不一定前三个字节都是相同的。但是这样已经很大的缩小了需要进行串比较的范围。  
  
我们来强调一下，前三个字节相同的串，必然在同一个链上。在同一个链上的，不一定前三个字节都相同。  
  
不同的三个字节有可能得到同一个结果的原因是，三个字节，一共24位，有2^24种可能值。而三个字节的哈希函数的计算结果为15位，有2^15种可能值。也就是说2^24种值，与2^15种值进行对应，必然是多对一的，也就是说，必然是有多种三个字节的值，用这个哈希函数计算出的值都是相同的。  
  
而我们使用哈希函数的理由是，实际上，我们只是在一个窗口大小的范围内（后面将会看到）寻找匹配串，一个窗口的大小范围是很有限的，能出现的三个字节的值组合情况也是很有限的，将远远小于2^24，使用合适的哈希函数是高效的。  
  
前三个字节相同的所有的串所在的链：  
  
head\[ins\_h\] 中的值，有两个作用。一个作用，是一个前三个字节计算结果为ins\_h的串的位置。另一个作用，是一个在prev\[\]数组中的索引，用这个索引在prev\[\]中，将找到前一个前三个字节计算结果为ins\_h的串的位置。即prev\[head\[ins\_h\]\]的值（不为空的话）为前一个前三个字节计算结果为ins\_h的串的位置。  
  
prev\[\]的值，也有两个作用。一个作用，是一个前三个字节计算结果为ins\_h的串的位置。另一个作用，是一个在prev\[\]数组中的索引，用这个索引在prev\[\]中，将找到前一个前三个字节计算结果为ins\_h的串的位子哈。即prev\[\]的值（不为空的话）为前一个三个字节计算结果为ins\_h的串的位置。  
  
直到prev\[\]为空，表示链结束。  
  
我们来举一个例子，串，  
0abcd abce,abcf\_abcg  
  
当处理到abcg的a时，由abcg的abc算出ins\_h。  
这时的head\[ins\_h\]中为 11，即串"abcf abcg"的开始位置。  
这时的prev\[11\]中为 6，即串"abce abcf abcg"的开始位置。  
这时的prev\[6\]中为 1，即串"abcd abce abcf abcg"的开始位置。  
这时的prev\[1\]中为 0。表示链结束了。  
  
我们看到所有头三个字母为abc的串，被链在了一起，从head可以一直找下去，直到找到0。  
  
链的建立：  
  
gzip在每次处理当前串的时候，首先用当前串的前三个字节计算出ins\_h，然后，就要把当前的串也插入到相应的链中，也就是把当前的串的位置，保存到 head\[ins\_h\] 中，而此时，head\[ins\_h\] 中（不空的话）为前一个串的开始位置。所以这时候需要把前一个串的位置，也就是原来的head\[ins\_h\]放入链中。于是把现在的head\[ins\_h\]的值，用当前串的位置做索引，保存到 prev\[\] 中。然后再把 head\[ins\_h\]赋值为当前串的位置。  
  
如果当前串的位置为strstart的话，那么也就是  
prev\[strstart\] = head\[ins\_h\];  
head\[ins\_h\] = strstart;  
  
就这样，每次把一个串的位置加入到链中，链就形成了。  
  
现在我们也就知道了，前三个字节计算得到同一ins\_h的所有的串被链在了一起，head\[ins\_h\]为链头，prev\[\]数组中放着的更早的串的位置。head数组和prev数组的名字，也正反应了他们的作用。  
  
链的特点：  
  
越向前（prev）与当前处理位置之间的距离越大。比如，当前处理串，算出了ins\_h，而且head\[ins\_h\]中的值不空，那么head\[ins\_h\]就是离当前处理串距离最近的一个可能的匹配串，并且顺着prev\[\]向前所找到的串，越来距离越远。  
  
匹配串中的字节开始的串的插入：  
  
我们说过了，所有字节开始的串，都将被插入“字典”。对于确定了的匹配串，匹配串中的每个字节开始的串，仍要被插入“字典”，以便后面串可以和他们进行匹配。  
  
注意：  
  
对于文件中的第0字节，情况很特殊，它开始的串的位置为0。所以第0串的前三个字节计算出ins\_h之后，在head\[ins\_h\]中保存的位置为0。而对是否有可能有匹配的判断，就是通过head\[ins\_h\]不为0，并且head\[ins\_h\]的值为一个串的开始位置。所以第0字节开始的串，由于其特殊性，将不会被用来匹配，不过这种情况只会出现在第0个字节，所以通常不会造成影响，即使影响，也会极小。  
  
例如，文件内容为  
jiurl jiurl  
  
找到的匹配情况如下，\[\]所括部分。  
  
jiurl j\[iurl\]  
  
2.2 懒惰啊匹配（lazy match）  
  
对于当前字节开始的串，寻找到了最长匹配之后，gzip并不立即决定使用这个串进行替换。而是看看这个匹配长度是否满意，如果匹配长度不满意，而下一个字节开始的串也有匹配串的话，那么gzip就找到下一个字节开始的串的最长匹配，看看是不是比现在这个长。这叫懒惰啊匹配。如果比现在这个长的话，将不使用现在的这个匹配。如果比现在这个短的话，将确定使用现在的这个匹配。  
  
我们来举个例子，串  
  
0abc bcde abcde  
  
处理到第10字节时，也就是"abcde"的a时，找到最长匹配的情况如下，\[\]所括部分。  
  
0abc bcde \[abc\]de  
  
这时，再看看下一个字节，也就是第11字节的情况，也就是'abcde"的b，找到最长匹配的情况如下，\[\]所括部分。  
  
0abc bcde a\[bcde\]  
  
发现第二次匹配的匹配长度大，就不使用第一次的匹配串。我们也看到了如果使用第一次匹配的话，将错过更长的匹配串。  
  
在满足懒惰啊匹配的前提条件下，懒惰啊匹配不限制次数，一次懒惰啊匹配发现了更长的匹配串之后，仍会再进行懒惰啊匹配，如果这次懒匹配，发现了更长的匹配串，那么上一次的懒匹配找到的匹配串就不用了。  
  
进行懒惰啊匹配是有条件的。进行懒惰啊匹配必须满足两个条件，第一，下一个处理字节开始的串，要有匹配串，如果下一个处理字节开始的串没有匹配串的话，那么就确定使用当前的匹配串，不进行懒匹配。第二，当前匹配串的匹配长度，gzip不满意，也就是当前匹配长度小于max\_lazy\_match（max\_lazy\_match在固定的压缩级别下，有固定的值）。  
  
讨论：  
  
我们可以看到了做另外一次尝试的原因。如果当前串有匹配就使用了的话，可能错过更长匹配的机会。使用懒惰啊匹配会有所改善。  
不过从我简单的分析来看，使用懒惰啊匹配对压缩率的改善似乎是非常有限的。  
2.3 大于64KB的文件，窗口的实现  
  
窗口的实现：  
  
实际中，当前串（当前处理字节开始的串）只是在它之前的窗口中寻找匹配串的，也就是说只是在它之前的一定大小的范围内寻找匹配串的。有这个限制的原因，将在后面说明。  
  
gzip 的窗口大小为 WSIZE，32KB。  
  
内存中有一个叫window\[\]的缓冲区，大小为2个窗口的大小，也就是64KB。文件的内容将被读到这个window\[\]中，我们在window\[\]上进行LZ77部分的处理，得到结果将放在其他缓冲区中。  
  
gzip 对window\[\]中的内容，从开始处开始，一个字节一个字节的向后处理。有一个指针叫strstart（其实是个索引），指向当前处理字节，当当前处理字节开始的串没有匹配时，不做改动的输出当前处理字节，strstart向后移动一个字节。当当前处理字节开始的串找到了匹配时，输出（匹配长度，相隔距离）对，strstart向后移动匹配长度个字节。我们把strstart到window\[\]结束的这部分内容，叫做lookahead buffer，超前查看缓冲区。这样叫的原因是，在我们处理当前字节的时候，就需要读出之后的字节来进行串的匹配。在一个变量lookahead中，保存着超前查看缓冲区所剩的字节数。lookahead，最开始被初始化为整个读入内容的大小，随着处理的进行，strstart不断后移，超前查看缓冲区不断减小，lookahead的值也不断的减小。  
  
我们需要限制查找匹配串的范围为一个窗口的大小（这么做的原因后面说明），也就是说，只能在当前处理字节之前的32KB的范围内寻找匹配串。而，由于处理是在2个窗口大小，也就是64KB大小的缓冲区中进行的，所以匹配链上的串与当前串之间的距离是很有可能超过32KB的。那么gzip是如何来实现这个限制的呢？  
  
gzip 通过匹配时的判断条件来实现这个限制。当当前串计算ins\_h，发现head\[ins\_h\]值不为空时（head\[ins\_h\]为一个串的开始位置），说明当前串有可能有匹配串，把这个值保存在 hash\_head中。这时就要做一个限制范围的判断，strstart - hash\_head <= 窗口大小，strstart-hash\_head 是当前串和最近的匹配串之间的距离，（注意前面说过，链头和当前串的距离最近，越向前（prev）与当前处理位置之间的距离越大），也就是说要判断当前串和距离最近的匹配串之间的距离是否在一个窗口的范围之内。如果不是的话，那么链上的其他串肯定更远，肯定更不在一个窗口的范围之内，就不进行匹配处理了。如果是在一个窗口的范围之内的话，还需要在链上寻找最长的匹配串，在和每个串进行比较的时候，也需要判断当前串和该串的距离是否超过一个窗口的范围，超过的话，就不能进行匹配。  
  
实际中，gzip为了使代码简单点，距离限制要比一个窗口的大小还要小一点。  
  
小于64KB的文件：  
  
初始化的时候，会首先从文件中读64KB的内容到window\[\]中。对于小于64KB的文件，整个文件都被读入到window\[\]中。在window\[\]上进行LZ77的处理，从开始直到文件结束。  
  
大于64KB的文件：  
  
每处理一个字节都要判断 lookahead < MIN\_LOOKAHEAD ，也就是window中还没有处理的字节是否还够MIN\_LOOKAHEAD ，如果不够的话，就会导致 fill\_window()，从文件中读内容到window\[\]中。由于我们一次最大可能使用的超前查看缓冲区的大小为，最大匹配长度（258个字节，后面进行说明）加上最小匹配长度，也就是下一个处理字节开始的串，可以找到一个最大匹配长度的匹配，发生匹配之后，还要预读一个最小匹配长度来计算之后的ins\_h。  
  
不管是大于64KB的文件，还是小于64KB的文件，随着处理的进行，最终都要到文件的结束，在接近文件结束的时候，都会出现 lookahead < MIN\_LOOKAHEAD ，对于这种情况，fill\_window() 读文件，就再读不出文件内容了，于是fill\_window()会设置一个标志eofile，表示文件就要结束了，之后肯定会接着遇到 lookahead < MIN\_LOOKAHEAD ，不过由于设置了 eofile 标志，就不会再去试图读文件到window\[\]中了。  
压缩开始之前的初始化，会从文件中读入64KB的内容到window\[\]中，窗口大小为32KB，也就是读入2窗的内容到window\[\]中。我们把第一窗的内容叫做w1\_32k，第二窗的内容叫做w2\_32k。  
  
压缩不断进行，直到 lookahead < MIN\_LOOKAHEAD，也就是处理到了64KB内容的接近结束部分，也就是如果再处理，超前查看缓冲区中的内容就可能不够了。由于 lookahead < MIN\_LOOKAHEAD ，将执行 fill\_window()。  
  
fill\_window() 判断是否压缩已经进行到了2窗内容快用完了，该把新的内容放进来了。如果是的话，  
  
fill\_window() 把第二窗的内容 w2\_32k，复制到第一窗中，第一窗中的内容就被覆盖掉了，然后对match\_start,strstart之类的索引，做修正。  
然后更新匹配链的链头数组，head\[\]，从头到尾过一遍，如果这个头中保存的串的位置，在w2\_32k中，就对这个串的位置做修正。  
如果这个头中保存的串的位置，在w1\_32k中，就不要了，设为空，因为第一窗的内容我们已经覆盖掉了。  
然后更新prev\[\]数组，从头到尾过一遍，如果某项的内容，在w2\_32k中，就做修正。如果这项的内容，在w1\_32k中，就不要了，设为空，因为第一窗的内容我们已经覆盖掉了。  
  
最后fill\_window()从文件中再读出一窗内容，也就是读出32KB的内容，复制到第二个窗中，注意第二个窗口中原来的内容，已经被复制到了第一个窗口中。  
  
就这样，一窗窗的处理，直到整个文件结束。  
  
分析：  
  
到第二窗文件内容也快要处理完的时候，才会从文件中读入新的内容。而这时，第一窗中的所有串，对于当前处理字节和之后的字节来说，已经超出了一个窗口的距离，当前处理字节和之后的字节不能和第一窗的串进行匹配了，也就是说第一窗的内容已经没有用了。所有插入字典的第一窗的串也已经没有用了。所以覆盖第一窗的内容是合理的，将字典中第一窗的串的开始位置都设为空也是合理的。  
  
将第二窗的内容复制到第一窗中，那么第二窗在字典中的所有索引都需要做相应的修正。  
  
由于第二窗的内容已经复制到了第一窗中，所以我们可以将新的内容读入到第二窗中，新的内容之前的32KB的内容，就是原来的第二窗中的内容。而这时，做过修正的字典中，仍然有原来第二窗中所有串的信息，也就是说，新的内容，可以继续利用前面一个窗口大小的范围之内的串，进行压缩，这也是合理的。  
  
2.4 其他问题1  
  
现在来说明一下，为什么最小匹配长度为3个字节。这是由于，gzip 中，(匹配长度，相隔距离)对中，"匹配长度"的范围为3-258，也就是256种可能值，需要8bit来保存。"相隔距离"的范围为0-32K，需要15bit来保存。所以一个(匹配长度，相隔距离)对需要23位，差一位3个字节。如果匹配串小于3个字节的话，使用(匹配长度，相隔距离)对进行替换，不但没有压缩，反而还会增大。所以保存(匹配长度，相隔距离)对所需要的位数，决定了最小匹配长度至少要为3个字节。  
  
最大匹配长度为258的原因是，综合各种因素，决定用8位来保存匹配长度，8位的最大值为255。实际中，我们在(匹配长度，相隔距离)对中的“匹配长度”保存的是，实际匹配长度-最小匹配长度，所以255对应的实际匹配长度为258。  
  
在进行匹配时，会对匹配长度进行判断，保证到达最大匹配长度时，匹配就停止。也就是说，即使有两个串的相同部分超过了最大匹配长度，也只匹配到最大匹配长度。  
  
保存相隔距离所用的位数和窗口大小是互相决定的，综合两方面各种因素，确定了窗口大小，也就确定了保存相隔距离所使用的位数。  
  
2.5 gzip 的 LZ77部分的实现要点  
  
gzip 的 LZ77 部分的实现主要在函数 defalte() 中。  
  
所使用的缓冲区  
  
window\[\] 用来放文件中读入的内容。  
  
l\_buf\[\]，d\_buf\[\]，flag\_buf\[\] 用来放LZ77压缩得到的结果。  
l\_buf\[\] 中的每个字节是一个没有匹配的字节，或者是一个匹配的对中的匹配长度-3。l\_buf\[\]共用了inbuf\[\]。  
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() 中，一个处理循环中，首先 INSERT\_STRING 把当前串插入字典，INSERT\_STRING 是一个宏，作用就是用哈希函数计算当前串的ins\_h，然后把原来的head\[ins\_h\]中的内容，链入链中（放到prev中），同时把原来的head\[ins\_h\]保存在hash\_head变量中，用来后面进行匹配判断，然后把当前串的开始位置，保存在head\[ins\_h\]中。  
  
判断hash\_head中保存的内容不为空，说明匹配链上有内容。调用 longest\_match () 寻找匹配链上的最长匹配。  
hash\_head中保存的内容为空，说明当前字节开始的串，在窗口中没有匹配。  
由于使用了lazy match，使得判断的情况更复杂。  
  
匹配串的输出，或者是没有匹配的字节的输出，都是调用函数 ct\_tally()。  
对于匹配串，输出之后，还需要为匹配串中的每个字节使用 INSERT\_STRING，把匹配串中每个字节开始的串都插入到字典中。  
  
ct\_tally()中，把传入的"没有匹配的字节"或者是"匹配长度-3"放到l\_buf\[\]中，然后为以后的Huffman编码做统计次数的工作，如果传入的是匹配情况，传入的参数中会有相隔距离，把相隔距离保存在d\_buf\[\]中。根据传入的参数，可以判断是哪种情况，然后设置一个变量中相应的标志位，每8个标志位，也就是够一个字节，就保存到flag\_buf\[\]中。还有一些判断，我们将在后面进行说明。  
  
2.6 分块输出  
  
LZ77 压缩的结果放在，l\_buf\[\]，d\_buf\[\]，flag\_buf\[\] 中。  
对于 LZ77 的压缩结果，可能使用一块输出或者分成多块输出（LZ77压缩一定的部分之后，就进行一次块输出，输出一块）。块的大小不固定。  
  
输出的时候，会对LZ77的压缩结果，进行Huffman编码，最终把Huffman编码的结果输出到outbuf\[\]缓冲区中。  
进行Huffman编码，并输出的工作，在 flush\_block() 中进行。  
  
在ct\_tally()中进行判断，如果满足一些条件的话，当从ct\_tally()中返回之后，就会对现有的LZ77的结果，进行Huffman编码，输出到一个块中。  
在整个文件处理结束，deflate()函数要结束的时候，会把LZ77的结果，进行Huffman编码，输出到一个块中。  
  
在ct\_tally()中，每当l\_buf\[\]中的字节数（每个字节是一个没有匹配的字节或者一个匹配长度）增加0x1000，也就是4096的时候。将估算压缩的情况，以判断现在结束这个块是否比较好，如果觉得比较好，就输出一个块。如果觉得不好，就先不输出。  
  
而当l\_buf\[\]满了的时候，或者d\_buf\[\]满了的时候，将肯定对现有的LZ77压缩的结果，进行Huffman编码，输出到一个块中。  
  
决定输出一块的话，会只针对这一块的内容，建立Huffman树，这一块内容将会被进行Huffman编码压缩，并被输出到outbuf\[\]中。如果是动态Huffman编码，树的信息也被输出到outbuf\[\]中。输出之后，会调用init\_block()，初始化一个新块，重新初始化一些变量，包括动态树的结点被置0，也就是说，将为新块将来的Huffman树重新开始统计信息。  
  
输出块的大小是不固定的，首先在进行Huffman编码之前，要输出的内容的大小就是不固定，要看情况，进行Huffman编码之后，就更不固定了。  
块的大小不固定，那么解压缩的时候，如何区分块呢。编码树中有一个表示块结束的结点，EOB，在每次输出块的最后，输出这个结点的编码，所以解压缩的时候，当遇到了这个结点就表明一个块结束了。  
  
每个块最开始的2位，用来指明本块使用的是哪种编码方式，00表示直接存储，01表示静态Huffman编码，10表示动态Huffman编码。接下来的1位，指明本块是否是最后一块，0表示不是，1表示是最后一块。  
  
输出一个块，对现在字典中的内容没有影响，下一个块，仍将用之前形成的字典，进行匹配。  
  
2.7 静态Huffman编码与动态Huffman编码  
  
静态Huffman编码就是使用gzip自己预先定义好了一套编码进行压缩，解压缩的时候也使用这套编码，这样不需要传递用来生成树的信息。  
动态Huffman编码就是使用统计好的各个符号的出现次数，建立Huffman树，产生各个符号的Huffman编码，用这产生的Huffman编码进行压缩，这样需要传递生成树的信息。  
  
gzip 在为一块进行Huffman编码之前，会同时建立静态Huffman树，和动态Huffman树，然后根据要输出的内容和生成的Huffman树，计算使用静态Huffman树编码，生成的块的大小，以及计算使用动态Huffman树编码，生成块的大小。然后进行比较，使用生成块较小的方法进行Huffman编码。  
  
对于静态树来说，不需要传递用来生成树的那部分信息。动态树需要传递这个信息。而当文件比较小的时候，传递生成树的信息得不偿失，反而会使压缩文件变大。也就是说对于文件比较小的时候，就可能会出现使用静态Huffman编码比使用动态Huffman编码，生成的块小。  
  
2.8 编码的产生  
  
deflate算法在Huffman树的基础上，又加入了几条规则，我们把这样的树称作deflate树，使得只要知道所有位长上的结点的个数，就可以得到所有结点的编码。这样做的原因是，减少需要存放在压缩压缩文件中的用来生成树的信息。要想弄明白，deflate如何生成Huffman编码，一定要弄明白一些Huffman树，和deflate树的性质，下面内容是对Huffman树和deflate树做了些简单研究得到的。  
  
Huffman树的性质  
  
1 叶子结点为n的话，那么整颗树的总结点为 2n-1。  
简单证明说明，先证，最小的树，也就是只有三个结点，一个根节点，两个叶子节点的树符合。然后在任何符合的树上做最小的添加得到的树也符合。所以都符合。  
  
2 最左边的叶子结点的编码为0，但是位长不一定。  
  
deflate中增加了附加条件的huffman树的性质  
  
1 同样位长的叶子结点的编码值为连续的，右面的总比左面的大1。  
  
2 (n+1)位长最左面的叶子结点（也就是编码值最小的叶子结点）的值为n位长最右面的叶子结点（也就是编码值最大的叶子结点）的值+1，然后变长一位（也就是左移1位）。  
  
3 n位长的叶子结点，最右面的叶子结点（也就是编码值最大的叶子结点）的值为最左面的叶子结点（也就是编码值最小的叶子结点）的值 加上 n位长的叶子结点的个数 减 1。  
  
4 (n+1)位长最左面的叶子结点（也就是编码值最小的叶子结点）的值 为 n位长最左面的叶子结点（也就是编码值最小的叶子结点）的值加上 n位长的叶子结点的个数，然后变长一位（也就是左移1位）。  
  
还有一些树的性质，比如，树的某一深度上最大可能编码数。  
  
从所有编码的位长，得到所有编码的编码：  
统计每个位长上的编码个数放在bl\_count\[\]中。  
根据 bl\_count\[\] 中的值，计算出每个位长上的最小编码值，放在 next\_code\[\] 中。  
计算方法为，code = (code + bl\_count\[bits-1\]) << 1;  
理由是deflate二叉树的性质，(n+1)位长最左面的叶子结点（也就是编码值最小的叶子结点）的值为 n位长最左面的叶子结点（也就是编码值最小的叶子结点）的值 加上 n位长的叶子结点的个数，然后变长一位（也就是左移1位）。  
  
然后按照代码值的顺序，为所有的代码编码。  
编码方法为，某一位长对应的next\_code\[n\]，最开始是这个位长上最左边的叶子结点的编码，然后++，就是下一个该位长上下一个叶子结点的编码，依次类推，直到把这个位长上的叶子结点编码完。实际上的编码为bi\_reverse(next\_code\[\])。  
这样编码的理由是，deflate二叉树的性质。  
  
2.9 5棵树  
  
一共有5棵树 static\_ltree\[\]，static\_dtree\[\]，dyn\_ltree\[\]，dyn\_dtree\[\]，bl\_tree\[\]。  
对于所有的树，一个叶子结点表示的符号的值为n的话，那么这个符号对应的叶子结点放在 tree\[n\] 中  
比如 static\_ltree 的叶子结点'a' 的值为十进制97，那么'a'的叶子结点就放在 static\_ltree\[97\] 。  
  
static\_ltree\[\] 静态Huffman编码时，用来对没有改动的字节和匹配长度进行编码的树。  
static\_dtree\[\] 静态Huffman编码时，用来对相隔距离进行编码的树。  
dyn\_ltree\[\] 动态Huffman编码时，用来对没有改动的字节和匹配长度进行编码的树。  
dyn\_dtree\[\] 动态Huffman编码时，用来对相隔距离进行编码的树。  
bl\_tree\[\] 动态Huffman编码时，用来对解压缩时用来产生dyn\_ltree\[\]和dyn\_dtree\[\]的信息进行编码的树。  
  
静态树在初始化的时候，为每个叶子结点直接产生编码。  
动态树，每次要输出一块的内容，就根据这一块的内容，生成动态树，再根据生成的动态树，为每个叶子结点产生编码。  
  
每次要输出一块的内容时，会计算用静态树编码得到的块的大小，和用动态树编码得到的块的大小，然后谁产生的块小就用谁。  
  
用静态编码的话，就使用 static\_ltree\[\]，static\_dtree\[\]，来进行编码输出。  
用动态编码的话，就使用 dyn\_ltree\[\]，dyn\_dtree\[\]，bl\_tree\[\] 来进行编码输出。  
  
2.10 叶子结点  
  
ltree （用来对没有改动的字节和匹配长度进行编码的树，静态，动态都一样）的叶子结点  
一共 L\_CODES 个，也就是286个。  
0-255 256个叶子结点，是字节的256个值  
256 1个叶子结点，是 END\_BLOCK，用来表示块结束的叶子结点。  
257-285 29个叶子结点，是表示匹配长度的29个范围。  
  
dtree （用来对相隔距离进行编码的树，静态，动态都一样）的叶子结点  
一共 D\_CODES 个，也就是30个。  
0-29 30个叶子结点，是表示相隔距离的30个范围。  
  
bl\_tree 的叶子结点  
一共 BL\_CODES 个，也就是19个。  
0-15 表示编码位长为 0-15。  
16 复制之前的编码长度3-6次。之后的两位指明重复次数。  
17 重复编码位长为0的，3-10次，之后的3位指明重复次数。  
18 重复编码位长为0的，11-138次，之后的7位指明重复次数。  
  
2.11 静态Huffman编码  
  
初始化base\_length\[\],length\_code\[\],base\_dist\[\],dist\_code\[\]。  
  
base\_length\[\]为，29个 匹配长度 范围的，每个范围开始的长度值。  
length\_code\[\]为，256 个可能的匹配长度 所属的范围。  
比如，base\_length\[9\]=0xa，表示第9个范围的开始值为0xa。  
length\_code\[11\]=9,表示匹配长度为11的匹配长度，属于第9个范围。  
  
base\_dist\[\],30个 匹配距离 范围的，每个范围的开始的值，就是每个范围内最小的值。  
dist\_code\[\],这个有点特殊，一共有32K个取值，这里把这32K种值，分成了两大类，  
0-255这256个值为一类，这时他们直接为dist\_code\[\]的索引。  
256-32K为一类，这时他们的去掉低7位，和最高位，剩下的8位为索引，8位刚好索引256项。能这么做的原因是，首先最大32K的距离最大需要15位，所以16位的最高位总不会用，其次剩下这些范围的边界至少都为二进制1 000 0000 的整数倍。  
比如 匹配距离为 10,小于256，所以它属于类 dist\_code\[10\]=6，第6类。  
匹配距离为 10K ，大于256，所以它属于类dist\_code\[256+10K>>7\]=dist\_code\[256+10240>>7\]=dist\_code\[256+80\]=dist\_code\[336\]=0x1a=26，属于26类，26类的范围为8193-12288，10240就是在这个范围内。  
  
指定了每个literal的位长。（一共将有288个literal。包括256个字节值+1个EOB+29个匹配长度范围=286个。多2个是为了满树。）并统计每个位长上的literal个数放在bl\_count\[\]中。  
  
根据 bl\_count\[\] 中的值，计算出每个位长上的最小编码值，放在 next\_code\[\] 中。  
计算方法为，code = (code + bl\_count\[bits-1\]) << 1;  
理由是deflate二叉树的性质，(n+1)位长最左面的叶子结点（也就是编码值最小的叶子结点）的值为 n位长最左面的叶子结点（也就是编码值最小的叶子结点）的值 加上 n位长的叶子结点的个数，然后变长一位（也就是左移1位）。  
  
然后从literal值的0，到literal值的最大。为每个literal编码。  
编码方法为，某一位长对应的next\_code\[n\]，最开始是这个位长上最左边的叶子结点的编码，然后++，就是下一个该位长上下一个叶子结点的编码，依次类推，直到把这个位长上的叶子结点编码完。  
实际上的编码为bi\_reverse(next\_code\[\])。  
比如  
tree\[n\].Code = bi\_reverse(next\_code\[len\]++, len);  
  
此时 next\_code\[len\] 值为 二进制 00110000 即0x30  
tree\[n\].Code 最后被赋值为 二进制 00001100 即0x0c  
  
这样我们就得到了 static\_ltree\[\]，它以literal的值为索引，存放着literal对应的编码。  
比如 'a' 的值为十进制97， static\_ltree\[97\].code=0x0089 static\_ltree\[97\].len=8。  
说明a的编码为二进制 10001001。  
  
为static\_dtree编码。这个编码很简单，由于所有结点都是5位长的（指定的），所以根据deflate二叉树性质，最左边的叶子节点编码为0，之后每次加1即可，直到编完所有叶子结点。注意这里也要bi\_reverse()一下。也就是说，编码为"从树根开始到一个叶子结点的路径对应的位流"的逆位流。  
  
用Huffman编码对LZ77处理结果进行编码输出。  
  
这时，  
l\_buf\[\]中每个字节为literal或者 匹配长度-MIN\_MATCH。  
d\_buf\[\]为匹配距离，每项为16位。  
flag\_buf\[\]中每位为指示inbuf\[\]中对应字节为literal还是匹配长度-MIN\_MATCH 的标志，比如  
flag\_buf第i位为1，说明inbuf\[i\]为匹配长度-MIN\_MATCH。  
  
读出flag\_buf中的每一位，进行判断。  
如果为0，表示对应的l\_buf中的那个字节为literal。  
如果为1，表示对应的l\_buf中的那个字节为匹配长度-MIN\_MATCH。  
  
对于literal，就用l\_buf\[\]的这个值做索引，在static\_ltree中得到编码，和编码长度，然后输出这个编码。  
  
对于 匹配长度-MIN\_MATCH，就用l\_buf\[\]的这个值做索引，在length\_code\[\]中首先得到这个匹配长度所在的范围，一共有29个范围。也就是说匹配长度-MIN\_MATCH 取值范围为 (3..258)，一共有256种可能的值。这256种可能值，被分配在了29个范围中。  
  
我们用l\_buf\[\]的这个值做索引，在length\_code\[\]中得到这个匹配长度所在的范围。  
  
然后用 范围值+256+1 得到该范围所对应的 literal。用这个literal做索引，在static\_ltree中得到编码，和编码长度，然后输出这个编码。  
  
然后用 范围值 做索引，在 extra\_lbits\[\] 中得到该范围的附加位的位数，如果附加位位数不为0，  
就输出附加位。附加位为 inbuf\[\]中的那个值，就是 匹配长度-MIN\_MATCH 减去 这个范围的对应的 base\_length\[\]。  
  
然后从d\_buf\[\]中取出，匹配距离。  
当匹配距离小于256时，用匹配距离做索引，在dist\_code中取出对应的范围值。  
当匹配距离不小于256时，用匹配距离右移7位，也就是用高8位，做索引，在dist\_code+256中取出对应的范围值。  
  
对匹配距离，匹配距离的取值范围为，(1..32,768)，一共有32k种可能的值。  
分成了30个范围。由于匹配距离的取值范围为，(1..32,768)，所以匹配距离使用15位。  
  
然后用距离的范围值做索引，在static\_dtree\[\] 中得到编码，和编码长度。然后输出这个编码。  
然后用距离的范围值做索引，在extra\_dbits\[\] 中得到该范围的附加位的位数，如果附加位位数不为0，  
就输出附加位。输出的附加位为 dist-base\_dist\[code\]。  
  
比如，取出一个dist为10。dist\_code\[10\]=6，说明属于第6个范围。  
然后查 extra\_dbits,extra\_dbits\[6\]=2，说明有两个extra bits。  
local int near extra\_dbits\[D\_CODES\] /\* extra bits for each distance code \*/  
= \{0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13\};  
首先输出 static\_dtree\[6\].len位的位流，static\_dree\[6\].code。（static\_dtree的位长都为5）  
然后输出 extra\_dbits\[6\]位的位流，10-base\_dist\[6\]=10-8=2=二进制的10。  
  
发送完inbuf中的每个字节之后，最后发送 END\_BLOCK 的编码。  
  
2.12 动态Huffman编码  
  
确定所有literal，匹配长度范围，和匹配距离范围的出现次数。  
在进行LZ77压缩的过程中，每确定一个literal或者匹配，都会调用 ct\_tally()。  
在 ct\_tally() 中，如果是一个literal，就 dyn\_ltree\[lc\].Freq++。  
如果是一个匹配，就 dyn\_ltree\[length\_code\[lc\]+LITERALS+1\].Freq++，dyn\_dtree\[d\_code(dist)\].Freq++。  
  
调用 build\_tree() 建立 literal和匹配长度范围（也就是dyn\_ltree的叶子结点，共286个） 的树，并为他们（literal和匹配长度范围）编码。  
生成树中，heap\[\]是用来辅助生成树的缓冲区。  
  
首先把tree\[\]中所有出现次数不为0的值（也就是索引，比如tree\[0x61\]就为'a'的对应项），放到heap\[\]中。  
  
tree\[\] 的元素个数为 2\*L\_CODES+1，L\_CODES为叶子结点的个数，286。  
由Huffman二叉树性质，叶子结点为n,那么这棵树的总结点为2n-1。  
  
tree\[\] 将用来保存生成的树。tree\[\]的前L\_CODES 项，用来存放叶子结点。比如'a'的结点信息，放在tree\[0x61\]中。L\_CODES 之后的项用来放中间结点。  
  
heap\[\] 将用来放生成树的过程中产生的临时内容。heap\[\]的大小也为 2\*L\_CODES+1 。它的前 L\_CODES 用来放  
生成树过程中的结点，最开始是叶子结点，随着生成树的进行，两个叶子结点被弄掉，放入他们的中间结点。后 L\_CODES ，从后向前用。在生成树的过程中，所有结点（根，中间，叶子）都将按权值大小顺序放在这里。  
将来生成位长时，需要使用。  
  
pqdownheap(tree, SMALLEST); 的作用就是将heap中的结点中，找出freq最小的那个，放在heap\[1\]中。  
  
生成树的过程为，每次从heap中找出两个最小的结点，然后给他们弄一个父结点。并把他们的tree\[\]的相应内容指向他们的父结点。  
并在heap中删掉这两个结点，而把他们的父结点加入到heap中。  
  
heaplen 为heap中结点的个数，每次由于要删2个结点，加1个结点，所以每次会使heaplen--，也就是结点数变少一个。  
  
等到heaplen，也就是结点数，小于2时，说明树已经要弄好了。  
  
树生成好之后，tree\[\]中的域 freq 和 dad 都被设置好了，调用 gen\_bitlen()，为他们生成位长。  
  
gen\_bitlen()中，  
  
从根开始，根的位长为0，向下，为每个结点设置位长。  
  
判断是否为叶子结点，判断的方法是，看是否大于最大代码，这里最大代码是286。  
  
当遇到叶子结点时，进行动态编码整个文件的总位长的计算，和进行静态编码整个文件的总位长的计算。  
bl\_count\[bits\]++; 用来一会儿产生编码。  
由于在叶子结点的freq域中保存着这个结点的出现次数，现在又有了位长，所以可以计算该结点的动态位长。  
而所有的结点的动态位长累加在一起就是总位长。  
有了出现次数，对于静态，结点位长是设定好的，也同样可以进行计算。  
  
最后调用 gen\_codes()，为所有叶子结点产生编码。和静态Huffman中的方法是相同的。  
  
调用 build\_tree() 建立 匹配距离范围（也就是dyn\_dtree的叶子结点，共30个） 的树，并为他们（匹配距离范围）编码。和生成dyn\_ltree的方法是相同的。  
  
调用 build\_bl\_tree() 为l（literal&匹配长度）和d（匹配距离）的位长数组 生成树，并为这些位长编码。  
  
调用scan\_tree统计一个树中的编码长度情况。  
分别对dyn\_ltree和dyn\_dtree进行统计。  
  
scan\_tree((ct\_data near \*)dyn\_ltree, l\_desc.max\_code);  
scan\_tree((ct\_data near \*)dyn\_dtree, d\_desc.max\_code);  
  
统计结果放在 bl\_tree\[\].Freq 中。  
  
弄明白了bl\_tree\[\]中叶子结点的含义，就很容易理解scan\_tree中所作的工作。  
比如 bl\_tree\[0\].Freq 表示编码位长为0的编码个数。  
bl\_tree\[10\].Freq 表示编码位长为10的编码个数。  
bl\_tree\[16\].Freq 表示 连续几个编码长度的出现个数都相同，这种情况的出现次数。  
  
最后调用 build\_tree() 建立位长情况（就是那19种情况）的树，并为他们（就是那19种情况）编码。  
  
发送用bl\_tree编码的结点位长数组。  
defalte算法中，只要知道了一个树的每个叶子结点的位长，就可以得到该叶子结点的编码。  
所以我们需要发送ltree的286个叶子结点的位长，我们需要发送dtree的30个叶子结点的位长。  
  
首先发送三个树的最大叶子结点值的一个变形。  
send\_bits(lcodes-257, 5); 发送ltree有效最大叶子结点值+1-257  
send\_bits(dcodes-1, 5); 发送dtree有效最大叶子结点值+1-1  
send\_bits(blcodes-4, 4); 发送bl\_tree有效最大叶子结点值+1-4。  
ltree最大叶子结点值，就决定了我们将要发送的ltree的叶子结点位长数组的个数。只发送到有效最大叶子结点数就行了。  
比如，ltree有效最大叶子结点值为0x102的话，那么我们只需要发送ltree中前0x103个的位长，并告诉解压缩程序，发送了0x103个就行了。  
  
发送 bl\_tree 的位长，注意发送的顺序是按 bl\_order\[\] 中规定的顺序发送的。  
  
调用 send\_tree() 先后发送 dyn\_ltree,dyn\_dtree 的位长。  
  
send\_tree()中使用和scan\_tree()中相同的方法，首先看这些位长属于bl\_tree的19个叶子结点对应的19种情况中的哪一种，确定了是哪一种之后，  
就按这种情况对应的叶子结点，在bl\_tree中的编码，发送这个编码。直到把这些位长都发完。  
  
用Huffman编码对LZ77处理结果进行编码输出。和静态Huffman编码时使用的方法是相同的。

2.13 要点

第一，省去了LZ77用来指明是"没有改动的字节"还是"匹配的信息对"的那个标志位。  
  
由于gzip实现中，把匹配长度的范围和字节值，做为不同的叶子结点进行编码。比如说，值为1的字节，和一个值为1的匹配长度，他们的值虽然相同，但是他们是不同的叶子结点，他们的编码也是不同的。这样一来，解压缩时，就可以直接区分，就不必再输出那个指示位了。  
  
这个节省对压缩率的改善应该有不小的帮助。  
  
静态Huffman编码时，编码本身不会起到什么压缩作用，但是还会从这个节省中获益。  
  
第二，叶子结点所表示的内容。  
  
我们看到gzip的实现中，叶子节点所代表的内容各种各样，不仅仅是一个固定的值，而且有些代表了一个值的范围，（然后用之后的更多的位来表示这个范围中的一个值），而且还有代表情况的。  
  
这个实现方法是相当不错的，非常值得借鉴。  
  
解压缩也不说了，原因看最后。  
  
2.14 匹配延伸到lookahead中  
  
可以进行这种压缩，与解压缩，关键是解压缩的处理中，做了特别的处理。  
  
例，串 0aaaaa  
  
进行lz77压缩时，当今行到下面位置时 0a 当前位置->aaaa  
匹配会延伸到lookahead中，结果就是 0a\[匹配长度4，距离1\]  
  
解压缩时，首先0a被做为没有改动的字节解压出来，  
然后解压发现\[匹配长度4，距离1\]，  
这里将做一个判断，看有没有延伸到lookahead中，如果有的话，将做特别的处理，一个字节一个字节的进行复制。

[2011092909392629.jpg]: /images/20220805/4a59401b216d438596759ef04b07474c.png