ZIP压缩算法详细分析及解压实例解释

《ZIP压缩算法详细分析及解压实例解释》由会员分享，可在线阅读，更多相关《ZIP压缩算法详细分析及解压实例解释（25页珍藏版）》请在装配图网上搜索。

1、ZIP 压缩算法详细分析及解压实例解释最近自己实现了一个ZIP压缩数据的解压程序，觉得有必要把ZIP压缩格式进行一下详细总结，数据压缩 是一门通信原理和计算机科学都会涉及到的学科，在通信原理中，一般称为信源编码，在计算机科学里， 一般称为数据压缩，两者本质上没啥区别，在数学家看来，都是映射。一方面在进行通信的时候，有必要 将待传输的数据进行压缩，以减少带宽需求；另一方面，计算机存储数据的时候，为了减少磁盘容量需求， 也会将文件进行压缩，尽管现在的网络带宽越来越高，压缩已经不像 90 年代初那个时候那么迫切，但在 很多场合下仍然需要，其中一个原因是压缩后的数据容量减小后，磁盘访问IO的时间也缩短

2、，尽管压缩 和解压缩过程会消耗CPU资源，但是CPU计算资源增长得很快，但是磁盘IO资源却变化得很慢，比如 目前主流的SATA硬盘仍然是7200转，如果把磁盘的IO压力转化到CPU上，总体上能够提升系统运行 速度。压缩作为一种非常典型的技术，会应用到很多很多场合下，比如文件系统、数据库、消息传输、网 页传输等等各类场合。尽管压缩里面会涉及到很多术语和技术，但无需担心，博主尽量将其描述得通俗易 懂。另外，本文涉及的压缩算法非常主流并且十分精巧，理解了 ZIP的压缩过程，对理解其它相关的压缩 算法应该就比较容易了。1、引子压缩可以分为无损压缩和有损压缩，有损，指的是压缩之后就无法完整还原原始信息，

3、但是压缩率可以很 高，主要应用于视频、话音等数据的压缩，因为损失了一点信息，人是很难察觉的，或者说，也没必要那 么清晰照样可以看可以听；无损压缩则用于文件等等必须完整还原信息的场合，ZIP自然就是一种无损压 缩，在通信原理中介绍数据压缩的时候，往往是从信息论的角度出发，引出香农所定义的熵的概念，这方 面的介绍实在太多，这里换一种思路，从最原始的思想出发，为了达到压缩的目的，需要怎么去设计算法。 而ZIP为我们提供了相当好的案例。尽管我们不去探讨信息论里面那些复杂的概念，不过我们首先还是要从两位信息论大牛谈起。因为是他们 奠基了今天大多数无损数据压缩的核心，包括ZIP、RAR、GZIP、GIF、

4、PNG等等大部分无损压缩格式。 这两位大牛的名字分别是Jacob Ziv和Abraham Lempel，是两位以色列人，在1977年的时候发表了 一篇论文A Unive rsal Alg or ithm for Sequential Data Comp ression，从名字可以看出，这是一 种通用压缩算法，所谓通用压缩算法，指的是这种压缩算法没有对数据的类型有什么限定。不过论文我觉 得不用仔细看了，因为博主作为一名通信专业的PHD，看起来也焦头烂额，不过我们后面可以看到，它的 思想还是很简单的，之所以看起来复杂，主要是因为 IEEE 的某些杂志就是这个特点，需要从数学上去证 明，这种压缩算法

5、到底有多优，比如针对一个各态历经的随机序列（不用追究什么叫各态历经随机序列）， 经过这样的压缩算法后，是否可以接近信息论里面的极限（也就是前面说的熵的概念）等等，不过在理解 其思想之前，个人认为没必要深究这些东西，除非你要发论文。这两位大牛提出的这个算法称为 LZ77， 两位大牛过了一年又提了一个类似的算法，称为LZ78,思想类似，ZIP这个算法就是基于LZ77的思想 演变过来的，但ZIP对LZ77编码之后的结果又继续进行压缩，直到难以压缩为止。除了 LZ77、LZ78， 还有很多变种的算法，基本都以 LZ 开头，如 LZW、 LZO、 LZMA、 LZSS、 LZR、 LZB、 LZH、 L

6、ZC、 LZT、 LZMW、LZJ、LZFG等等，非常多，LZW也比较流行，GIF那个动画格式记得用了 LZW。我也写过解码 程序，以后有时间可以再写一篇，但感觉跟LZ77这些类似，写的必要性不大。ZIP的作者是一个叫Phil Katz的人，这个人算是开源界的一个具有悲剧色彩的传奇人物。虽然二三十年 前，开源这个词还没有现在这样风起云涌，但是总有一些具有黑客精神的牛人，内心里面充满了自由，无 论他处于哪个时代。Phil Katz这个人是个牛逼程序员，成名于DOS时代，我个人也没有经历过那个时代， 我是从Windows98开始接触电脑的，只是从书籍中得知，那个时代网速很慢，拨号使用的是只有几十

