无损数据压缩分析

无损数据压缩分析

无损数据压缩分析

在网上看到的，不知道作者，觉得不错，就转了过来。


无损数据压缩是一件奇妙的事情，想一想，一串任意的数据能够根据一定的规则转换成只有原来 1/2 - 1/5 长度的数据，并且能够按照相应的规则还原到原来的样子，听起来真是很酷。
半年前，苦熬过初学 vc 时那段艰难的学习曲线的我，对 MFC、SDK 开始失望和不满，这些虽然不算易学，但和 DHTML 没有实质上的区别，都是调用微软提供的各种各样的函数，不需要你自己去创建一个窗口，多线程编程时，也不需要你自己去分配 CPU 时间。我也做过驱动，同样，有DDK（微软驱动开发包），当然，也有 DDK 的“参考手册”，连一个最简单的数据结构都不需要你自己做，一切都是函数、函数……
微软的高级程序员编写了函数让我们这些搞应用的去调用，我不想在这里贬低搞应用的人，正是这些应用工程师连接起了科学和社会之间的桥梁，将来可以做销售，做管理，用自己逐渐积累起来的智慧和经验在社会上打拼。
但是，在技术上来说，诚实地说，这并不高深，不是吗？第一流的公司如微软、Sybase、Oracle 等总是面向社会大众的，这样才能有巨大的市场。但是他们往往也是站在社会的最顶层的：操作系统、编译器、数据库都值得一代代的专家去不断研究。这些帝国般的企业之所以伟大，恐怕不是“有经验”、“能吃苦”这些中国特色的概念所能涵盖的，艰深的技术体系、现代的管理哲学、强大的市场能力都是缺一不可的吧。我们既然有志于技术，并且正在起步阶段，何必急不可耐地要转去做“管理”，做“青年才俊”，那些所谓的“成功人士”的根底能有几何，这样子浮躁，胸中的规模和格局能有多大？

在我发现vc只是一个用途广泛的编程工具，并不能代表“知识”、“技术”的时候，我有些失落，无所不能的不是我，而是 MFC、SDK、DDK，是微软的工程师，他们做的，正是我想做的，或者说，我也想成为那种层次的人，现在我知道了，他们是专家，但这不会是一个梦，有一天我会做到的，为什么不能说出我的想法呢。
那时公司做的系统里有一个压缩模块，领导找了一个 zlib 库，不让我自己做压缩算法，站在公司的立场上，我很理解，真的很理解，
自己做算法要多久啊。但那时自己心中隐藏的一份倔强驱使我去寻找压缩原理的资料，我完全没有意识到，我即将打开一扇大门，进入一个神奇的“数据结构”的世界。“计算机艺术”的第一线阳光，居然也照到了我这样一个平凡的人的身上。

上面说到“计算机艺术”，或者进一步细化说“计算机编程艺术”，听起来

无损数据压缩分析

很深奥，很高雅，但是在将要进入专业的压缩算法的研究时，我要请大家做的第一件事情是：忘掉自己的年龄、学历，忘掉自己的社会身份，忘掉编程语言，忘掉“面向对象”、“三层架构”等一切术语。把自己当作一个小孩，有一双求知的眼睛，对世界充满不倦的、单纯的好奇，唯一的前提是一个正常的具有人类理性思维能力的大脑。
下面就让我们开始一段神奇的压缩算法之旅吧：


1. 原理部分：
　　有两种形式的重复存在于计算机数据中，zip 就是对这两种重复进行了压缩。
　　一种是短语形式的重复，即三个字节以上的重复，对于这种重复，zip用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩，这很容易理解。
　　一个字节有 0 - 255 共 256 种可能的取值，三个字节有 256 * 256 * 256 共一千六百多万种可能的情况，更长的短语取值的可能情况以指数方式增长，出现重复的概率似乎极低，实则不然，各种类型的数据都有出现重复的倾向，一篇论文中，为数不多的术语倾向于重复出现；一篇小说，人名和地名会重复出现；一张上下渐变的背景图片，水平方向上的像素会重复出现；程序的源文件中，语法关键字会重复出现（我们写程序时，多少次前后copy、paste？），以几十 K 为单位的非压缩格式的数据中，倾向于大量出现短语式的重复。经过上面提到的方式进行压缩后，短语式重复的倾向被完全破坏，所以在压缩的结果上进行第二次短语式压缩一般是没有效果的。
　　第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。其中，某些字节出现次数可能较多，另一些则较少，在统计上有分布不均匀的倾向，这是容易理解的，比如一个 ASCII 文本文件中，某些符号可能很少用到，而字母和数字则使用较多，各字母的使用频率也是不一样的，据说字母 e 的使用概率最高；许多图片呈现深色调或浅色调，深色（或浅色）的像素使用较多（这里顺便提一下：png 图片格式是一种无损压缩，其核心算法就是 zip 算法，它和 zip 格式的文件的主要区别在于：作为一种图片格式，它在文件头处存放了图片的大小、使用的颜
色数等信息）；上面提到的短语式压缩的结果也有这种倾向：重复倾向于出现在离当前压缩位置较近的地方，重复长度倾向于比较短（20字节以内）。这样，就有了压缩的可能：给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节

