正在阅读：Gzip Zlib PNG 压缩算法,源码详解Gzip Zlib PNG 压缩算法,源码详解

2004-03-03 10:03 出处：CSDN 作者：JIURL 责任编辑：linjixiong

在本页浏览全文

gzip,zlib,以及图形格式png，使用的是同一个压缩算法deflate。我们通过对gzip源码的分析来对deflate压缩算法做一个详细的说明。我阅读的gzip版本为 gzip-1.2.4。我们对算法做三种程度的说明。第一种程度，对gzip所使用压缩算法基本原理的说明。第二种程度，对gzip压缩算法实现方法的说明。第三种程度，对gzip实现源码级的说明。　　　　如果你有时间的话，我建议你先不要看下面的内容，自己尝试通过读gzip源码，来了解它的压缩解压缩是如何实现的，这将会是一个非常有趣的智力游戏，千万不要错过。当一个又一个的谜被解开时，那感觉就像唐伯虎同志所说的，“慷慨然诺杯酒中”。（小唐的诗，除了另一个倒霉蛋曹雪芹外，好像不太被人提。）　　　　1 gzip所使用压缩算法的基本原理　　　　gzip 对于要压缩的文件，首先使用lz77算法进行压缩，对得到的结果再使用huffman编码的方法进行压缩。所以我们分别对lz77和huffman编码的原理进行说明。　　　　1.1 ... 1.2 ... 　　　　2 gzip压缩算法实现方法　　　　2.1 LZ77算法的gzip实现　　　　首先，gzip 从要压缩的文件中读入64KB的内容到一个叫window的缓冲区中。为了简单起见，我们以32KB以下文件的压缩为例做说明。对于我们这里使用32KB以下文件，gzip将整个文件读入到window缓冲区中。然后使用一个叫strstart的变量在window数组中，从0开始一直向后移动。strstart在每一个位置上，都在它之前的区域中，寻找和当前strstart开始的串的头3个字节匹配的串，并试图从这些匹配串中找到最长的匹配串。　　　　如果当前的strstart开始的串，可以找到最少为3个字节的匹配串的话，当前的strstart开始的匹配长度那么长的串，将会被一个<匹配长度,到匹配串开头的距离>对替换。　　　　如果当前的strstart开始的串，找不到任何的最少为3个字节的匹配串的话，那么当前strstart的所在字节将不作改动。　　　　为了区分是一个<匹配长度,到匹配串开头的距离>对，还是一个没有被改动的字节，还需要为每一个没有被改动的字节或者<匹配长度,到匹配串开头的距离>对，另外再占用一　　位，来进行区分。这位如果为1，表示是一个<匹配长度,到匹配串开头的距离>对，这位如果为0，表示是一个没有被改动的字节。　　　　现在来说明一下，为什么最小匹配为3个字节。这是由于，gzip 中，<匹配长度,到匹配串开头的距离>对中，"匹配长度"的范围为3-258，也就是256种可能值，需要8bit来保存。"到匹配串开头的距离"的范围为0-32K，需要15bit来保存。所以一个<匹配长度,到匹配串开头的距离>对需要23位，差一位3个字节。如果匹配串小于3个字节的话，使用<匹配长度,到匹配串开头的距离>对进行替换，不但没有压缩，反而还会增大。所以保存<匹配长度,到匹配串开头的距离>对所需要的位数，决定了最小匹配长度至少要为3个字节。　　　　下面我们就来介绍gzip如何实现寻找当前strstart开始的串的最长匹配串。　　　　如果每次为当前串寻找匹配串时，都要和之前的每个串的至少3个字节进行比较的话，那么比较量将是非常非常大的。为了提高比较速度，gzip使用了哈希表。这是gzip实现LZ77的关键。这个哈希表是一个叫head的数组（后面我们将看到为什么这个缓冲区叫head）。gzip对windows中的每个串，使用串的头三个字节，也就是strstart,strstart+1,strstart+2，用一个设计好的哈希函数来进行计算，得到一个插入位置ins_h。也就是用串的头三个字节来确定一个插入位置。然后把串的位置，也就是 strstart的值，保存在head数组的第ins_h项中。我们马上就可以看到为什么要这样做。head数组在没有插入任何值时，全部为0。

察看评论详细内容我要发表评论