7、Kb （比特不是字节）的猫，56Kb实际上是这种猫的最高速度，在ADSL出现之后，这种技术被迅速淘汰。 当时记录文件的也是硬盘，但是在电脑之间拷贝文件的是软盘，这个东西我大一还用过，最高容量记得是 1.44MB，这还是200X年的软盘，以前的软盘容量具体多大就不知道了，Phil Katz上网的时候还不到 1990 年， WWW 实际上就没出现，浏览器当然是没有的，当时上网干嘛呢？基本就是类似于网管敲各种 命令，这样实际上也可以聊天、上论坛不是吗，传个文件不压缩的话肯定死慢死慢的，所以压缩在那个时 代很重要。当时有个商业公司提供了一种称为ARC的压缩软件，可以让你在那个时代聊天更快，当然是要 付

8、费的，Phil Katz就感觉到不爽，于是写了一个PKARC，免费的，看名字知道是兼容ARC的，于是网 友都用PKARC 了，ARC那个公司自然就不爽，把哥们告上了法庭，说牵涉了知识产权等等，结果Phil Katz 坐牢了。牛人就是牛人，在牢里面冥思苦想，决定整一个超越ARC的牛逼算法出来，牢里面就是适 合思考，用了两周就整出来的，称为PKZIP，不仅免费，而且这次还开源了，直接公布源代码，因为算法 都不一样了，也就不涉及到知识产权了，于是ZIP流行开来，不过Phil Katz这个人没有从里面赚到一分 钱，还是穷困潦倒，因为喝酒过多等众多原因， 2000 年的时候死在一个汽车旅馆里。英雄逝去，

9、精神永 存，现在我们用UE打开ZIP文件，我们能看到开头的两个字节就是PK两个字符的ASCII码。2、一个案例的入门思考好了，Phil Katz在牢里面到底思考了什么？用什么样的算法来压缩数据呢？我们想一个简单的例子：生，容易。活，容易。生活，不容易。上面这句话假如不压缩，如果使用Unicode编码，每个字会用2个字节表示。为什么是两个字节呢？ Unicode 是一种国际标准，把常见各国的字符，比如英文字符、日文字符、韩文字符、中文字符、拉丁字 符等等全部制定了一个标准，显然，用2个字节可以最多表示2人16=65536个字符，那么65536就够 了吗？生僻字其实是很多的，比如光康熙字典里面收录

10、的汉字就好几万，所以实际上是不够的，那么是不 是扩到 4个字节？也可以，这样空间倒是变大了，可以收录更多字符，但一方面扩到4 个字节就一定保证 够吗？另一方面， 4 个字节是不是太浪费空间了，就为了那些一般情况都不会出现的生僻字？所以，一般 情况下，使用 2 个字节表示，当出现生僻字的时候，再使用4个字节表示。这实际上就体现了信息论中数 据压缩基本思想，出现频繁的那些字符，表示得短一些；出现稀少的，可以表示得长些（反正一般情况下 也不会出现），这样整体长度就会减小。除了 Unicode, ASCII编码是针对英文字符的编码方案，用1个 字节即可，除了这两种编码方案，还有很多地区性的编码方案，比

11、如 GB2312 可以对中文简体字进行编码， Big5 可以对中文繁体字进行编码。两个文件如果都使用一种编码方案，那是没有问题的，不过考虑到国际 化，还是尽量使用Unicode这种国际标准吧。不过这个跟ZIP没啥关系，纯属背景介绍。好了，回到我们前面说的例子，一共有17个字符（包括标点符号），如果用普通Unicode表示，一共是 17*2=34 字节。可不可以压缩呢？所有人一眼都可以看出里面出现了很多重复的字符，比如里面出现了 好多次容易（实际上是容易加句号三个字符）这个词，第一次出现的时候用普通的Unicode，第二次出现 的“容易。 ”则可以用（距离、长度）表示，距离的意思是接下来的字符离

12、前面重复的字符隔了几个，长度 则表示有几个重复字符，上面的例子的第二个“容易。 ”就表示为（5,3），就是距离为 5 个字符，长度是 3， 在解压缩的时候，解到这个地方的时候，往前跳5 个字符，把这个位置的连续3 个字符拷贝过来就完成了 解压缩，这实际上不就是指针的概念？没有错，跟指针很类似，不过在数据压缩领域，一般称为字典编码， 为什么叫字典呢，当我们去查一个字的时候，我们总是先去目录查找这个字在哪一页，再翻到那一页去看， 指针不也是这样，指针不就是内存的地址，要对一个内存进行操作，我们先拿到指针，然后去那块内存去 操作。所谓的指针、字典、索引、目录等等术语，不同的背景可能称呼不同，但我们要