无损数据压缩分析

更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。
　　在进一步讨论编码的要求以及办法前，先提一下：编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。
　　在编码式压缩后，以连续的八位作为一个字节，原先未压缩文件中所具有的字节取值不均匀的倾向被彻底破坏，成为随机性取值，根据统计学知识，随机性取值具有均匀性的倾向（比如抛硬币试验，抛一千次，正反面朝上的次数都接近于 500 次）。因此，编码式压缩后的结果无法再进行编码式压缩。
　　短语式压缩和编码式压缩是目前计算机科学界研究出的仅有的两种无损压缩方法，它们都无法重复进行，所以，压缩文件无法再次压缩（实际上，能反复进行的压缩算法是不可想象的，因为最终会压缩到 0 字节）。
　　短语式重复的倾向和字节取值分布不均匀的倾向是可以压缩的基础，两种压缩的顺序不能互换的原因也说了，下面我们来看编码式压缩的要求及方法：

首先，为了使用不定长的编码表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀，反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位 0 或 1 组成，否则解压缩程序将无法解码。
看一下前缀编码的一个最简单的例子：


符号 编码
A 0
B 10
C 110
D 1110
E 11110

有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：

1110010101110110111100010 - DABBDCEAAB

要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：

　　　　　　　　根(root)
　　　　　　 0　　|　　 1
　　　　 　 +-------+--------+
　　　　0　 |　1　　 0 　|　 1
　 　 +-----+------+　+----+----+
　 　 |　　　　　|　|　 　　 |
　 　 a　　 　　 |　d 　　　 e
　　　　　0　　|　　1
　　　　　+--
---+-----+
　　　　　|　　　　 |
　　　　　b　　 　　c

要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为0，右转为1，则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径

无损数据压缩分析

，符合要求的前缀编码也就构造成功了：

a - 00 b - 010 c - 011 d - 10 e - 11


接下来来看编码式压缩的过程：
为了简化问题，假定一个文件中只出现了 a，b，c，d ，e五种字符，它们的出现次数分别是
a : 6次
b : 15次
c : 2次
d : 9次
e : 1次
如果用定长的编码方式为这四种字符编码： a : 000 b : 001 c : 010 d : 011 e : 100
那么整个文件的长度是 3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99

用二叉树表示这四种编码(其中叶子节点上的数字是其使用次数，非叶子节点上的数字是其左右孩子使用次数之和):

　　　　　　　　 　根
　　　　　　　　 　 |
　　　　　　+---------33---------+
　　　　　　|　　　　　　 　|
　　 +----32---+　　　　 +----1---+
　　 |　　　　|　 　　　|　　　 |
+-21-+ 　 +-11-+ 　 　+--1--+　　
|　　 | 　 |　　 | 　 　|　　 |
6　 15 　2　　9 　 　1　　　

（如果某个节点只有一个子节点，可以去掉这个子节点。）

　　　　　　　　 根
　　　　　　　　　|
　 　 　　　 +------33------+
　　　　　　 |　　　　　|
　 　 +-----32----+ 　 　 1
　 　 |　　　 　 |
　 +--21--+ 　+--11--+
　 |　　　|　 |　　　|
　 6 　　15　2　 　 9

现在的编码是： a : 000 b : 001 c : 010 d : 011 e : 1 仍然符合“前缀编码”的要求。

第一步：如果发现下层节点的数字大于上层节点的数字，就交换它们的位置，并重新计算非叶子节点的值。
先交换11和1，由于11个字节缩短了一位，1个字节增长了一位，总文件缩短了10位。

　　　　　　　　　　 根
　 　 　　　　　　　　|
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　 +-----22----+　　　　　+----11----+
　　 | 　　 　　|　　　　　|　　　　 |
+--21--+　　　 1　 　 　　2　　　　 9
| 　 　 |
6　　 15

再交换15和1、6和2，最终得到这样的树：

　　　　　　　　　　 根
　　　　　 　　　　 　|
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　 　 +-----18----+　　　 +----15----+
　　　 | 　　 　　|　　　 |　　　　 |
　　+--3--+ 　 　15　　　6　　　　 9
　　|　 　|
　　2　　 1

这时所有上层节点的数值都大于下层节点的数值，似乎无法再进
一步压缩了。但是我们把每一层的最小的两个节点结合起来，常会发现仍有压缩余地。

第二步：把每一层的最小的两个节点结合起来，重新计算相关节点的值。

在上面的树中，第一、二、四三层都只有一或二个节点，无法重新组合，但第三层上有四个节点，我们把最小的3和6结合起来，并重新计算相关节点

无损数据压缩分析

的值，成为下面这棵树。

　　　　　　　　　　 根
　　　　　 　　　　 　|
　　　　　　 +----------33---------+
　　　　　　 | 　　　　　　　 |
　　　 +------9-----+　　　 +----24----+
　　　 |　 　　 　|　　　 |　　　　 |
　　 +--3--+　 　 6　　　15　　　　9
　　 |　　 |
　　2　　1

然后，再重复做第一步。
这时第二层的9小于第三层的15，于是可以互换，有9个字节增长了一位，15个字节缩短了一位，文件总长度又缩短了6位。然后重新计算相关节点的值。

