ZIP算法原理（带图解）
需积分: 3 122 浏览量
2013-06-09
17:08:30
上传
评论
收藏 109KB DOC 举报
zip 的算法原理
无损数据压缩是一件奇妙的事情，想一想，一串任意的数据能够根据一定的规则转换成只
有原来 1/2 - 1/5 长度的数据，并且能够按照相应的规则还原到原来的样子，听起来真是很
酷。
原理部分：
有两种形式的重复存在于计算机数据中，zip 就是对这两种重复进行了压缩。
一种是短语形式的重复，即三个字节以上的重复，对于这种重复，zip 用两个数字：1.重复
位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个
字节，于是数据便得到了压缩，这很容易理解。
一个字节有 0 - 255 共 256 种可能的取值，三个字节有 256 * 256 * 256 共一千六百多万种可
能的情况，更长的短语取值的可能情况以指数方式增长，出现重复的概率似乎极低，实则
不然，各种类型的数据都有出现重复的倾向，一篇论文中，为数不多的术语倾向于重复出
现；一篇小说，人名和地名会重复出现；一张上下渐变的背景图片，水平方向上的像素会
重复出现； 程序的源文件中，语法关键字会重复出现（我们写程序时，多少次前后
copy、paste？），以几十 K 为单位的非压缩格式的数据中，倾向于大量出现短语式的重复。
经过上面提到的方式进行压缩后，短语式重复的倾向被完全破坏，所以在压缩的结果上进
行第二次短语式压缩一般是没有效果的。
第二种重复为单字节的重复，一个字节只有 256 种可能的取值，所以这种重复是必然的。
其中，某些字节出现次数可能较多，另一些则较少，在统计上有分布不均匀的倾向，这是
容易理解的，比如一个 ASCII 文本文件中，某些符号可能很少用到，而字母和数字则使用
较多，各字母的使用频率也是不一样的，据说字母 e 的使用概率最高；许多图片呈现深色
调或浅色调，深色（或浅色）的像素使用较多（这里顺便提一下：png 图片格式是一种无
损压缩，其核心算法就是 zip 算法，它和 zip 格式的文件的主要区别在于：作为一种图片格
式，它在文件头处存放了图片的大小、使用的颜色数等信息）；上面提到的短语式压缩的
结果也有这种倾向：重复倾向于出现在离当前压缩位置较近的地方，重复长度倾向于比较
短（20 字节以内）。这样，就有了压缩的可能：给 256 种字节取值重新编码，使出现较多
的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于
变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越
大。
在进一步讨论编码的要求以及办法前，先提一下：编码式压缩必须在短语式压缩之后进行
因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向
也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单
双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺
序不能变。
剩余12页未读，继续阅读
资源评论