13、理解他们的本质。 如果使用（5,3）这种表示方法，原来需要用 6个字节表示，现在只需要记录5 和3 即可。那么， 5 和3 怎么记录呢？ 一种方法自然还是可以用Unicode，那么就相当于节省了 2个字节，但是有两个问题，第一 个问题是解压缩的时候怎么知道是正常的 5 和3 这两个字符，还是这只是一个特殊标记呢？所以前面还得 加一个标志来区分一下,到底接下来的Unicode码是指普通字符，还是指距离和长度，如果是普通Unicode, 则直接查Unicode码表，如果是距离和长度，则往前面移动一段距离，拷贝即可。第二个问题，还是压缩 程度不行，这么一弄，感觉压缩不了多少，如果重复字符比较长那倒是

14、比较划算，因为反正“距离+长度” 就够了，但比如这个例子，如果5 和3 前面加一个特殊字节，岂不是又是3 个字节，那还不如不压缩。咋 办呢？能不能对（5,3）这种整数进行再次压缩？这里就利用了我们前面说的一个基本原则：出现的少的整 数多编一些比特，出现的多的整数少编一些比特。那么，比如 3、4、5、6、7、8、9这些距离谁出现得 多？谁出现的少呢？谁知道？压缩之前当然不知道，不过扫描一遍不就知道了？比如，后面那个重复的字符串“容易。”按照前面的规则 可以表示为（7,3）,即离前面重复的字符串距离为 7，长度为3。（7,3）指着前面跟自己一样那个字符串。 那么，为什么不指着第一个“容易。”要指着

15、第二个“容易。”呢？如果指着第一个，那就不是（7,3）了，就 是（12，3）了。当然，表示为（12,3）也可以解压缩，但是有一个问题，就是12 这个值比7 大，大了 又怎么了？我们在生活中会发现一些普遍规律，重复现象往往具有局部性。比如，你跟一个人说话，你说 了一句话以后，往往很快会重复一遍，但是你不会隔了 5 个小时又重复这句话，这种特点在文件里面也存 在着，到处都是这种例子，比如你在编程的时候，你定义了一个变量int nCount,这个nCount 般你很 快就会用到，不会离得很远。我们前面所说的距离代表了你隔了多久再说这句话，这个距离一般不大，既 然如此，应该以离当前字符串距离最近的那个

16、作为记录的依据（也就是指向离自己最近那个重复字符串）， 这样的话，所有的标记都是一些短距离，比如都是3、4、5、6、7而不会是 3、5、78、965等等，如果 大多数都是一些短距离，那么这些短距离就可以用短一些的比特表示，长一些的距离不太常见，则用一些 长一些的比特表示。这样， 总体的表示长度就会减少。好了，我们前面得到了（5,3）、（7、3）这种记 录重复的表示，距离有两种：5、7；长度只有 1 种：3。咋编码？越短越好。既然表示的比特越短越好， 3 表示为 0、5 表示为 10、7 表示为11，行不行？这样（5,3）,（7,3）就只 需要表示为 100、110，这样岂不是很短？貌似可以，貌

17、似很高效。但解压缩遇到 10 这两个比特的时候，怎么知道10 表示5呢？这种表示方法是一个映射表，称为码表。 我们设计的上面这个例子的码表如下：3-05-107-11这个码表也得传过去或者记录在压缩文件里才行啊，否则无法解压缩，但会不会记录了码表以后整体空间 又变大了，会不会起不到压缩的作用？而且一个码表怎么记录？码表记录下来也是一堆数据，是不是也需 要编码？码表是否可以继续压缩？那岂不是又需要新的码表？压缩会不会是一个永无止境的过程？作为一 个入门级的同学，大概想到这儿就不容易想下去了。3、ZIP中的LZ编码思想上面我们说的重复字符串用指针标记记录下来，这种方法就是 LZ 这两个人提出来的，

18、理解起来比较简单。 后面分析（5,3）这种指针标记应该怎么编码的时候，就涉及到一种非常广泛的编码方式， Huffman 编码， Huffman大致和香农是一个时代的人，这种编码方式是他在MIT读书的时候提出来的。接下来，我们来 看看ZIP是怎么做的。以上面的例子，一个很简单的示意图如下：为前压缩位邑可以看出，ZIP中使用的LZ77算法和前面分析的类似，当然，如果仔细对比的话，ZIP中使用的算法和LZ 提出来的 LZ77 算法其实还是有差异的，不过我建议不用仔细去扣里面的差异，思想基本是相同的，我 们后面会简要分析一下两者的差异。LZ77算法一般称为滑动窗口压缩”，我们前面说过，该算法的核心 是