　　　　　　　　　　 根
　　　　 　　　　　　 |
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　　　　　 15　　　　 +----18----+　
　　　　　　　　　　　　|　　　　|
　　　　　　　　　+------9-----+　　 9
　　　　　　　　　|　 　　　 |
　 　　　　　 　+--3--+　　　6
　　 　　　　 　|　　 |
　　　　 　　　 2　　1

这时发现所有的上层节点都大于下层节点，每一层上最小的两个节点被并在了一起，也不可能再产生比同层其他节点更小的父节点了。

这时整个文件的长度是 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

这时可以看出编码式压缩的一个基本前提：各节点之间的值要相差比较悬殊，以使某两个节点的和小于同层或下层的另一个节点，这样，交换节点才有利益。
所以归根结底，原始文件中的字节使用频率必须相差较大，否则将没有两个节点的频率之和小于同层或下层其他节点的频率，也就无法压缩。反之，相差得越悬殊，两个节点的频率之和比同层或下层节点的频率小得越多，交换节点之后的利益也越大。

在这个例子中，经过上面两步不断重复，得到了最优的二叉树，但不能保证在所有情况下，都能通过这两步的重复得到最优二叉树，下面来看另一个例子：

　　　　　　　　　　　　　　　　　　　　　　　　　根
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－１９－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－１２－－－－－－＋　　　　　　　　　　　　７
　　　　
　　｜　　　　　　　　　　　　　　｜
　　＋－－－５－－－＋　　　　　　＋－－－７－－－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜
＋－２－＋　　　＋－３－＋　　＋－３－＋　　　＋－４－＋
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
１　　　１　　　

无损数据压缩分析

１　　　２　　１　　　２　　　２　　　２

这个例子中，所有上层节点都大于等于下层节点，每一层最小的两个节点结合在了一起，但仍然可以进一步优化：


　　　　　　　　　　　　　　　　　　　　　　　　　根
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－１９－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－１２－－－－－－＋　　　　　　　　　　　　７
　　　　　　｜　　　　　　　　　　　　　　｜
　　＋－－－４－－－＋　　　　　　＋－－－８－－－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜
＋－２－＋　　　＋－２－＋　　＋－４－＋　　　＋－４－＋
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
１　　　１　　　１　　　１　　２　　　２　　　２　　　２

通过最低一层的第４第５个节点对换，第３层的８大于第２层的７。
到这里，我们得出这样一个结论：一棵最优二叉编码树（所有上层节点都无法和下层节点交换），必须符合这样两个条件：
１．所有上层节点都大于等于下层节点。
２．某节点，设其较大的子节点为ｍ，较小的子节点为ｎ，ｍ下的任一层的所有节点都应大于等于ｎ下的该层的所有节点。

当符合这两个条件时，任一层都无法产生更小的节点去和下层节点交换，也无法产生更大的节点去和上层节点交换。

上面的两个例子是比较简单的，实际的文件中，一个字节有256种可能的取值，所以二叉树的叶子节点多达256个，需要不断的调整树形，最终的树形可能非常复杂，有一种非常精巧的算法可以快速地建起一棵最优二叉树，这种算法由D.Huffman（戴·霍夫曼）提出，下面我们先来介绍霍夫曼算法的步骤，然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。

霍夫曼算法的步骤是这样的：

·从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。
·然后从节点序列中去除这两个节点，加入它们的父节点到序列中。

重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节
点。

仍以上面的例子来看霍夫曼树的建立过程。
最初的节点序列是这样的：
a(6) 　b(15) 　c(2) 　d(9) 　e(1)

把最小的c和e结合起来
　　　　　　　　　　　　 　　 　 　| (3)
a(6) 　　b(15) 　　d(9)　　　+------+-

无损数据压缩分析

-----+
　　　　　　　　　　　　　　|　　 　　　|
　　　　　　　　　　　　　　c　　　　　e

不断重复，最终得到的树是这样的：

　　 　　　 根
　 　 　　　 |
　 　+-----33-----+
　　　|　　　　　|
　　　15　　 +----18----+　　　
　　　　　　 | 　 　 　 |
　　　　　　 9　 +------9-----+
　 　　 　　　　　|　　 　 　 |
　　　　　　　　 6 　　 　+--3--+
　　 　　　　　　　　　 　|　　 |
　　　　 　　　 　　　　　2　　1

这时各个字符的编码长度和前面我们说过的方法得到的编码长度是相同的，因而文件的总长度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼树的建立过程中的每一步的节点序列的变化：

6 　15　2　9　1
6　 15　9　3
15　9　 9
15　18
33

下面我们用逆推法来证明对于各种不同的节点序列，用霍夫曼算法建立起来的树总是一棵最优二叉树：

对霍夫曼树的建立过程运用逆推法：
当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。
然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：
1.按照霍夫曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。
2.这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。
3.只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。

这样一步步逆推下去，在这个过程中霍夫曼树每一步都始终保持着是一棵最优二叉树。

由于每一步都从节点序列中删除两个节点，新增一个节点，霍夫曼树
的建立过程共需 (原始节点数 - 1) 步，所以霍夫曼算法不失为一种精巧的编码式压缩算法。


