Gzip压缩技术以及压缩算法
3星 · 超过75%的资源 需积分: 48 17 浏览量
2011-05-09
21:12:00
上传
评论 1
收藏 27KB DOC 举报 
gzip 压缩算法
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 算法的压缩原理
如果文件中有两块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后
一块的内容。所以我们可以用（两者之间的距离，相同内容的长度）这样一对信息，来替
换后一块内容。由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替
换内容的大小，所以文件得到了压缩。
下面我们来举一个例子。
有一个文件的内容如下
其中有些部分的内容，前面已经出现过了，下面用()括起来的部分就是相同的部分。
(
)nease(.net)
我们使用 (两者之间的距离，相同内容的长度) 这样一对信息，来替换后一块内容。
(22,13)nease(23,4)
(22,13)中，22 为相同内容块与当前位置之间的距离，13 为相同内容的长度。
(23,4)中，23 为相同内容块与当前位置之间的距离，4 为相同内容的长度。
由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，
所以文件得到了压缩。
1.1.2 LZ77 使用滑动窗口寻找匹配串
LZ77 算法使用"滑动窗口"的方法，来寻找文件中的相同部分，也就是匹配串。我们先对这
里的串做一个说明，它是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来
的那些字节的序列。这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变
化。
LZ77 从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口（在
当前处理字节之前，并且紧挨着当前处理字节），随着处理的字节不断的向后滑动，就象
在阳光下，飞机的影子滑过大地一样。对于文件中的每个字节，用当前处理字节开始的串
和窗口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指，窗口中每个字节开
始的串。如果当前处理字节开始的串在窗口中有匹配串，就用(之间的距离，匹配长度) 这
样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。如果
资源评论
xhobitsy2013-06-07百度文库里的，而且不全....
一尘听风2013-03-21怎么没看到接口