19、在前面的历史数据中寻找重复字符串，但如果要压缩的文件有100MB,是不是从文件头开始找？不是， 这里就涉及前面提过的一个规律，重复现象是具有局部性的，它的基本假设是，如果一个字符串要重复， 那么也是在附近重复，远的地方就不用找了，因此设置了一个滑动窗口，ZIP中设置的滑动窗口是32KB, 那么就是往前面32KB的数据中去找，这个32KB随着编码不断进行而往前滑动。当然，理论上讲，把滑 动窗口设置得很大，那样就有更大的概率找到重复的字符串，压缩率不就更高了？初看起来如此，找的范 围越大，重复概率越大，不过仔细想想，可能会有问题，一方面，找的范围越大，计算量会增大，不顾一 切地增大滑动窗口，甚至不

20、设置滑动窗口，那样的软件可能不可用，你想想，现在这种方式，我们在压缩 一个大文件的时候，速度都已经很慢了，如果增大滑动窗口，速度就更慢，从工程实现角度来说，设置滑 动窗口是必须的；另一方面，找的范围越大，距离越远，出现的距离很多，也不利于对距离进行进一步压 缩吧，我们前面说过，距离和长度最好出现的值越少越好，那样更好压缩，如果出现的很多，如何记录距 离和长度可能也存在问题。不过，我相信滑动窗口设置得越大，最终的结果应该越好一些，不过应该不会 起到特别大的作用，比如压缩率提高了 5%，但计算量增加了 10 倍，这显然有些得不偿失。在第一个图中，容易。”是一个重复字符串，距离distance =

21、5,字符串长度length = 3。当对这三个字符 压缩完毕后，接下来滑动窗口向前移动 3 个字符，要压缩的是我.”这个字符串，但这个串在滑动窗口内 没找到，所以无法使用 distance+length 的方式记录。这种结果称为 literal。 literal 的中文含义是原义 的意思，表示没有使用 distance+length 的方式记录的那些普通字符。 literal 是不是就用原始的编码方 式，比如Unicode方式表示？ ZIP里不是这么做的，ZIP把literal认为也是一个数，尽管不能用 distance+length 表示，但不代表不可以继续压缩。另外，如果我”出现在了滑动窗

22、口内，是不是就可以 用 distance+length 的方式表示？也不是，因为一个字出现重复，不值得用这种方式表示，两个字呢？ distance+length就是两个整数，看起来也不一定值得，ZIP中确实认为2个字节如果在滑动窗口内找到 重复，也不管，只有3个字节以上的重复字符串，才会用distance+length表示，重复字符串的长度越 长越好，因为不管多长，都用 distance+length 表示就行了。这样的话，一段字符串最终就可以表示成literal、distance+length这两种形式了。LZ系列算法的作用 到此为止，下面，Phil Katz考虑使用Huffman对上面的这

23、些LZ压缩后的结果进行二次压缩。个人认为 接下来的过程才是ZIP的核心，所以我们要熟悉一下Huffman编码。4、 ZIP 中的 Huffman 编码思想上面LZ压缩结果有三类（literal、distance、length），我们拿出distance 一类来举例。distance代 表重复字符串离前一个一模一样的字符串之间的距离，是一个大于0的整数。如何对一个整数进行编码呢？ 一种方法是直接用固定长度表示，比如采用计算机里面描述一个4字节整数那样去记录，这也是可以的， 主要问题当然是浪费存储空间，在ZIP中，distance这个数表示的是重复字符串之间的距离，显然，一般 而言，越小的距离，出

24、现的数量可能越多，而越大的距离，出现的数量可能越少，那么，按照我们前面所 说的原则，小的值就用较少比特表示，大的值就用较多比特表示，在我们这个场景里,distance当然也不 会无限大，比如不会超过滑动窗口的最大长度，假如对一个文件进行LZ压缩后，得到的distance值为：3 、 6、 4、 3 、 4、 3 、 4 、 3 、 5这个例子里， 3出现了 4次， 4出现了 3次， 5出现了 1次， 6出现了 1次。当然，不同的文件得到的结 果不同，这里只是举一个典型的例子，因为只有4种值，所以我们没有必要对其它整数编码。只需要对这4 个整数进行编码即可。那么，怎么设计一个算法，符合3的编码长

25、度最短？6的编码长度最长这种直观上可行的原则（我们并没 有说这是理论上最优的方式）呢？看起来似乎很难想出来。我们先来简化一下，用固定长度表示。这里有4个整数，只要使用2个比特表示 即可。于是这样表示就很简单：00-3 ； 01-4； 10-5; 11-6。00、 01这种编码结果称为码字，码字的平均长度是2。上面这个对应关系即为码表，在压缩时，需要将 码表放在最前面，后面的数字就用码字表示，解码时，先把码表记录在内存里，比如用一个哈希表记录下 来，解压缩时，遇到 00，就解码为 3 等等。因为出现了 9个数，所以全部码字总长度为18个比特。（我们暂时不考虑记录码表到底要占多少空间）想要编码结果

