LZ77压缩算法详解.docx
《LZ77压缩算法详解.docx》由会员分享，可在线阅读，更多相关《LZ77压缩算法详解.docx（33页珍藏版）》请在冰点文库上搜索。
LZ77压缩算法详解
gzip、zlib以及图形格式png,使用的压缩算法都是deflate算法。
从gzip的源码中，我们了解到了defalte算法的原理和实现。
我阅读的gzip版本为gzip-1.2.4。
下面我们将要对deflate算法做一个分析和说明。
首先简单介绍一下基本原理，然后详细的介绍实现。
1gzip所使用压缩算法的基本原理
gzip对于要压缩的文件，首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用Huffman编码的
方法（实际上gzip根据情况，选择使用静态Huffman编码或者动态Huffman编码，详细内容在实现中说明）进行压缩。
所以明白了LZ77算法和Huffman编码的压缩原理，也就明白了gzip的压缩原理。
我们来对LZ77算法和Huffman编码做一个简单介绍。
1.1LZ77算法简介
这一算法是由JacobZiv和AbrahamLempel于1977年提出，所以命名为LZ77。
1.1.1LZ77算法的压缩原理
如果文件中有两块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后一块的内容。
所以我们可以用（两者之间的距离，相同内容的长度）这样一对信息，来替换后一块内容。
由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。
下面我们来举一个例子。
有一个文件的内容如下
其中有些部分的内容，前面已经出现过了，下面用（）括起来的部分就是相同的部分。
（.）nease（.net）
我们使用（两者之间的距离，相同内容的长度）这样一对信息，来替换后一块内容。
（22.13）nease（23,4）
（22.13）中，22为相同内容块与当前位置之间的距离，13为相同内容的长度。
（23,4）中，23为相同内容块与当前位置之间的距离，4为相同内容的长度。
由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。
1.1.2LZ77使用滑动窗口寻找匹配串
LZ77算法使用"滑动窗口"的方法，来寻找文件中的相同部分，也就是匹配串。
我们先对这里的串做一个说明，它是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。
这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化。
LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。
一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节），随着处理的字节不断的向后滑动，就象在阳光下，飞机的影子滑过大地一样。
对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。
窗口中的每个串指，窗口中每个字节开始的串。
如果当前处理字节开始的串在窗口中有匹配串，就用（之间的距离，匹配长度）这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。
如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。
处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任何内容，被处理的字节就会不做改动的输出。
随着处理的不断向后，窗口越来越多的滑入文件，最后整个窗口滑入文件，然后整个窗口在文件上向后滑动，直到整个文件结束。
1.1.3使用LZ77算法进行压缩和解压缩
为了在解压缩时，可以区分“没有匹配的字节”和“（之间的距离，匹配长度）对”，我们还需要在每个“没有匹配的字节”或者“（之间的距离，匹配长度）对”之前，放上一位，来指明是“没有匹配的字节”，还是“（之间的距离，匹配长度）对”。
我们用0表示“没有匹配的字节”，用1表示“（之间的距离，匹
配长度）对”。
实际中，我们将固定（之间的距离，匹配长度）对中的，“之间的距离”和“匹配长度”所使用的位数。
由于我们要固定“之间的距离”所使用的位数，所以我们才使用了固定大小的窗口，比如窗口的大小为
32KB,那么用15位（2T5=32K）就可以保存0-32K范围的任何一个值。
实际中，我们还将限定最大的匹配长度，这样一来，“匹配长度”所使用的位数也就固定了。
实际中，我们还将设定一个最小匹配长度，只有当两个串的匹配长度大于最小匹配长度时，我们才认为是
一个匹配。
我们举一个例子来说明这样做的原因。
比如，“距离”使用15位，“长度”使用8位，那么“（之间的距离，匹配长度）对”将使用23位，也就是差1位3个字节。
如果匹配长度小于3个字节的话，那么用“（之间的距离，匹配长度）对”进行替换的话，不但没有压缩，反而会增大，所以需要一个最小匹配长度。
压缩：
从文件的开始到文件结束，一个字节一个字节的向后进行处理。
用当前处理字节开始的串，和滑动窗口中的每个串进行匹配，寻找最长的匹配串。
如果当前处理字节开始的串在窗口中有匹配串，就先输出一个标志位，表明下面是一个（之间的距离，匹配长度）对，然后输出（之间的距离，匹配长度）对，然后从刚才处理完的串之后的下一个字节，继续处理。
如果当前处理字节开始的串在窗口中没有匹配串，就先输出一个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，然后继续处理当前处理字节的下一个字节。
解压缩：
从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个（之间的距离，匹配长度）对，还是一个没有改动的字节。
如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。
如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。
我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多。
这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。
1.2Huffman编码简介
1.2.1Huffman编码的压缩原理
我们把文件中一定位长的值看作是符号，比如把8位长的256种值，也就是字节的256种值看作是符号。
我们
根据这些符号在文件中出现的频率，对这些符号重新编码。
对于出现次数非常多的，我们用较少的位来表示，对于出现次数非常少的，我们用较多的位来表示。
这样一来，文件的一些部分位数变少了，一些部分位数变多了，由于变小的部分比变大的部分多，所以整个文件的大小还是会减小，所以文件得到了压缩。
1.2.2Huffman编码使用Huffman树来产生编码
要进行Huffman编码，首先要把整个文件读一遍，在读的过程中，统计每个符号（我们把字节的256种值看
作是256种符号）的出现次数。
然后根据符号的出现次数，建立Huffman树，通过Huffman树得到每个符号
的新的编码。
对于文件中出现次数较多的符号，它的Huffman编码的位数比较少。
对于文件中出现次数较少的符号，它的Huffman编码的位数比较多。
然后把文件中的每个字节替换成他们新的编码。
建立Huffman树：
把所有符号看成是一个结点，并且该结点的值为它的出现次数。
进一步把这些结点看成是只有一个结点的树。
每次从所有树中找出值最小的两个树，为这两个树建立一个父结点，然后这两个树和它们的父结点组成一个新的树，这个新的树的值为它的两个子树的值的和。
如此往复，直到最后所有的树变成了一棵树。
我们就得到了一棵Huffman树。
通过Huffman树得到Huffman编码：
这棵Huffman树，是一棵二叉树，它的所有叶子结点就是所有的符号，它的中间结点是在产生Huffman树
的过程中不断建立的。
我们在Huffman树的所有父结点到它的左子结点的路径上标上0，右子结点的路径上标上1。
现在我们从根节点开始，到所有叶子结点的路径，就是一个0和1的序列。
我们用根结点到一个叶子结点路
径上的0和1的序列，作为这个叶子结点的Huffman编码。
我们来看一个例子。
有一个文件的内容如下
abbbbccccddde
我们统计一下各个符号的出现次数，
abcde
14431
建立Huffman树的过程如图：
2.
bc
ae
bc
ae
通过最终的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编码替换成它对应的符号，并输出。
2gzip所使用压缩算法的实现
我们将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位，有2A24种可能值。
而三个字节的
哈希函数的计算结果为15位，有2T5种可能值。
也就是说2A24种值，与2T5种值进行对应，必然是多对一的，也就是说，必然是有多种三个字节的值，用这个哈希函数计算出的值都是相同的。
而我们使用哈希函数的理由是，实际上，我们只是在一个窗口大小的范围内（后面将会看到）寻找匹配串，一个窗口的大小范围是很有限的，能出现的三个字节的值组合情况也是很有限的，将远远小于2A24，使用
合适的哈希函数是高效的。
前三个字节相同的所有的串所在的链：
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[]为空，表示链结束。
我们来举一个例子，串，
0abcdabce,abcf_abcg
当处理到abcg的a时，由abcg的abc算出ins_h这时的head[ins_h]中为11，即串"abcfabcg"的开始位置。
这时的prev[11]中为6，即串"abceabcfabcg"的开始位置。
这时的prev[6]中为1，即串"abcdabceabcfabcg"的开始位置。
这时的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个字节，所以通常不会造成影响，即使影响，也会极小。
例如，文件内容为
jiurljiurl
找到的匹配情况如下，[]所括部分
jiurlj[iurl]
2.2懒惰啊匹配（lazymatch）
对于当前字节开始的串，寻找到了最长匹配之后，gzip并不立即决定使用这个串进行替换。
而是看看这个匹配长度是否满意，如果匹配长度不满意，而下一个字节开始的串也有匹配串的话，那么gzip就找到下一个字节开始的串的最长匹配，看看是不是比现在这个长。
这叫懒惰啊匹配。
如果比现在这个长的话，将不使用现在的这个匹配。
如果比现在这个短的话，将确定使用现在的这个匹配。
我们来举个例子，串
0abcbcdeabcde
处理到第10字节时，也就是"abcde"的a时，找到最长匹配的情况如下，[]所括部分。
0abcbcde[abc]de
这时，再看看下一个字节，也就是第11字节的情况，也就是’abcde"的b，找到最长匹配的情况如下，[]所
括部分。
0abcbcdea[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[]结束的这部分内容，叫做lookaheadbuffer，超前查看缓冲区。
这样叫的原因是，在我们处理当前字节的时候，就需要读出之后的字节来进行串的匹配。
在一个变量lookahead中，保存着超前查看缓冲区所剩的字节数。
lookahead，最开始被初始化为整个读入内容的大小，随着处理的进行，strstart不断后移，超前查看缓冲区不断减小，lookahead的值也不断的减小。
我们需要限制查找匹配串的范围为一个窗口的大小（这么做的原因后面说明），也就是说，只能在当前处理字节之前的32KB的范围内寻找匹配串。
而，由于处理是在2个窗口大小，也就是64KB大小的缓冲区中进行
的，所以匹配链上的串与当前串之间的距离是很有可能超过32KB的。
那么gzip是如何来实现这个限制的
呢？
gzip通过匹配时的判断条件来实现这个限制。
当当前串计算ins_h，发现head[ins_h]值不为空时（head[ins_h]为一个串的开始位置），说明当前串有可能有匹配串，把这个值保存在hash_head中。
这时就要做一个限制范围的判断，strstart-hash_head<=窗口大小，st
升级会员 