zip 的压缩原理与实现二

２．实现部分
　　如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析 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 的官方网站 www.gzip.org 下载。下面提到的每一个问题，都首先介绍最直观简单的解决方法，然后指出这种方法的弊端所在，最后介绍 gzip 采用的做法，这样也许能使读者对 gzip 看似复杂、不直观的做法的意义有更好的理解。）
最直观的搜索方式是顺序搜索：以待压缩部分的第一个字节与窗口中的每一个字节依次比较，当找到一个相等的字节时，再比较后续的字节…… 遍历了窗口后得出最长匹配。gzip 用的是被称作“哈希表”的方法来实现较高效的搜索。“哈希（hash）”是分散的意思，把待搜索的数据按照字节值分散到一个个“桶”中，搜索时再根据字节值到相应的“桶”中去寻找。短语式压缩的最短匹配为 3 个字节，gzip 以 3 个字节的值作为哈希表的索引，但 3 个字节共有 2 的 24 次方种取值，需要 16M 个桶，桶里存放的是窗口中的位置值，窗口的大小为 32K，所以每个桶至少要有大于两个字节的空间，哈希表将大于 32M，作为 90 年代开发的程序，这个要求是太大了，而且随着窗口的移动，哈希表里的数据会不断过时，维护这么大的表，会降低程序的效率，gzip 定义哈希表为 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 个元素，所以这项工作是必须要做的。
　　gzip 从原始文件中读出两个窗口大小的内容（共 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. 综合考虑各种因素（匹配数和未匹配的单双字节在原始文件中所占的比例，后一个匹配长度大于前一个匹配长度的概率，等等），经过改进的懒惰匹配算法，对总的压缩率即使有贡献，也仍是很小的，而且也仍然很有可能会降低压缩率。再考虑到时间的确定的明显的增加与压缩率的不确定的微弱的增益，也许最好的改进是果断地放弃懒惰匹配。