26、更短，因为 3出现的最多，所以考虑把3的码字缩短点，比如3是不是可以用 1个比特表示， 这样才算缩短吧，因为0和1只是二进制的一个标志，所以用0还是1没有本质区别，那么，我们暂定把 3用比特0表示。那么， 4、 5、 6还能用 0开头的码字表示呢？这样会存在问题，因为4、 5、 6的编码结果如果以0开头，那么，在解压缩的时候，遇到比特0，就不知 道是表示 3 还是表示 4、 5、 6了，就无法解码，当然，似乎理论上也不是不可以，比如可以往后解解看， 比如假定0表示3的条件下往后解，如果无效则说明这个假设不对，但这种方式很容易出现两个字符串的 编码结果是一样的，这个谁来保证？所以， 4、 5、

27、6都得以1开头才行，那么，按照这个原则， 4用 1个 比特也不行，因为 5、 6要么以 0开头，要么以 1开头，就无法编码了，所以我们将4的码字增加至2个 比特，比如10，于是我们得到了部分码表:0-3 ；10-4。 按照这个道理，5、6 既不能以0 开头，也不能以10 开头了，因为同样存在无法解码的问题，所以5 应该 以 11 开头，就定为 11 行不行呢？也不行，因为 6 就不知道怎么编码了，6 也不能以 0 开头，也不能以 10、11开头，那就无法表示了，所以，迫不得已，我们必须把 5扩展一位，比如110，那么，6显然就 可以用 111 表示了，反正也没有其他数了。于是我们得到了最终的码

28、表：0-3；10-4；110-5；111-6。看起来，编码结果只能是这样了，我们来算一下，码字的总长度减少了没有，原来的 9个数是 3、6、4、3、4、3、4、3、5，分别对应的码字是：0、111、10、0、10、0、10、0、110算一下，总共16 个比特，果然比前面那种方式变短了。我们在前面的设计过程中，是按照这些值出现次 数由高到底的顺序去找码字的，比如先确定3，再确定4、5、6 等等。按照一个码字不能是另一个码字的 前缀这一规则，逐步获得所有的码字。这种编码规则有一个专用术语，称为前缀码。Huffman编码基本上 就是这么做的，把出现频率排个序，然后逐个去找，这个逐个去找的过程，就引入

29、了二叉树。不过 Huffman 的算法一般是从频率由低到高排序，从树的下面依次往上合并，不过本质上没区别，理解思想即可。上面 的结果可以用一颗二叉树表示为下图：这棵树也称为码树，其实就是码表的一种形式化描述，每个节点（除了叶子节点）都会分出两个分支，左 分支代表比特0，右边分支代表 1，从根节点到叶子节点的一个比特序列就是码字。因为只有叶子节点可 以是码字，所以这样也符合一个码字不能是另一个码字的前缀这一原则。说到这里，可以说一下另一个话 题，就是一个映射表 map 在内存中怎么存储，没有相关经验的可以跳过， map 实现的是 key-value 这样的一个表， map 的存储一般有哈希表和树

30、形存储两类，树形存储就可以采用上面这棵树，树的中间节 点并没有什么含义，叶子节点的值表示value，从根节点到叶子节点上分支的值就是key,这样比较适合 存储那些key由多个不等长字符组成的场合，比如key如果是字符串，那么把二叉树的分支扩展很多，成 为多叉树，每个分支就是a,b,c,d这种字符，这棵树也就是Trie树，是一种很好使的数据结构。利用树的 遍历算法，就实现了一个有序 Map。好了，我们理解了 Huffman编码的思想，我们来看看distance的实际情况。ZIP中滑动窗口大小固定为 32KB,也就是说，distance的值范围是1-32768。那么，通过上面的方式，统计频率后，就

31、得到32768 个码字，按照上面这种方式可以构建出来。于是我们会遇到一个最大的问题，那就是这棵树太大了，怎么 记录呢？好了，个人认为到了 ZIP的核心了，那就是码树应该怎么缩小，以及码树怎么记录的问题。5、ZIP 中 Huffman 码树的记录方式 分析上面的例子，看看这个码表：0-3；10-4；110-5；111-6。我们之前提过，0 和1 就是二进制的一个标志，互换一下其实根本不影响编码长度，所以，下面的码表其 实是一样的：1-3；00-4；010-5；011-6。1-3；01-4；000-5；001-6。0-3；11-4；100-5；101-6。这些都可以，而且编码长度完全一样，只是码字

