《lz77压缩算法详解》由会员分享，可在线阅读，更多相关《lz77压缩算法详解（21页珍藏版）》请在金锄头文库上搜索。
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、子。有一个文件的内容如下http:/ http:/其中有些部分的内容，前面已经出现过了，下面用()括起来的部分就是相同的部分。http:/ (http:/jiurl.)nease(.net)我们使用 (两者之间的距离，相同内容的长度) 这样一对信息，来替换后一块内容。http:/ (22,13)nease(23,4)(22,13)中，22为相同内容块与当前位置之间的距离，13为相同内容的长度。(23,4)中，23为相同内容块与当前位置之间的距离，4为相同内容的长度。由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。1.1.2 LZ77使用滑动窗口
4、寻找匹配串LZ77算法使用滑动窗口的方法，来寻找文件中的相同部分，也就是匹配串。我们先对这里的串做一个说明，它是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化。LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节） ，随着处理的字节不断的向后滑动，就象在阳光下，飞机的影子滑过大地一样。对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指，窗口中每个字节开始的串。如果当前处理字节开始的
5、串在窗口中有匹配串，就用(之间的距离，匹配长度) 这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任何内容，被处理的字节就会不做改动的输出。随着处理的不断向后，窗口越来越多的滑入文件，最后整个窗口滑入文件，然后整个窗口在文件上向后滑动，直到整个文件结束。1.1.3 使用 LZ77算法进行压缩和解压缩为了在解压缩时，可以区分“没有匹配的字节”和“（之间的距离，匹配长度）对” ，我们还需要在每个“没有匹配的字
6、节”或者“（之间的距离，匹配长度）对”之前，放上一位，来指明是“没有匹配的字节”，还是“（之间的距离，匹配长度）对” 。我们用0表示“没有匹配的字节” ，用1表示“（之间的距离，匹配长度）对” 。实际中，我们将固定（之间的距离，匹配长度）对中的， “之间的距离”和“匹配长度”所使用的位数。由于我们要固定“之间的距离”所使用的位数，所以我们才使用了固定大小的窗口，比如窗口的大小为32KB，那么用15位（215=32K）就可以保存0-32K 范围的任何一个值。实际中，我们还将限定最大的匹配长度，这样一来， “匹配长度”所使用的位数也就固定了。实际中，我们还将设定一个最小匹配长度，只有当两个串的匹配
7、长度大于最小匹配长度时，我们才认为是一个匹配。我们举一个例子来说明这样做的原因。比如， “距离”使用15位， “长度”使用8位，那么“（之间的距离，匹配长度）对”将使用23位，也就是差1位3个字节。如果匹配长度小于3个字节的话，那么用“（之间的距离，匹配长度）对”进行替换的话，不但没有压缩，反而会增大，所以需要一个最小匹配长度。压缩：从文件的开始到文件结束，一个字节一个字节的向后进行处理。用当前处理字节开始的串，和滑动窗口中的每个串进行匹配，寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串，就先输出一个标志位，表明下面是一个(之间的距离，匹配长度) 对，然后输出(之间的距离，匹配长度
8、) 对，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就先输出一个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，然后继续处理当前处理字节的下一个字节。解压缩：从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个(之间的距离，匹配长度) 对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时
9、需要做的工作很少，也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。1.2 Huffman 编码简介1.2.1 Huffman 编码的压缩原理我们把文件中一定位长的值看作是符号，比如把8位长的256种值，也就是字节的256种值看作是符号。我们根据这些符号在文件中出现的频率，对这些符号重新编码。对于出现次数非常多的，我们用较少的位来表示，对于出现次数非常少的，我们用较多的位来表示。这样一来，文件的一些部分位数变少了，一些部分位数变多了，由于变小的部分比变大的部分多，所以整个文件的大小还是会减小，所以文件得到了压缩。1.2.2 Huffman 编码使用
10、Huffman 树来产生编码要进行 Huffman 编码，首先要把整个文件读一遍，在读的过程中，统计每个符号（我们把字节的256种值看作是256种符号）的出现次数。然后根据符号的出现次数，建立 Huffman 树，通过 Huffman 树得到每个符号的新的编码。对于文件中出现次数较多的符号，它的 Huffman 编码的位数比较少。对于文件中出现次数较少的符号，它的 Huffman 编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。建立 Huffman 树：把所有符号看成是一个结点，并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树。每次从所有树中找出值最小的两个树，
11、为这两个树建立一个父结点，然后这两个树和它们的父结点组成一个新的树，这个新的树的值为它的两个子树的值的和。如此往复，直到最后所有的树变成了一棵树。我们就得到了一棵 Huffman 树。通过 Huffman 树得到 Huffman 编码：这棵 Huffman 树，是一棵二叉树，它的所有叶子结点就是所有的符号，它的中间结点是在产生 Huffman 树的过程中不断建立的。我们在 Huffman 树的所有父结点到它的左子结点的路径上标上0，右子结点的路径上标上1。现在我们从根节点开始，到所有叶子结点的路径，就是一个0和1的序列。我们用根结点到一个叶子结点路径上的0和1的序列，作为这个叶子结点的 Huf
12、fman 编码。我们来看一个例子。有一个文件的内容如下abbbbccccddde我们统计一下各个符号的出现次数，a b c d e1 4 4 3 1建立 Huffman 树的过程如图：通过最终的 Huffman 树，我们可以得到每个符号的 Huffman 编码。a 为 110b 为 00c 为 01d 为 10e 为 111我们可以看到，Huffman 树的建立方法就保证了，出现次数多的符号，得到的 Huffman 编码位数少，出现次数少的符号，得到的 Huffman 编码位数多。各个符号的 Huffman 编码的长度不一，也就是变长编码。对于变长编码，可能会遇到一个问题，就是重新编码的文件中
13、可能会无法如区分这些编码。比如，a 的编码为000，b 的编码为0001，c 的编码为1，那么当遇到0001时，就不知道0001代表 ac，还是代表 b。出现这种问题的原因是 a 的编码是 b 的编码的前缀。由于 Huffman 编码为根结点到叶子结点路径上的0和1的序列，而一个叶子结点的路径不可能是另一个叶子结点路径的前缀，所以一个 Huffman 编码不可能为另一个 Huffman 编码的前缀，这就保证了 Huffman 编码是可以区分的。1.2.3 使用 Huffman 编码进行压缩和解压缩为了在解压缩的时候，得到压缩时所使用的 Huffman 树，我们需要在压缩文件中，保存树的信息，也
14、就是保存每个符号的出现次数的信息。压缩：读文件，统计每个符号的出现次数。根据每个符号的出现次数，建立 Huffman 树，得到每个符号的Huffman 编码。将每个符号的出现次数的信息保存在压缩文件中，将文件中的每个符号替换成它的Huffman 编码，并输出。解压缩：得到保存在压缩文件中的，每个符号的出现次数的信息。根据每个符号的出现次数，建立 Huffman 树，得到每个符号的 Huffman 编码。将压缩文件中的每个 Huffman 编码替换成它对应的符号，并输出。2 gzip 所使用压缩算法的实现我们将 gzip 的实现分成很多个部分，一个个来说明，这样做的原因见本文最后一部分。gzip
15、 中所使用的各种实现技巧的出处或者灵感，gzip 的作者在源码的注释中进行了说明。2.1 寻找匹配串的实现为一个串寻找匹配串需要进行大量的匹配工作，而且我们还需要为很多很多个串寻找匹配串。所以 gzip 在寻找匹配串的实现中使用哈希表来提高速度。要达到的目标是，对于当前串，我们要在它之前的窗口中，寻找每一个匹配长度达到最小匹配的串，并找出匹配长度最长的串。在 gzip 中，最小匹配长度为3，也就是说，两个串，最少要前3个字节相同，才能算作匹配。为什么最小匹配长度为3，将在后面说明。gzip 对遇到的每一个串，首先会把它插入到一个“字典”中。这样当以后有和它匹配的串，可以直接从“字典”中查出这个
16、串。插入不是乱插，查也不是乱查。插入的时候，使用这个插入串的前三个字节，计算出插入的“字典”位置，然后把插入串的开始位置保存在这个“字典”位置中。查出的时候，使用查出串的前三个字节，计算出“字典”位置，由于插入和查出使用的是同一种计算方法，所以如果两个串的前三个字节相同的话，计算出的“字典”位置肯定是相同的，所以就可以直接在该“字典”位置中，取出以前插入时，保存进去的那个串的开始位置。于是查出串，就找到了一个串，而这个串的前三个字节和自己的一样（其实只是有极大的可能是一样的，原因后面说明） ，所以就找到了一个匹配串。如果有多个串，他们的前三个字节都相同，那么他们的“字典”位置，也都是相同的，他们将被链成一条链，放在那个“字典”位置上。所以，如果一个串，查到了一个“字典”位置，也就查到了一个链，所有和它前三个字节相同的串，都在这个链上。也就是说，当前串之前的所有匹配串被链在了一个链上，放在某个“字典”
