超级变态的gzip算法

1、1 gzip 所使用压缩算法的基本原理gzip 对于要压缩的文件,首先使用LZ77算法的一个变种进行压缩,对得到的结果再使用Huffman编码的方法(实际上gzip根据情况,选择使用静态Huffman编码或者动态Huffman 编码,详细内容在实现中说明进行压缩。所以明白了LZ77算法和Huffman编码的压缩原理,也就明白了gzip的压缩原理。我们来对LZ77算法和Huffman编码做一个简单介绍。1.1 LZ77算法简介这一算法是由Jacob Ziv 和Abraham Lempel 于1977 年提出,所以命名为LZ77。如果文件中有两块内容相同的话,那么只要知道前一块的位置和大小,我们就

2、可以确定后一块的内容。所以我们可以用(两者之间的距离,相同内容的长度这样一对信息,来替换后一块内容。由于(两者之间的距离,相同内容的长度这一对信息的大小,小于被替换内容的大小,所以文件得到了压缩。下面我们来举一个例子。有一个文件的内容如下(22,13中,22为相同内容块与当前位置之间的距离,13为相同内容的长度。(23,4中,23为相同内容块与当前位置之间的距离,4为相同内容的长度。由于(两者之间的距离,相同内容的长度这一对信息的大小,小于被替换内容的大小,所以文件得到了压缩。LZ77算法使用"滑动窗口"的方法,来寻找文件中的相同部分,也就是匹配串。我们先对这里的串做一个说

3、明,它是指一个任意字节的序列,而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强调的是它在文件中的位置,它的长度随着匹配的情况而变化。LZ77从文件的开始处开始,一个字节一个字节的向后进行处理。一个固定大小的窗口(在当前处理字节之前,并且紧挨着当前处理字节,随着处理的字节不断的向后滑动,就象在阳光下,飞机的影子滑过大地一样。对于文件中的每个字节,用当前处理字节开始的串,和窗口中的每个串进行匹配,寻找最长的匹配串。窗口中的每个串指,窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串,就用(之间的距离,匹配长度 这样一对信息,来替换当前串,然后从刚才处理完的串之后的下一个

4、字节,继续处理。如果当前处理字节开始的串在窗口中没有匹配串,就不做改动的输出当前处理字节。处理文件中第一个字节的时候,窗口在当前处理字节之前,也就是还没有滑到文件上,这时窗口中没有任何内容,被处理的字节就会不做改动的输出。随着处理的不断向后,窗口越来越多的滑入文件,最后整个窗口滑入文件,然后整个窗口在文件上向后滑动,直到整个文件结束。为了在解压缩时,可以区分“没有匹配的字节”和“(之间的距离,匹配长度对”,我们还需要在每个“没有匹配的字节”或者“(之间的距离,匹配长度对”之前,放上一位,来指明是“没有匹配的字节”,还是“(之间的距离,匹配长度对”。我们用0表示“没有匹配的字节”,用1表示“(之

5、间的距离,匹配长度对”。实际中,我们将固定(之间的距离,匹配长度对中的,“之间的距离”和“匹配长度”所使用的位数。由于我们要固定“之间的距离”所使用的位数,所以我们才使用了固定大小的窗口,比如窗口的大小为32KB,那么用15位(215=32K就可以保存0-32K范围的任何一个值。实际中,我们还将限定最大的匹配长度,这样一来,“匹配长度”所使用的位数也就固定了。实际中,我们还将设定一个最小匹配长度,只有当两个串的匹配长度大于最小匹配长度时,我们才认为是一个匹配。我们举一个例子来说明这样做的原因。比如,“距离”使用15位,“长度”使用8位,那么“(之间的距离,匹配长度对”将使用23位,也就是差1位

6、3个字节。如果匹配长度小于3个字节的话,那么用“(之间的距离,匹配长度对”进行替换的话,不但没有压缩,反而会增大,所以需要一个最小匹配长度。压缩:从文件的开始到文件结束,一个字节一个字节的向后进行处理。用当前处理字节开始的串,和滑动窗口中的每个串进行匹配,寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串,就先输出一个标志位,表明下面是一个(之间的距离,匹配长度 对,然后输出(之间的距离,匹配长度 对,然后从刚才处理完的串之后的下一个字节,继续处理。如果当前处理字节开始的串在窗口中没有匹配串,就先输出一个标志位,表明下面是一个没有改动的字节,然后不做改动的输出当前处理字节,然后继续处理

7、当前处理字节的下一个字节。解压缩:从文件开始到文件结束,每次先读一位标志位,通过这个标志位来判断下面是一个(之间的距离,匹配长度 对,还是一个没有改动的字节。如果是一个(之间的距离,匹配长度对,就读出固定位数的(之间的距离,匹配长度对,然后根据对中的信息,将匹配串输出到当前位置。如果是一个没有改动的字节,就读出一个字节,然后输出这个字节。我们可以看到,LZ77压缩时需要做大量的匹配工作,而解压缩时需要做的工作很少,也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩,多次解压缩的情况,是一个巨大的优点。1.2 Huffman编码简介我们把文件中一定位长的值看作是符号,比如把8位长的256种

8、值,也就是字节的256种值看作是符号。我们根据这些符号在文件中出现的频率,对这些符号重新编码。对于出现次数非常多的,我们用较少的位来表示,对于出现次数非常少的,我们用较多的位来表示。这样一来,文件的一些部分位数变少了,一些部分位数变多了,由于变小的部分比变大的部分多,所以整个文件的大小还是会减小,所以文件得到了压缩。要进行Huffman编码,首先要把整个文件读一遍,在读的过程中,统计每个符号(我们把字节的256种值看作是256种符号的出现次数。然后根据符号的出现次数,建立Huffman 树,通过Huffman树得到每个符号的新的编码。对于文件中出现次数较多的符号,它的Huffman编码的位数比

9、较少。对于文件中出现次数较少的符号,它的Huffman编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。建立Huffman树:把所有符号看成是一个结点,并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树。每次从所有树中找出值最小的两个树,为这两个树建立一个父结点,然后这两个树和它们的父结点组成一个新的树,这个新的树的值为它的两个子树的值的和。如此往复,直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树。通过Huffman树得到Huffman编码:这棵Huffman树,是一棵二叉树,它的所有叶子结点就是所有的符号,它的中间结点是在产生Huffman树的过程

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

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

12、man编码是可以区分的。为了在解压缩的时候,得到压缩时所使用的Huffman树,我们需要在压缩文件中,保存树的信息,也就是保存每个符号的出现次数的信息。压缩:读文件,统计每个符号的出现次数。根据每个符号的出现次数,建立Huffman树,得到每个符号的Huffman编码。将每个符号的出现次数的信息保存在压缩文件中,将文件中的每个符号替换成它的Huffman编码,并输出。解压缩:得到保存在压缩文件中的,每个符号的出现次数的信息。根据每个符号的出现次数,建立Huffman树,得到每个符号的Huffman编码。将压缩文件中的每个Huffman编码替换成它对应的符号,并输出。2 gzip 所使用压缩算法

13、的实现我们将gzip的实现分成很多个部分,一个个来说明,这样做的原因见本文最后一部分。gzip 中所使用的各种实现技巧的出处或者灵感,gzip 的作者在源码的注释中进行了说明。2.1 寻找匹配串的实现为一个串寻找匹配串需要进行大量的匹配工作,而且我们还需要为很多很多个串寻找匹配串。所以gzip 在寻找匹配串的实现中使用哈希表来提高速度。要达到的目标是,对于当前串,我们要在它之前的窗口中,寻找每一个匹配长度达到最小匹配的串,并找出匹配长度最长的串。在gzip 中,最小匹配长度为3,也就是说,两个串,最少要前3个字节相同,才能算作匹配。为什么最小匹配长度为3,将在后面说明。gzip 对遇到的每一个

14、串,首先会把它插入到一个“字典”中。这样当以后有和它匹配的串,可以直接从“字典”中查出这个串。插入不是乱插,查也不是乱查。插入的时候,使用这个插入串的前三个字节,计算出插入的“字典”位置,然后把插入串的开始位置保存在这个“字典”位置中。查出的时候,使用查出串的前三个字节,计算出“字典”位置,由于插入和查出使用的是同一种计算方法,所以如果两个串的前三个字节相同的话,计算出的“字典”位置肯定是相同的,所以就可以直接在该“字典”位置中,取出以前插入时,保存进去的那个串的开始位置。于是查出串,就找到了一个串,而这个串的前三个字节和自己的一样(其实只是有极大的可能是一样的,原因后面说明,所以就找到了一个

15、匹配串。如果有多个串,他们的前三个字节都相同,那么他们的“字典”位置,也都是相同的,他们将被链成一条链,放在那个“字典”位置上。所以,如果一个串,查到了一个“字典”位置,也就查到了一个链,所有和它前三个字节相同的串,都在这个链上。也就是说,当前串之前的所有匹配串被链在了一个链上,放在某个“字典”位置上。而当前串使用它的前三个字节,进行某种计算,就可以得到这个“字典”位置(得到了“字典”位置之后,它首先也把自己链入到这个链上,也就找到了链有它的所有匹配串的链,所以要找最长的匹配,也就是遍历这个链上的每一个串,看和哪个串的匹配长度最大。下面我们更具体的说明,寻找匹配串的实现。我们前面所说的“字典”

16、,是一个数组,叫做head(为什么叫head,后面进行说明。我们前面所说的“字典”位置,放在一个叫做ins_h的变量中。我们前面所说的链,是在一个叫做prev的数组中。插入:当前字节为第strstart 个字节。通过第strstart,strstart+1,strstart+2,这三个字节,使用一个设计好的哈希函数算出ins_h,也就是插入的位置。然后将当前字节的位置,即strstart,保存在headins_h中。注意由strstart,strstart+1,strstart+2,这三个字节(也就是strstart开始处的串的头三个字节,也就是当前字节和之后的两个字节确定了ins_h。hea

17、dins_h中保存的又是strstart,也就是这个串开始的位置。判断是否有匹配:当前串的前三个字节,使用哈希函数算出ins_h,这时如果headins_h的值不为空的话,那么headins_h中的值,便是之前保存在这里的另一个串的位置,并且这个串的前三个字节算出的ins_h,和当前串的前三个字节算出的ins_h相同。也就是说有可能有匹配。如果headins_h的值为空的话,那么肯定没有匹配。gzip所使用的哈希函数:gzip 所使用的哈希函数,用三个字节来计算一个ins_h,这是由于最小匹配为三个字节。对于相同的三个字节,通过哈希函数得到的ins_h必然是相同的。而不同的三个字节,通过哈希函

18、数有可能得到同一个ins_h,不过这并不要紧,当gzip发现headins_h不空后,也就是说有可能有匹配串的话,会对链上的每一个串进行真正的串的比较。所以一个链上的串,只是前三个字节用哈希函数算出的值相同,而并不一定前三个字节都是相同的。但是这样已经很大的缩小了需要进行串比较的范围。我们来强调一下,前三个字节相同的串,必然在同一个链上。在同一个链上的,不一定前三个字节都相同。不同的三个字节有可能得到同一个结果的原因是,三个字节,一共24位,有224种可能值。而三个字节的哈希函数的计算结果为15位,有215种可能值。也就是说224种值,与215种值进行对应,必然是多对一的,也就是说,必然是有多

19、种三个字节的值,用这个哈希函数计算出的值都是相同的。而我们使用哈希函数的理由是,实际上,我们只是在一个窗口大小的范围内(后面将会看到寻找匹配串,一个窗口的大小范围是很有限的,能出现的三个字节的值组合情况也是很有限的,将远远小于224,使用合适的哈希函数是高效的。前三个字节相同的所有的串所在的链:headins_h 中的值,有两个作用。一个作用,是一个前三个字节计算结果为ins_h的串的位置。另一个作用,是一个在prev数组中的索引,用这个索引在prev中,将找到前一个前三个字节计算结果为ins_h的串的位置。即prevheadins_h的值(不为空的话为前一个前三个字节计算结果为ins_h的串

20、的位置。prev的值,也有两个作用。一个作用,是一个前三个字节计算结果为ins_h的串的位置。另一个作用,是一个在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 abc

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

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

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

24、,不过这种情况只会出现在第0个字节,所以通常不会造成影响,即使影响,也会极小。例如,文件内容为jiurl jiurl找到的匹配情况如下,所括部分。jiurl jiurl2.2 懒惰啊匹配(lazy match对于当前字节开始的串,寻找到了最长匹配之后,gzip并不立即决定使用这个串进行替换。而是看看这个匹配长度是否满意,如果匹配长度不满意,而下一个字节开始的串也有匹配串的话,那么gzip就找到下一个字节开始的串的最长匹配,看看是不是比现在这个长。这叫懒惰啊匹配。如果比现在这个长的话,将不使用现在的这个匹配。如果比现在这个短的话,将确定使用现在的这个匹配。我们来举个例子,串0abc bcde a

25、bcde处理到第10字节时,也就是"abcde"的a时,找到最长匹配的情况如下,所括部分。0abc bcde abcde这时,再看看下一个字节,也就是第11字节的情况,也就是'abcde"的b,找到最长匹配的情况如下,所括部分。0abc bcde abcde发现第二次匹配的匹配长度大,就不使用第一次的匹配串。我们也看到了如果使用第一次匹配的话,将错过更长的匹配串。在满足懒惰啊匹配的前提条件下,懒惰啊匹配不限制次数,一次懒惰啊匹配发现了更长的匹配串之后,仍会再进行懒惰啊匹配,如果这次懒匹配,发现了更长的匹配串,那么上一次的懒匹配找到的匹配串就不用了。进行懒惰

26、啊匹配是有条件的。进行懒惰啊匹配必须满足两个条件,第一,下一个处理字节开始的串,要有匹配串,如果下一个处理字节开始的串没有匹配串的话,那么就确定使用当前的匹配串,不进行懒匹配。第二,当前匹配串的匹配长度,gzip不满意,也就是当前匹配长度小于max_lazy_match(max_lazy_match在固定的压缩级别下,有固定的值。讨论:我们可以看到了做另外一次尝试的原因。如果当前串有匹配就使用了的话,可能错过更长匹配的机会。使用懒惰啊匹配会有所改善。不过从我简单的分析来看,使用懒惰啊匹配对压缩率的改善似乎是非常有限的。2.3 大于64KB的文件,窗口的实现窗口的实现:实际中,当前串(当前处理字

27、节开始的串只是在它之前的窗口中寻找匹配串的,也就是说只是在它之前的一定大小的范围内寻找匹配串的。有这个限制的原因,将在后面说明。gzip 的窗口大小为WSIZE,32KB。内存中有一个叫window的缓冲区,大小为2个窗口的大小,也就是64KB。文件的内容将被读到这个window中,我们在window上进行LZ77部分的处理,得到结果将放在其他缓冲区中。gzip 对window中的内容,从开始处开始,一个字节一个字节的向后处理。有一个指针叫strstart(其实是个索引,指向当前处理字节,当当前处理字节开始的串没有匹配时,不做改动的输出当前处理字节,strstart向后移动一个字节。当当前处理

28、字节开始的串找到了匹配时,输出(匹配长度,相隔距离对,strstart向后移动匹配长度个字节。我们把strstart 到window结束的这部分内容,叫做lookahead buffer,超前查看缓冲区。这样叫的原因是,在我们处理当前字节的时候,就需要读出之后的字节来进行串的匹配。在一个变量lookahead 中,保存着超前查看缓冲区所剩的字节数。lookahead,最开始被初始化为整个读入内容的大小,随着处理的进行,strstart不断后移,超前查看缓冲区不断减小,lookahead的值也不断的减小。我们需要限制查找匹配串的范围为一个窗口的大小(这么做的原因后面说明,也就是说,只能在当前处理

29、字节之前的32KB的范围内寻找匹配串。而,由于处理是在2个窗口大小,也就是64KB大小的缓冲区中进行的,所以匹配链上的串与当前串之间的距离是很有可能超过32KB的。那么gzip是如何来实现这个限制的呢?gzip 通过匹配时的判断条件来实现这个限制。当当前串计算ins_h,发现headins_h值不为空时(headins_h为一个串的开始位置,说明当前串有可能有匹配串,把这个值保存在hash_head中。这时就要做一个限制范围的判断,strstart - hash_head <= 窗口大小, strstart-hash_head 是当前串和最近的匹配串之间的距离,(注意前面说过,链头和当前

30、串的距离最近,越向前(prev与当前处理位置之间的距离越大,也就是说要判断当前串和距离最近的匹配串之间的距离是否在一个窗口的范围之内。如果不是的话,那么链上的其他串肯定更远,肯定更不在一个窗口的范围之内,就不进行匹配处理了。如果是在一个窗口的范围之内的话,还需要在链上寻找最长的匹配串,在和每个串进行比较的时候,也需要判断当前串和该串的距离是否超过一个窗口的范围,超过的话,就不能进行匹配。实际中,gzip为了使代码简单点,距离限制要比一个窗口的大小还要小一点。小于64KB的文件:初始化的时候,会首先从文件中读64KB的内容到window中。对于小于64KB的文件,整个文件都被读入到window中

31、。在window上进行LZ77的处理,从开始直到文件结束。大于64KB的文件:每处理一个字节都要判断lookahead < MIN_LOOKAHEAD ,也就是window中还没有处理的字节是否还够MIN_LOOKAHEAD ,如果不够的话,就会导致fill_window(,从文件中读内容到window中。由于我们一次最大可能使用的超前查看缓冲区的大小为,最大匹配长度(258个字节,后面进行说明加上最小匹配长度,也就是下一个处理字节开始的串,可以找到一个最大匹配长度的匹配,发生匹配之后,还要预读一个最小匹配长度来计算之后的ins_h。不管是大于64KB的文件,还是小于64KB的文件,随着

32、处理的进行,最终都要到文件的结束,在接近文件结束的时候,都会出现lookahead < MIN_LOOKAHEAD ,对于这种情况, fill_window( 读文件,就再读不出文件内容了,于是fill_window(会设置一个标志eofile,表示文件就要结束了,之后肯定会接着遇到lookahead < MIN_LOOKAHEAD ,不过由于设置了eofile 标志,就不会再去试图读文件到window中了。压缩开始之前的初始化,会从文件中读入64KB的内容到window中,窗口大小为32KB,也就是读入2窗的内容到window中。我们把第一窗的内容叫做w1_32k,第二窗的内容叫

33、做w2_32k。压缩不断进行,直到lookahead < MIN_LOOKAHEAD,也就是处理到了64KB内容的接近结束部分,也就是如果再处理,超前查看缓冲区中的内容就可能不够了。由于lookahead < MIN_LOOKAHEAD ,将执行fill_window(。fill_window( 判断是否压缩已经进行到了2窗内容快用完了,该把新的内容放进来了。如果是的话,fill_window( 把第二窗的内容w2_32k,复制到第一窗中,第一窗中的内容就被覆盖掉了,然后对match_start,strstart之类的索引,做修正。然后更新匹配链的链头数组,head,从头到尾过一遍

34、,如果这个头中保存的串的位置,在w2_32k中,就对这个串的位置做修正。如果这个头中保存的串的位置,在w1_32k中,就不要了,设为空,因为第一窗的内容我们已经覆盖掉了。然后更新prev数组,从头到尾过一遍,如果某项的内容,在w2_32k中,就做修正。如果这项的内容,在w1_32k中,就不要了,设为空,因为第一窗的内容我们已经覆盖掉了。最后fill_window(从文件中再读出一窗内容,也就是读出32KB的内容,复制到第二个窗中,注意第二个窗口中原来的内容,已经被复制到了第一个窗口中。就这样,一窗窗的处理,直到整个文件结束。分析:到第二窗文件内容也快要处理完的时候,才会从文件中读入新的内容。而

35、这时,第一窗中的所有串,对于当前处理字节和之后的字节来说,已经超出了一个窗口的距离,当前处理字节和之后的字节不能和第一窗的串进行匹配了,也就是说第一窗的内容已经没有用了。所有插入字典的第一窗的串也已经没有用了。所以覆盖第一窗的内容是合理的,将字典中第一窗的串的开始位置都设为空也是合理的。将第二窗的内容复制到第一窗中,那么第二窗在字典中的所有索引都需要做相应的修正。由于第二窗的内容已经复制到了第一窗中,所以我们可以将新的内容读入到第二窗中,新的内容之前的32KB的内容,就是原来的第二窗中的内容。而这时,做过修正的字典中,仍然有原来第二窗中所有串的信息,也就是说,新的内容,可以继续利用前面一个窗口

36、大小的范围之内的串,进行压缩,这也是合理的。2.4 其他问题1现在来说明一下,为什么最小匹配长度为3个字节。这是由于,gzip 中,(匹配长度,相隔距离对中,"匹配长度"的范围为3-258,也就是256种可能值,需要8bit来保存。"相隔距离"的范围为0-32K,需要15bit来保存。所以一个(匹配长度,相隔距离对需要23位,差一位3个字节。如果匹配串小于3个字节的话,使用(匹配长度,相隔距离对进行替换,不但没有压缩,反而还会增大。所以保存(匹配长度,相隔距离对所需要的位数,决定了最小匹配长度至少要为3个字节。最大匹配长度为258的原因是,综合各种因素,

37、决定用8位来保存匹配长度,8位的最大值为255。实际中,我们在(匹配长度,相隔距离对中的“匹配长度”保存的是,实际匹配长度-最小匹配长度,所以255对应的实际匹配长度为258。在进行匹配时,会对匹配长度进行判断,保证到达最大匹配长度时,匹配就停止。也就是说,即使有两个串的相同部分超过了最大匹配长度,也只匹配到最大匹配长度。保存相隔距离所用的位数和窗口大小是互相决定的,综合两方面各种因素,确定了窗口大小,也就确定了保存相隔距离所使用的位数。2.5 gzip 的LZ77部分的实现要点gzip 的LZ77 部分的实现主要在函数defalte( 中。所使用的缓冲区window 用来放文件中读入的内容。

38、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中。lookahe

39、ad 中为返回的读入字节数。使用window中的头两个字节,UPDATE_HASH,初始化ins_h。deflate( 中,一个处理循环中,首先INSERT_STRING 把当前串插入字典,INSERT_STRING 是一个宏,作用就是用哈希函数计算当前串的ins_h,然后把原来的headins_h中的内容,链入链中(放到prev中,同时把原来的headins_h保存在hash_head变量中,用来后面进行匹配判断,然后把当前串的开始位置,保存在headins_h中。判断hash_head中保存的内容不为空,说明匹配链上有内容。调用longest_match ( 寻找匹配链上的最长匹配。has

40、h_head中保存的内容为空,说明当前字节开始的串,在窗口中没有匹配。由于使用了lazy match,使得判断的情况更复杂。匹配串的输出,或者是没有匹配的字节的输出,都是调用函数ct_tally(。对于匹配串,输出之后,还需要为匹配串中的每个字节使用INSERT_STRING,把匹配串中每个字节开始的串都插入到字典中。ct_tally(中,把传入的"没有匹配的字节"或者是"匹配长度-3"放到l_buf中,然后为以后的Huffman编码做统计次数的工作,如果传入的是匹配情况,传入的参数中会有相隔距离,把相隔距离保存在d_buf中。根据传入的参数,可以判断是

41、哪种情况,然后设置一个变量中相应的标志位,每8个标志位,也就是够一个字节,就保存到flag_buf中。还有一些判断,我们将在后面进行说明。2.6 分块输出LZ77 压缩的结果放在,l_buf,d_buf,flag_buf 中。对于LZ77 的压缩结果,可能使用一块输出或者分成多块输出(LZ77压缩一定的部分之后,就进行一次块输出,输出一块。块的大小不固定。输出的时候,会对LZ77的压缩结果,进行Huffman编码,最终把Huffman编码的结果输出到outbuf缓冲区中。进行Huffman编码,并输出的工作,在flush_block( 中进行。在ct_tally(中进行判断,如果满足一些条件的

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

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

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

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

46、能会出现使用静态Huffman编码比使用动态Huffman编码,生成的块小。2.8 编码的产生deflate算法在Huffman树的基础上,又加入了几条规则,我们把这样的树称作deflate树,使得只要知道所有位长上的结点的个数,就可以得到所有结点的编码。这样做的原因是,减少需要存放在压缩压缩文件中的用来生成树的信息。要想弄明白,deflate如何生成Huffman 编码,一定要弄明白一些Huffman树,和deflate树的性质,下面内容是对Huffman树和deflate 树做了些简单研究得到的。Huffman树的性质1 叶子结点为n的话,那么整颗树的总结点为2n-1。简单证明说明,先证,

47、最小的树,也就是只有三个结点,一个根节点,两个叶子节点的树符合。然后在任何符合的树上做最小的添加得到的树也符合。所以都符合。2 最左边的叶子结点的编码为0,但是位长不一定。deflate中增加了附加条件的huffman树的性质1 同样位长的叶子结点的编码值为连续的,右面的总比左面的大1。2 (n+1位长最左面的叶子结点(也就是编码值最小的叶子结点的值为n位长最右面的叶子结点(也就是编码值最大的叶子结点的值+1,然后变长一位(也就是左移1位。3 n位长的叶子结点,最右面的叶子结点(也就是编码值最大的叶子结点的值为最左面的叶子结点(也就是编码值最小的叶子结点的值加上n位长的叶子结点的个数减1。4

48、(n+1位长最左面的叶子结点(也就是编码值最小的叶子结点的值为n位长最左面的叶子结点(也就是编码值最小的叶子结点的值加上n位长的叶子结点的个数,然后变长一位(也就是左移1位。还有一些树的性质,比如,树的某一深度上最大可能编码数。从所有编码的位长,得到所有编码的编码:统计每个位长上的编码个数放在bl_count中。根据bl_count 中的值,计算出每个位长上的最小编码值,放在next_code 中。计算方法为,code = (code + bl_countbits-1 << 1;理由是deflate二叉树的性质,(n+1位长最左面的叶子结点(也就是编码值最小的叶子结点的值为n位长最

49、左面的叶子结点(也就是编码值最小的叶子结点的值加上n位长的叶子结点的个数,然后变长一位(也就是左移1位。然后按照代码值的顺序,为所有的代码编码。编码方法为,某一位长对应的next_coden,最开始是这个位长上最左边的叶子结点的编码,然后+,就是下一个该位长上下一个叶子结点的编码,依次类推,直到把这个位长上的叶子结点编码完。实际上的编码为bi_reverse(next_code。这样编码的理由是,deflate二叉树的性质。2.9 5棵树一共有5棵树static_ltree,static_dtree,dyn_ltree,dyn_dtree,bl_tree。对于所有的树,一个叶子结点表示的符号的

50、值为n的话,那么这个符号对应的叶子结点放在treen 中,比如static_ltree 的叶子结点'a' 的值为十进制97,那么'a'的叶子结点就放在static_ltree97 。static_ltree 静态Huffman编码时,用来对没有改动的字节和匹配长度进行编码的树。static_dtree 静态Huffman编码时,用来对相隔距离进行编码的树。dyn_ltree 动态Huffman编码时,用来对没有改动的字节和匹配长度进行编码的树。dyn_dtree 动态Huffman编码时,用来对相隔距离进行编码的树。bl_tree 动态Huffman编码时,用来

51、对解压缩时用来产生dyn_ltree和dyn_dtree的信息进行编码的树。静态树在初始化的时候,为每个叶子结点直接产生编码。动态树,每次要输出一块的内容,就根据这一块的内容,生成动态树,再根据生成的动态树,为每个叶子结点产生编码。每次要输出一块的内容时,会计算用静态树编码得到的块的大小,和用动态树编码得到的块的大小,然后谁产生的块小就用谁。用静态编码的话,就使用static_ltree,static_dtree,来进行编码输出。用动态编码的话,就使用dyn_ltree,dyn_dtree,bl_tree 来进行编码输出。2.10 叶子结点ltree (用来对没有改动的字节和匹配长度进行编码的

52、树,静态,动态都一样的叶子结点一共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

53、次,之后的3位指明重复次数。18 重复编码位长为0的,11-138次,之后的7位指明重复次数。2.11 静态Huffman编码初始化base_length,length_code,base_dist,dist_code。base_length为,29个匹配长度范围的,每个范围开始的长度值。length_code为,256 个可能的匹配长度所属的范围。比如,base_length9=0xa,表示第9个范围的开始值为0xa。length_code11=9,表示匹配长度为11的匹配长度,属于第9个范围。base_dist,30个匹配距离范围的,每个范围的开始的值,就是每个范围内最小的值。dist_c

54、ode,这个有点特殊,一共有32K个取值,这里把这32K种值,分成了两大类,0-255这256个值为一类,这时他们直接为dist_code的索引。256-32K为一类,这时他们的去掉低7位,和最高位,剩下的8位为索引,8位刚好索引256项。能这么做的原因是,首先最大32K的距离最大需要15位,所以16位的最高位总不会用,其次剩下这些范围的边界至少都为二进制1 000 0000 的整数倍。比如匹配距离为10,小于256,所以它属于类dist_code10=6,第6类。匹配距离为10K ,大于256,所以它属于类dist_code256+10K>>7=dist_code256+1024

55、0>>7=dist_code256+80=dist_code336=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_countbits-1 << 1;理由是deflate二叉树的性质,(n+

56、1位长最左面的叶子结点(也就是编码值最小的叶子结点的值为n位长最左面的叶子结点(也就是编码值最小的叶子结点的值加上n位长的叶子结点的个数,然后变长一位(也就是左移1位。然后从literal值的0,到literal值的最大。为每个literal编码。编码方法为,某一位长对应的next_coden,最开始是这个位长上最左边的叶子结点的编码,然后+,就是下一个该位长上下一个叶子结点的编码,依次类推,直到把这个位长上的叶子结点编码完。实际上的编码为bi_reverse(next_code。比如treen.Code = bi_reverse(next_codelen+, len;此时next_codel

57、en 值为二进制00110000 即0x30treen.Code 最后被赋值为二进制00001100 即0x0c这样我们就得到了static_ltree,它以literal的值为索引,存放着literal对应的编码。比如'a' 的值为十进制97,static_ltree97.code=0x0089 static_ltree97.len=8。说明a的编码为二进制10001001。为static_dtree编码。这个编码很简单,由于所有结点都是5位长的(指定的,所以根据deflate二叉树性质,最左边的叶子节点编码为0,之后每次加1即可,直到编完所有叶子结点。注意这里也要bi_reverse(一下。也就是说,编码为"从树根开始到一个叶子结点的路径对应的位流"的逆位流。用Huffman编码对LZ77处理结果进行编码输出。这时,l_buf中每个字节为literal或者匹配长度-MIN_MATCH。d_buf为匹配距离,每项为16位。flag_buf中每