32、不同而已。对比一下第一个和第二个例子，对应的码树是这个样子：Q13014565也就是说，我们把码树的任意节点的左右分支旋转（0、1 互换），也可以称为树的左右互换，其实不影响 编码长度，也就是说，这些码表其实都是一样好的，使用哪个都可以。这个规律暗示了什么信息呢？暗示了码表可以怎么记录呢？ Phil Katz当年在牢里也深深地思考了这一问 题。为了体会Phil Katz当时的心情，我们有必要盯着这两棵树思考几分钟：怎么把一颗树用最少的比特记录 下来？Phil Katz当时思考的逻辑我猜是这样的，既然这些树的压缩程度都一样，那干脆使用最特殊的那棵树，反 正压缩程度都一样，只要ZIP规定了这棵树的

33、特殊性，那么我记录的信息就可以最少，这种特殊化的思想 在后面还会看到。不同的树当然有不同的特点，比如数据结构里面常见的平衡树也是一类特殊的树，他选 的树就是左边那棵，这棵树有一个特点，越靠左边越浅，越往右边越深，是这些树中最不平衡的树。ZIP 里的压缩算法称为Deflate算法，这棵树也称为Deflate树，对应的解压缩算法称为Inflate，Deflate的 大致意思是把轮胎放气了，意为压缩；Inflate是给轮胎打气的意思，意为解压。那么，Deflate树的特殊 性又带来什么了？揭晓答案吧，Phil Katz认为换来换去只有码字长度不变，如果规定了一类特殊的树，那么就只需要记录码 字长度即

34、可。比如，一个有效的码表是0-3； 10-4； 110-5； 111-6。但只需要记录这个对应 关系即可：3456也就是说，把1、2、3、3 记录下来，解压一边照着左边那棵树的形状构造一颗树，然后只需要 1、2、3、 3 这个信息自然就知道是 0、10、110 、111 。这就是 Phil Katz 想出来的 ZIP 最核心的一点：这棵码树 用码字长度序列记录下来即可。当然，只把1、2、3、3 这个序列记录下来还不行，比如不知道111 对应5还是对应6？ 所以，构造出树来只是知道了有哪些码字了，但是这些码字到底对应哪些整数还是不知道。Phil Katz于是又出现了一个想法：记录1、2、3、3还

35、是记录1、3、2、3,或者3、3、2、1,其实都 能构造出这棵树来，那么，为什么不按照一个特殊的顺序记录呢？这个顺序就是整数的大小顺序，比如上 面的3、 4、 5、 6是整数大小顺序排列的,那么,记录的顺序就是1、 2、 3、 3。而不是2、 3、 3、 1。好了,根据1、 2、 3、 3这个信息构造出了码字,这些码字对应的整数一个比一个大,假如我们知道编码 前的整数就是 3、 4、 5、 6这四个数,那就能对应起来了,不过到底是哪四个还是不知道啊？这个整数可 以表示距离啊,距离不知道怎么去解码 LZ？Phil Katz又想了，既然distance的范围是1-32768,那么就按照这个顺序记录

36、。上面的例子1和2没 有,那就记录长度 0。所以记录下来的码字长度序列为：0 、 0、 1 、 2 、 3 、 3 、 0 、 0、 0、 0 、 0、。这样就知道构造出来的码字对应哪个整数了吧，但因为distance可能的值很多（32768个），但实际出 现的往往不多,中间会出现很多 0（也就是根本就没出现这个距离）,不过这个问题倒是可以对连续的 0 做个特殊标记，这样是不是就行了呢？还有什么问题？我们还是要站在时代的高度来看待这个问题。我们明白，每个distance肯定对应唯一一个码字，使用 Huffman编码可以得到所有码字，但是因为distance可能非常多，虽然一般不会有32768这

37、么多，但 对一个大些的文件进行LZ编码，distance上千还是很正常的，所以这棵树很大，计算量、消耗的内存都 容易超越了那个时代的硬件条件，那么怎么办呢？这里再次体现了 Phil Katz对Huffman编码掌握的深度, 他把distance划分成多个区间，每个区间当做一个整数来看，这个整数称为Distance Code。当一个 distance落到某个区间，则相当于是出现了那个Code，多个distance对应于一个Distance Code， Distance虽然很多，但Distance Code可以划分得很少，只要我们对Code进行Huffman编码，得到 Code的编码后，Dista

38、nce Code再根据一定规则扩展出来。那么，划分多少个区间？怎么划分区间呢？ 我们分析过，越小的距离，出现的越多；越大的距离，出现的越少，所以这种区间划分不是等间隔的，而 是越来越稀疏的，类似于下面的划分：12345,67用9-1213-1617-241、2、3、4这四个特殊distance不划分，或者说1个Distance就是1个区间；5,6作为一个区间；7、 8作为一个区间等等，基本上，区间的大小都是1、 2、 4、 8、 16、 32这么递增的，越往后，涵盖的距离 越多。为什么这么分呢？首先自然是距离越小出现频率越高，所以距离值小的时候，划分密一些，这样相 当于一个放大镜，可以对小的距