附：对于 huffman 树，《计算机程序设计艺术》中有完全不同的证明，大意是这样的：
１．二叉编码树的内部节点（非叶子节点）数等于外部节点（叶子节点）数减１。
２．二叉编码树的外部

无损数据压缩分析

节点的加权路径长度（值乘以路径长度）之和，等于所有内部节点值之和。（这两条都可以通过对节点数运用数学归纳法来证明，留给大家做练习。）
３．对 huffman 树的建立过程运用逆推，当只有一个内部节点时，肯定是一棵最优二叉树。
４．往前步进，新增两个最小的外部节点，它们结合在一起产生一个新的内部节点，当且仅当原先的内部节点集合是极小化的，加入这个新的内部节点后仍是极小化的。（因为最小的两个节点结合在一起，并处于最低层，相对于它们分别和其他同层或上层节点结合在一起，至少不会增加加权路径长度。）
５．随着内部节点数逐个增加，内部节点集合总维持极小化。




２．实现部分
　　如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析 zip 算法是如何解决这些难题的，其中很多问题带有普遍意义，比如查找匹配，比如数组排序等等，这些都是说不尽的话题，让我们深入其中，做一番思考


我们前面说过，对于短语式重复，我们用“重复距当前位置的距离”和“重复的长度”这两个数字来表示这一段重复，以实现压缩，现在问题来了，一个字节能表示的数字大小为 0 －255，然而重复出现的位置和重复的长度都可能超过 255，事实上，二进制数的位数确定下来后，所能表示的数字大小的范围是有限的，ｎ位的二进制数能表示的最大值是２的ｎ次方减１，如果位数取得太大，对于大量的短匹配，可能不但起不到压缩作用，反而增大了最终的结果。针对这种情况，有两种不同的算法来解决这个问题，它们是两种不同的思路。一种称为 lz77 算法，这是一种很自然的思路：限制这两个数字的大小，以取得折衷的压缩效果。例如距离取 15 位，长度取 8 位，这样，距离的最大取值为 32 k - 1，长度的最大取值为 255，这两个数字占 23 位，比三个字节少一位，是符合压缩的要求的。让我们在头脑中想象一下 lz77 算法压缩进行时的情况，会出现有意思的模型：

　　　最远匹配位置－＞　　　　　　　　
　　当前处理位置－＞
───┸─────────────────╂─────────────＞压缩进行方向
　　　已压缩部分　　　　　　　　　　　　　┃　　　　未压缩部分

　　在最远匹配位置和当前处理位置之间是可以用来查找匹配的“字典”区域，随着压缩的进行，“字典”区域从待压缩

无损数据压缩分析

文件的头部不断地向后滑动，直到达到文件的尾部，短语式压缩也就结束了。
　　解压缩也非常简单：

　　　　　　　　　┎────────拷贝────────┒
　匹配位置　　　　┃　　　　　　　　　　当前处理位置　　┃
　　　┃＜──匹配长度──＞┃　　　　　　　┠─────∨────┨
───┸──────────┸───────╂──────────┸─＞解压进行方向
　　　已解压部分　　　　　　　　　　　　　　┃　　　　未解压部分

　　不断地从压缩文件中读出匹配位置值和匹配长度值，把已解压部分的匹配内容拷贝到解压文件尾部，遇到压缩文件中那些压缩时未能得到匹配，而是直接保存的单、双字节，解压时只要直接拷贝到文件尾部即可，直到整个压缩文件处理完毕。
　　lz77算法模型也被称为“滑动字典”模型或“滑动窗口”模型。
　　另有一种lzw算法对待压缩文件中存在大量简单匹配的情况进行了完全不同的算法设计，它只用一个数字来表示一段短语，下面来描述一下lzw的压缩解压过程，然后来综合比较两者的适用情况。
　　lzw的压缩过程：
1) 初始化一个指定大小的字典，把 256 种字节取值加入字典。
2) 在待压缩文件的当前处理位置寻找在字典中出现的最长匹配，输出该匹配在字典中的序号。
3) 如果字典没有达到最大容量，把该匹配加上它在待压缩文件中的下一个字节加入字典。
4) 把当前处理位置移到该匹配后。
5) 重复 2、3、4 直到文件输出完毕。

　　lzw 的解压过程：
1) 初始化一个指定大小的字典，把 256 种字节取值加入字典。
2) 从压缩文件中顺序读出一个字典序号，根据该序号，把字典中相应的数据拷贝到解压文件尾部。
3) 如果字典没有达到最大容量，把前一个匹配内容加上当前匹配的第一个字节加入字典。
4) 重复 2、3 两步直到压缩文件处理完毕。

　　从 lzw 的压缩过程，我们可以归纳出它不同于 lz77 算法的一些主要特点：
1) 对于一段短语，它只输出一个数字，即字典中的序号。（这个数字的位数决定了字典的最大容量，当它的位数取得太大时，比如 24 位以上，对于短匹配占多数的情况，压缩率可能很低。取得太小时，比如 8 位，字典的容量受到限制。所以同样
需要取舍。）
2) 对于一个短语，比如 abcd ，当它在待压缩文件中第一次出现时，ab 被加入字典，第二次出现时，abc 被加入字典，第三次出现时，abcd 才会被加入字典，对于一些长匹配，它必须高频率地出现，并且字典有较大的容量，才会被最终完整地加入字典。相应地，lz77 只要匹配