39、离进行更精细地编码，使得其编码长度与其出现次数尽量匹配；对于距离 较大那些，因为出现频率低，所以可以适当放宽一些。另一个原因是，只要知道这个区间Code的码字， 那么对于这个区间里面的所有distance，后面追加相应的多个比特即可，比如，17-24这个区间的 Huffman码字是110，因为17-24这个区间有8个整数，于是按照下面的规则即可获得其distance对 应的码字：17- -110 00018- -110 00119- -110 01020- -110 01121- -110 10022- -110 10123- -110 11024- -110 111这样计算复杂度和内存消耗是

40、不是很小了，因为需要进行Huffman编码的整数一下字变少了，这棵树不 会多大，计算起来时间和空间复杂度降低，扩展起来也比较简单。当然，从理论上来说，这样的编码方式 实际上将编码过程分为了两级，并不是理论上最优的，把所有distance当作一个大空间去编码才可能得 到最优结果，不过还是那句话，工程实现的限制，在压缩软件实现上，我们不能用压缩率作为衡量一个算 法优劣的唯一指标，其实耗费的时间和空间同样是指标，所以需要看综合指标。很多其他软件也一样，扩 展性、时间空间复杂度、稳定性、移植性、维护的方便性等等是工程上很重要的东西。我没有看过RAR是 如何压缩的，有可能是在类似的地方进行了改进，如果如

41、此，那也是站在巨人的肩膀上，而且硬件条件不 同，进行一些改进也并不奇怪。具体来说，Phil Katz把distance划分为30个区间，如下图：CodeExtraIntsDistanceCodeExtrabitsDistanceCodeExtrabitsDistance00110433 482091025-15361U21 444642191537-204S20312n65-96 1(2049-30723u413597 128231()3073 4096415：614129-19224114097-6144517,815占103-2562511HI 45-8192(i21)-12IG7257-

42、3842(；128193-12288213-1 ti177385-512271212289-163848317 24用8513-768281316385-245769325-32I!)8769- 1024291324577 32768这个图是我从 David Salomon 的Data Compression The Complete Referenc 这本书（第四版） 中拷贝出来的，下面的有些图也是，如果需要对数据压缩进行全面的了解，这本书几乎是最全的了，强烈 推荐。当然，你要问为什么是 30 个区间，我也没分析过，也许是复杂度和压缩率经过试验之后的一种折中吧。其中，左边的Code表示区间的

43、编号，是0-29,共30个区间，这只是个编号，没有特别的含义，但Huffman 就是对0-29这30个Code进行编码的，得到区间的码字；bits表示distance的码字需要在Code的码字基础上扩展几位，比如0就表示不扩展，最大的13表示 要扩展13位，因此，最大的区间包含的distance数量为8192个。Distance 一列则表示这个区间涵盖的 distance 范围。理解了码树如何有效记录，以及如何缩小码树的过程，我觉得就理解了 ZIP的精髓。6、ZIP 中 literal 和 length 的压缩方式 说完了 distance, LZ编码结果还有两类：literal和length

44、。这两类也利用了类似于distance的方式进 行压缩。前面分析过，literal表示未匹配的字符，我们前面之所以拿汉字来举例，完全是为了便于理解，ZIP之所 以是通用压缩，它实际上是针对字节作为基本字符来编码的，所以一个literal至多有256种可能。length 表示重复字符串长度， length=1 当然不会出现，因为一个字符不值得用 distance+length 去记 录，重复字符串当然越长越好，Phil Katz （下面还是简称PK 了，拷贝太麻烦）认为，length = 2也不值 得用这种方式记录，还是太短了，所以PK把length最小值认为是3,必须3个以上字符的字符串出现重

45、 复才用distance+length记录。那么，最大的length是多少呢？理论上当然可以很长很长，比如一个文 件就是连续的0这个重复字符串长度其实接近于这个文件的实际长度。但是PK把length的范围做了限 制,限定length的个数跟literal 样，也只有256个，因为PK认为，一个重复字符串达到了 256个已 经很长了，概率非常小；另外，其实哪怕超过了256，我还是认为是一段256再加上另外一段，增加一个 distance+length 就行了嘛，并不影响结果。而且这样做，我想同样也考虑了硬件条件吧。初看有点奇怪的在于，将literal和length二者合二为一，什么意思呢？就是对

46、这两种整数（literal本质 上是一个字节）共用一个Huffman码表，一会儿解释为什么。PK对Huffman的理解我觉得达到了炉火 纯青的地步，前面已经看到，后面还会看到。他认为Huffman编码的输入反正说白了就是一个集合的元 素就行，无论这个元素是啥，所以多个集合看做一个集合当作Huffman编码的输入没啥问题。literal用 整数0-255表示，256是一个结束标志，解码以后结果是256表示解码结束；从257开始表示length， 所以257这个数表示length = 3, 258这个数表示length=4等等，但PK也不是一直这么一一对应，和 distance 一样，也是把len

47、gth （总共256个值）划分为29个区间，其结果如下图：ClodeExtraLengths(cleExtLengthsCodeExtr1718CCL:1rj r.150(1n0000n0024nPosition:1617180S96105111123 13 211115CCL:24(14(J卄(I5i)(ItJ5(i1n 505卄不过粗看起来，这个置换效果并不好，我一开始接触这个置换的时候，我觉得应该按照16、 17、 18、 0、1、2、 3、。这样的顺序来存储，如果按照我理解的，那么置换后的结果如下：2、4、 0、 4、 5、 5、 1、 5、 0、 6、 0、 0、 0、 0、 0、

48、0、 0、 0、 0这样后面的一大串0直接截断，比PK的方法更短。但PK却按照上面的顺序。我总是认为，我觉得牛人 可能出错了的时候，往往是我自己错了，所以我又仔细想了一下，上面的顺序特点比较明显，直观上看， PK认为CL为0和中间的值出现得比较多（放在了前面），但CL比较小的和比较大的出现得比较少（1、 15、 2、 14这些放在了后面，你看，后面交叉着放），在文件比较小的时候，这种方法效果不算好，上面 就是一个典型的例子，但文件比较大了以后，CL1、CL2码树比较大，码字长度普遍比较长，大部分很可 能接近于中间值，那么这个时候PK的方法可能就体现出优势了。不得不说，对一个算法或者数据结构的

49、优化程度，简直完全取决于程序员对那个东西细节的理解的深度。当我仔细研究了 ZIP压缩算法的过程之 后，我对 PK 这种深夜埋头冥思苦想的大牛佩服得五体投地。到此为止，ZIP压缩算法的结果已经完毕。这个算法命名为Deflate算法。总结一下其编码流程为:8、Deflate 压缩数据格式ZIP的格式实际上就是Deflate压缩码流外面套了一层文件相关的信息，这里先介绍Deflate压缩码流格 式。其格式为:Header： 3个比特，第一个比特如果是1表示此部分为最后一个压缩数据块；否则表示这是.ZIP文件 的某个中间压缩数据块，但后面还有其他数据块。这是ZIP中使用分块压缩的标志之一；第2、3比特

50、表 示3个选择：压缩数据中没有使用Huffman、使用静态Huffman、使用动态Huffman,这是对LZ77 编码后的literal/length/distance进行进一步编码的标志。我们前面分析的都是动态Huffman，其实Deflate也支持静态Huffman编码，静态Huffman编码原理更为简单，无需记录码表（因为PK自己定 义了一个固定的码表），但压缩率不高，所以大多数情况下都是动态 Huffman。HLIT：5比特，记录literal/length码树中码长序列（CL1）个数的一个变量。后面CL1个数等于HLIT+257 （因为至少有0-255总共256个literal，还有

51、一个256表示解码结束，但length的个数不定）。HDIST： 5比特，记录distance码树中码长序列（CL2）个数的一个变量。后面CL2个数等于HDIST+1。 哪怕没有1个重复字符串，distance都为0也是一个CL。HCLEN：4比特，记录Huffman码表3中码长序列（CCL）个数的一个变量。后面CCL个数等于HCLEN+4。 PK 认为 CCL 个数不会低于 4 个，即使对于整个文件只有 1 个字符的情况。接下来是3比特编码的CCL，一共HCLEN+4个，用以构造Huffman码表3；接下来是对CL1 （码长）序列经过游程编码（SQ1：缩短的整数序列）后，并对SQ1继续用Hu

52、ffman 编码后的比特流。包含HLIT+257个CL1,其解码码表为Huffman码表3,用以构造Huffman码表1；接下来是对CL2 （码长）序列经过游程编码（SQ2：缩短的整数序列）后，并对SQ2继续用Huffman 编码后的比特流。包含HDIST+1个CL2,其解码码表为Huffman码表3,用于构造Huffman码表2；总之，上面的数据都是为了构造LZ解码需要的2个Huffman码表。接下来才是经过Huffman编码的压缩数据，解码码表为Huffman码表1和码表2。最后是数据块结束标志，即literal/length这个码表输入符号位256的编码比特。对倒数第1、2内容块进行解码

53、时，首先利用Huffman码表1进行解码，如果解码所得整数位于0-255 之间，表示literal未匹配字符，接下来仍然利用Huffman码表1解码；如果位于257-285之间，表示 length匹配长度，之后需要利用Huffman码表2进行解码得到distance偏移距离；如果等于256，表 示数据块解码结束。9、 ZIP 文件格式解析上面各节对ZIP的原理进行了分析，这一节我们来看一个实际的例子，为了更好地描述，我们尽量把这个 例子举得简单一些。下面是我随便从一本书拷贝出来的一段较短的待压缩的英文文本数据：As mentioned above,there are many kinds of wireles