无损数据压缩分析

在“字典区域”中存在，马上就可以直接使用。
3) 设 lzw 的“字典序号”取 n 位，它的最大长度可以达到 2 的 n 次方；设 lz77 的“匹配长度”取 n 位，“匹配距离”取 d 位，它的最大长度也是 2 的 n 次方，但还要多输出 d 位（d 至少不小于 n），从理论上说 lzw 每输出一个匹配只要 n 位，不管是长匹配还是短匹配，压缩率要比 lz77 高至少一倍，但实际上，lzw 的字典中的匹配长度的增长由于各匹配互相打断，很难达到最大值。而且虽然 lz77 每一个匹配都要多输出 d 位，但 lzw 每一个匹配都要从单字节开始增长起，对于种类繁多的匹配，lzw 居于劣势。
　　可以看出，在多数情况下，lz77 拥有更高的压缩率，而在待压缩文件中占绝大多数的是些简单的匹配时，lzw 更具优势，GIF 就是采用了 lzw 算法来压缩背景单一、图形简单的图片。zip 是用来压缩通用文件的，这就是它采用对大多数文件有更高压缩率的 lz77 算法的原因。

　　接下来 zip 算法将要解决在“字典区域”中如何高速查找最长匹配的问题。


注：以下关于技术细节的描述是以 gzip 的公开源代码为基础的，如果需要完整的代码，可以在 gzip 的官方网站 http:// 下载。下面提到的每一个问题，都首先介绍最直观简单的解决方法，然后指出这种方法的弊端所在，最后介绍 gzip 采用的做法，这样也许能使读者对 gzip 看似复杂、不直观的做法的意义有更好的理解。）
最直观的搜索方式是顺序搜索：以待压缩部分的第一个字节与窗口中的每一个字节依次比较，当找到一个相等的字节时，再比较后续的字节…… 遍历了窗口后得出最长匹配。gzip 用的是被称作“哈希表”的方法来实现较高效的搜索。“哈希（hash）”是分散的意思，把待搜索的数据按照字节值分散到一个个“桶”中，搜索时再根据字节值到相应的“桶”中去寻找。短语式压缩的最短匹配为 3 个字节，gzip 以 3 个字节的值作为哈希表的索引，但 3 个字节共有 2 的 24 次方种取值，需要 16M 个桶，桶里存放的是窗口中的位置值，窗口的大小为 32K，所以每个桶至少要有大于两个字节的空间，哈希表将大于 32M，作为 90 年代开发的程序，这个要求是太大了，而且随着窗口的移动，哈希表里的数据会不断过时，维护这么大的表，会降低程序的效率，gzi
p 定义哈希表为 2 的 15 次方（32K）个桶，并设计了一个哈希函数把 16M 种取值对应到 32K 个桶中，不同的值被对应到相同的桶中是不可避免的，哈希函数的任务是 1.使各种取值尽可能均匀地分布到各个桶中，避免许多不同的值集中到某些桶中，而另一些是空桶，使搜索的效率降低。2.函数

无损数据压缩分析

的计算尽可能地简单，因为每次“插入”和“搜寻”哈希表都要执行哈希函数，哈希函数的复杂度直接影响程序的执行效率，容易想到的哈希函数是取 3 个字节的左边（或右边）15 位二进制值，但这样只要左边（或右边）2 个字节相同，就会被放到同一个桶中，而 2 个字节相同的概率是比较高的，不符合“平均分布”的要求。gzip 采用的算法是：A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8) （说明：A 指 3 个字节中的第 1 个字节，B 指第 2 个字节，C 指第 3 个字节，A(4,5) 指第一个字节的第 4,5 位二进制码，“^”是二进制位的异或操作，“+”是“连接”而不是“加”，“^”优先于“+”）这样使 3 个字节都尽量“参与”到最后的结果中来，而且每个结果值 h 都等于 ((前1个h << 5) ^ c)取右 15 位，计算也还简单。
哈希表的具体实现也值得探讨,因为无法预先知道每一个“桶”会存放多少个元素，所以最简单的，会想到用链表来实现：哈希表里存放着每个桶的第一个元素，每个元素除了存放着自身的值，还存放着一个指针，指向同一个桶中的下一个元素，可以顺着指针链来遍历该桶中的每一个元素，插入元素时，先用哈希函数算出该放到第几个桶中，再把它挂到相应链表的最后。这个方案的缺点是频繁地申请和释放内存会降低运行速度；内存指针的存放占据了额外的内存开销。有更少内存开销和更快速的方法来实现哈希表，并且不需要频繁的内存申请和释放：gzip 在内存中申请了两个数组，一个叫 head[]，一个叫 pre[]，大小都为 32K，根据当前位置 strstart 开始的 3 个字节，用哈希函数计算出在 head[] 中的位置 ins_h，然后把 head[ins_h] 中的值记入 pre[strstart]，再把当前位置 strstart 记入 head[ins_h]。随着压缩的进行，head[]里记载着最近的可能的匹配的位置（如果有匹配的话，head[ins_h]不为 0），pre[]中的所有位置与原始数据的位置相对应，但每一个位置保存的值是前一个最近的可能的匹配的位置。（“可能的匹配”是指哈希函数计算出的 ins_h 相同。）顺着 pre[] 中的指示找下去，直到遇到 0，可以得到所有匹配在原始数据中的位置，0 表示不再有更远的匹配。
　　接下来很自然地要观察 gzip 具体是如何判断哈希表中数据的过时，如何清理哈希表的，因为 pre[] 里只能存放 32K 个元素，所以这项工作是必须要做的。
　　g
zip 从原始文件中读出两个窗口大小的内容（共 64K 字节）到一块内存中，这块内存也是一个数组，称作 Window[]；申请 head[]、pre[] 并清零；strstart 置为 0。然后 gzip 边搜索边插入，搜索时通过计算 ins_h，检查 head[] 中是否有匹配，如果有

无损数据压缩分析

匹配，判断 strstart 减 head[] 中的位置是否大于 1 个窗口的大小，如果大于 1 个窗口的大小，就不到 pre[] 中去搜索了，因为 pre[] 中保存的位置更远了，如果不大于，就顺着 pre[] 的指示到 Window[] 中逐个匹配位置开始，逐个字节与当前位置的数据比较，以找出最长匹配，pre[] 中的位置也要判断是否超出一个窗口，如遇到超出一个窗口的位置或者 0 就不再找下去，找不到匹配就输出当前位置的单个字节到另外的内存（输出方法在后文中会介绍），并把 strstart 插入哈希表，strstart 递增，如果找到了匹配，就输出匹配位置和匹配长度这两个数字到另外的内存中，并把 strstart 开始的，直到 strstart + 匹配长度 为止的所有位置都插入哈希表，strstart += 匹配长度。插入哈希表的方法为：
pre[strstart % 32K] = head[ins_h];
head[ins_h] = strstart;
可以看出，pre[] 是循环利用的，所有的位置都在一个窗口以内，但每一个位置保存的值不一定是一个窗口以内的。在搜索时，head[] 和 pre[] 中的位置值对应到 pre[] 时也要 % 32K。当 Window[] 中的原始数据将要处理完毕时，要把 Window[] 中后一窗的数据复制到前一窗，再读取 32K 字节的数据到后一窗，strstart -= 32K，遍历 head[]，值小于等于 32K 的，置为 0，大于 32K 的，-= 32K；pre[] 同 head[] 一样处理。然后同前面一样处理新一窗的数据。
　　分析：现在可以看到，虽然 3 个字节有 16M 种取值，但实际上一个窗口只有 32K 个取值需要插入哈希表，由于短语式重复的存在，实际只有 < 32K 种取值插入哈希表的 32K 个“桶”中，而且哈希函数又符合“平均分布”的要求，所以哈希表中实际存在的“冲突”一般不会多，对搜索效率的影响不大。可以预计，在“一般情况”下，每个“桶”中存放的数据，正是我们要找的。哈希表在各种搜索算法中，实现相对的比较简单，容易理解，“平均搜索速度”最快，哈希函数的设计是搜索速度的关键，只要符合“平均分布”和“计算简单”，就常常能成为诸种搜索算法中的首选，所以哈希表是最流行的一种搜索算法。但在某些特殊情况下，它也有缺点，比如：1.当键码 k 不存在时，要求找出小于 k 的最大键码或大于 k 的最小键码，哈希表无法有效率地满足这种要求。2.哈希表的“平均搜
索速度”是建立在概率论的基础上的，因为事先不能预知待搜索的数据集合，我们只能“信赖”搜索速度的“平均值”，而不能“保证”搜索速度的“上限”。在同人类性命攸关的应用中（如医疗或宇航领域），将是不合适的。这些情况及其他一些特殊情况下，我们必须求助其他“平均速度”较低，但能满足相应的特殊要求的

无损数据压缩分析

算法。（见《计算机程序设计艺术》第3卷 排序与查找）。幸而“在窗口中搜索匹配字节串”不属于特殊情况。
时间与压缩率的平衡：
gzip 定义了几种可供选择的 level，越低的 level 压缩时间越快但压缩率越低，越高的 level 压缩时间越慢但压缩率越高。
不同的 level 对下面四个变量有不同的取值：

nice_length
max_chain
max_lazy
good_length

nice_length：前面说过，搜索匹配时，顺着 pre[] 的指示到 Window[] 中逐个匹配位置开始，找出最长匹配，但在这过程中，如果遇到一个匹配的长度达到或超过 nice_length，就不再试图寻找更长的匹配。最低的 level 定义 nice_length 为 8，最高的 level 定义 nice_length 为 258（即一个字节能表示的最大短语匹配长度 3 + 255）。

max_chain：这个值规定了顺着 pre[] 的指示往前回溯的最大次数。最低的 level 定义 max_chain 为 4，最高的 level 定义 max_chain 为 4096。当 max_chain 和 nice_length 有冲突时，以先达到的为准。

max_lazy：这里有一个懒惰匹配（lazy match）的概念，在输出当前位置（strstart）的匹配之前，gzip 会去找下一个位置（strstart + 1）的匹配，如果下一个匹配的长度比当前匹配的长度更长，gzip 就放弃当前匹配，只输出当前位置处的首个字节，然后再查找 strstart + 2 处的匹配，这样的方式一直往后找，如果后一个匹配比前一个匹配更长，就只输出前一个匹配的首字节，直到遇到前一个匹配长于后一个匹配，才输出前一个匹配。
gzip 作者的思路是，如果后一个匹配比前一个匹配更长，就牺牲前一个匹配的首字节来换取后面的大于等于1的额外的匹配长度。
max_lazy 规定了，如果匹配的长度达到或超过了这个值，就直接输出，不再管后一个匹配是否更长。最低的4级 level 不做懒惰匹配，第5级 level 定义 max_lazy 为 4，最高的 level 定义 max_lazy 为 258。

good_length：这个值也和懒惰匹配有关，如果前一个匹配长度达到或超过 good_length，那在寻找当前的懒惰匹配时，回溯的最大次数减小到 max_chain 的 1/4，以减少当前的懒惰匹配花费的时间。第5级 level 定义 good_length 为 4（这一级等于忽略了 good_length），最高的 level 定义 good_length 为 32。

分析：懒惰匹配有必要吗？可以改进吗？
gzip 的作者是无损压缩方面的专家，但是世界上没有
绝对的权威，吾爱吾师，更爱真理。我觉得 gzip 的作者对懒惰匹配的考虑确实不够周详。只要是进行了认真客观的分析，谁都有权利提出自己的观点。
采用懒惰匹配，需要对原始文件的更多的位置查找匹配，时间肯定增加了许多倍，但压缩率的提高在总体上十分有限。在几种情况下，它反而增长了短语压缩的结果

无损数据压缩分析

，所以如果一定要用懒惰匹配，也应该改进一下算法，下面是具体的分析。
1. 连续3次以上找到了更长的匹配，就不应该单个输出前面的那些字节，而应该作为匹配输出。
2. 于是，如果连续找到更长的匹配的次数大于第一个匹配的长度，对于第一个匹配，相当于没有做懒惰匹配。
3. 如果小于第一个匹配的长度但大于2，就没有必要作懒惰匹配，因为输出的总是两个匹配。
4. 所以找到一个匹配后，最多只需要向后做 2 次懒惰匹配，就可以决定是输出第一个匹配，还是输出1（或 2）个首字节加后面的匹配了。
5. 于是，对于一段原始字节串，如果不做懒惰匹配时输出两个匹配（对于每个匹配，距离占15位二进制数，长度占8位二进制数，加起来约占3字节，输出两个匹配约需要6字节），做了懒惰匹配如果有改进的话，将是输出1或2个单字节加上1个匹配（也就是约4或5字节）。这样，懒惰匹配可以使某些短语压缩的结果再缩短1/3到1/6。
6. 再观察这样一个例子：
1232345145678[当前位置]12345678
不用懒惰匹配，约输出6字节，用懒惰匹配，约输出7字节，由于使用了懒惰匹配，把更后面的一个匹配拆成了两个匹配。（如果 678 正好能归入再后面的一个匹配，那懒惰匹配可能是有益的。）
7. 综合考虑各种因素（匹配数和未匹配的单双字节在原始文件中所占的比例，后一个匹配长度大于前一个匹配长度的概率，等等），经过改进的懒惰匹配算法，对总的压缩率即使有贡献，也仍是很小的，而且也仍然很有可能会降低压缩率。再考虑到时间的确定的明显的增加与压缩率的不确定的微弱的增益，也许最好的改进是果断地放弃懒惰匹配。

gzip 在完成短语式压缩后，将转入编码式压缩的阶段。这个阶段的实现是很复杂的，对最终的压缩率至关重要，我会详细解说 gzip 的做法。gzip 是开放源代码的无损压缩程序中最著名的，其中的种种技巧很有启发意义，但是他是比较早期的程序，现在有很多的程序已经在压缩率上超过了它，所以我会根据自己对无损压缩的基本规律的理解提出对它的改进。

编码式压缩的几点考虑：
1. huffman 算法压缩率的关键是各节点值的差异要大，这样就要求分段编码输出。因为某些段落中某些节点的出现频率较高，另一些段落中这
些节点出现频率较低，如果不分段输出，频率的差异会被彼此抵消，而不同段落中，节点的出现频率不同是常有的。
　　要决定分段的大小，必须解决一对矛盾：上面的分析似乎要求段落越小越好，但由于要保存码表以对 huffman 压缩结果进行解压，每个段落都要保存一份不同的码表，所以段落取得太小，保存

无损数据压缩分析

了码表后得不偿失，这样，似乎又要求段落要尽量大，使码表的保存份数尽量少。
　　gzip 采取了这样的策略来确定段落的大小：lz77 压缩每产生 4k（小）的数据，就判断现在对未编码部分进行编码输出是否合适，最多积压到 32k（大）的时候，必定进行强制输出，因为平庸的数据积压得太多，后面即使有好的数据，频率统计在一起，也会被平庸化。
　　判断当前输出合适与否的条件是：1)用预先设定好的各节点长度和各节点实际的出现次数，计算压缩结果的大概值，看这个值是否小于未压缩时的 1/2。2)看目前为止的匹配数是否小于未匹配的字节数，因为 lz77 压缩产生的数据包括“匹配”和“未匹配的原始字节”，段落间的节点频率差异主要体现在“未匹配的原始字节”中。
　　上面的判断只是一种“猜测”，真正的精确的计算需要花费更多的时间。
　　我觉得 gzip 的策略可以改进，我的策略是：1)输出的时机是压缩率的关键之一，现在计算机的速度和九十年代时已经今非昔比，现在完全有条件采用真正的建 huffman 树的方法得到各节点的码长，作精确的判断。2)不应该与未压缩的原始数据比较，而应该与 lz77 输出的数据比较，否则计算出的压缩比很大一部分是短语式压缩的功劳。3)由于采用了真正的建 huffman 树的方法，不用再去做匹配数与未匹配的字节数的比较，因为那只是一种猜测。4)每 4k 的数据都单独统计频率，如果是合适的，就先输出之前的积压（如果有的话），再输出当前的 4k，这样可以避免当前的数据被积压的数据平庸化。如果不合适，就把当前的频率归入到积压的数据（如果有）的频率中，再判断是否合适，如仍不合适就暂缓输出，否则一起输出，这和 gzip 的作法是一样的。说明：几段差的数据积压到一起仍有可能成为好的数据，比如 01、 02、……积压在一起，0 的频率逐渐高出了其他字节。5)如果愿意付出更多的时间，在把当前的频率归入之前的频率时，可以先和之前 4k 的频率合并，如果不合适，和之前 8k 的频率合并，这样逐渐往前合并 4k，避免前面不好的数据拖累合并后的好的数据。6)有了前面的机制，32k 的强制输出点可以取消。7)进一步的改进：当要输出时，只输出积压的不好的部分，好的数据
先留着，等后面的 4k，如果新的加入后，仍是好的数据，就再等，如果会降低压缩率，才输出好的部分。这样，让好的数据大段的输出，可以减少码表的保存份数。8)再进一步的改进：坏的数据放在一起可能会提高压缩率，好的数据放在一起也可能更好，当然，两种情况也都有可能降低压缩率，所以前面判断“好”还是

无损数据压缩分析

“不好”，“合适”还是“不合适”的标准应该从某一个固定的压缩率标准改变为：提高了压缩率还是降低了压缩率。（提高的幅度应该至少抵消多保存一份码表的损失；降低的幅度也应该至少抵消少保存一份码表的得益）9)综合前面的分析，确定分段大小的策略最终调整为：当新的数据和前面的未切分数据放在一起时，两者中任何一方受到损失，都应该设置切分点，积累了两个分段后，通过计算，当切分带来的收益大于少保存一份码表时，才输出前一段，否则取消它们之间的切分点。这个策略实际上可以涵盖前面提到的所有改进，因为每个实际的分段之中的数据或者相互促进，或者彼此稍有妨害，但好过多保存一份码表；而每两个相邻的分段之间的数据彼此妨害，抵消了少保存一份码表的收益。这个策略简单直观地体现了我们设置分段的初衷：就是分段输出必须能提高压缩率。

2. 如果不考虑码表，huffman 算法能得到最短的编码式压缩结果，但是这种算法必须保存码表以便解压缩，所以不能保证结果是最佳的。gzip 预先拟定了一套通用的静态的编码，当要输出一个段落时，比较 huffman 压缩结果加码表的长度和静态编码的压缩结果长度，再决定用哪种方法输出这个段落。静态编码不需要建树，计算压缩结果长度时耗时很少。如果各节点的频率的差异很小，huffman 压缩结果加码表反而增大了结果，静态编码也不合适，同样增大了结果，gzip 就直接保存 lz77 的原始输出。由于输出一个段落时，增加了静态编码的方案，使输出的实际长度和之前确定分段点时计算的值可能不同，那么前面计算出的这个分段点是否仍是正确的？前面的分段策略是否需要调整？
　　分析：1)静态编码的各节点编码是不变的，对于段落的合并是无所谓的，两个连续段落即使都采用静态编码，也不用合并，因为合并后结果长度是不会变的。2)所以只对一种情况可能有影响：一个段落中拆分出一些部分用 huffman 编码，另一些部分用静态编码，压缩结果更好。当这种情况发生时，则必有一些部分的优势节点（频率高的节点）与静态编码预先拟定的优势节点相近，采用静态编码后有稍许改善，其他部分则与静态编码预先拟定的优势节点有一定分歧，采用静态编码
后会有稍许不利。之所以说“稍许”，是因为我们已知同一个段落里的各部分数据或者互相促进，或者仅有稍许妨害，说明它们的优势节点是大致趋同的。考虑到拆分后可能要多保存几份码表，拆分带来收益的可能性和程度是很小的，而且计算的复杂度较大，所以前面的拆分策略可以不作调整。
　　至于直接保存 lz7