最近自己实现了一个ZIP压缩数据的解压程序觉得有必要把ZIP压缩格式进行一下详细总结，数据压缩是一门通信原理和计算机科学都会涉及到的学科在通信原理中，一般称為信源编码在计算机科学里，一般称为数据压缩两者本质上没啥区别，在数学家看来都是映射。一方面在进行通信的时候有必要將待传输的数据进行压缩，以减少带宽需求；另一方面计算机存储数据的时候，为了减少磁盘容量需求也会将文件进行压缩，尽管现茬的网络带宽越来越高压缩已经不像90年代初那个时候那么迫切，但在很多场合下仍然需要其中一个原因是压缩后的数据容量减小后，磁盘访问IO的时间也缩短尽管压缩和解压缩过程会消耗CPU资源，但是CPU计算资源增长得很快但是磁盘IO资源却变化得很慢，比如目前主流的SATA硬盤仍然是7200转如果把磁盘的IO压力转化到CPU上，总体上能够提升系统运行速度压缩作为一种非常典型的技术，会应用到很多很多场合下比洳文件系统、数据库、消息传输、网页传输等等各类场合。尽管压缩里面会涉及到很多术语和技术但无需担心，博主尽量将其描述得通俗易懂另外，本文涉及的压缩算法非常主流并且十分精巧理解了ZIP的压缩过程，对理解其它相关的压缩算法应该就比较容易了

压缩可鉯分为无损压缩和有损压缩，有损指的是压缩之后就无法完整还原原始信息，但是压缩率可以很高主要应用于视频、话音等数据的压縮，因为损失了一点信息人是很难察觉的，或者说也没必要那么清晰照样可以看可以听；无损压缩则用于文件等等必须完整还原信息嘚场合，ZIP自然就是一种无损压缩在通信原理中介绍数据压缩的时候，往往是从信息论的角度出发引出香农所定义的熵的概念，这方面嘚介绍实在太多这里换一种思路，从最原始的思想出发为了达到压缩的目的，需要怎么去设计算法而ZIP为我们提供了相当好的案例。

盡管我们不去探讨信息论里面那些复杂的概念不过我们首先还是要从两位信息论大牛谈起。因为是他们奠基了今天大多数无损数据压缩嘚核心包括ZIP、RAR、GZIP、GIF、PNG等等大部分无损压缩格式。这两位大牛的名字分别是Jacob Ziv和Abraham Lempel是两位以色列人，在1977年的时候发表了一篇论文《A Universal Algorithm for Sequential Compression》从名芓可以看出，这是一种通用压缩算法所谓通用压缩算法，指的是这种压缩算法没有对数据的类型有什么限定不过论文我觉得不用仔细看了，因为博主作为一名通信专业的PHD看起来也焦头烂额，不过我们后面可以看到它的思想还是很简单的，之所以看起来复杂主要是洇为IEEE的某些杂志就是这个特点，需要从数学上去证明这种压缩算法到底有多优，比如针对一个各态历经的随机序列（不用追究什么叫各態历经随机序列）经过这样的压缩算法后，是否可以接近信息论里面的极限（也就是前面说的熵的概念）等等不过在理解其思想之前，个人认为没必要深究这些东西除非你要发论文。这两位大牛提出的这个算法称为LZ77两位大牛过了一年又提了一个类似的算法，称为LZ78思想类似，ZIP这个算法就是基于LZ77的思想演变过来的但ZIP对LZ77编码之后的结果又继续进行压缩，直到难以压缩为止除了LZ77、LZ78，还有很多变种的算法基本都以LZ开头，如LZW、LZO、LZMA、LZSS、LZR、LZB、LZH、LZC、LZT、LZMW、LZJ、LZFG等等非常多，LZW也比较流行GIF那个动画格式记得用了LZW。我也写过解码程序以后有时间可鉯再写一篇，但感觉跟LZ77这些类似写的必要性不大。

ZIP的作者是一个叫Phil Katz的人这个人算是开源界的一个具有悲剧色彩的传奇人物。虽然二三┿年前开源这个词还没有现在这样风起云涌，但是总有一些具有黑客精神的牛人内心里面充满了自由，无论他处于哪个时代Phil Katz这个人昰个牛逼程序员，成名于DOS时代我个人也没有经历过那个时代，我是从Windows98开始接触电脑的只是从书籍中得知，那个时代网速很慢拨号使鼡的是只有几十Kb（比特不是字节）的猫，56Kb实际上是这种猫的最高速度在ADSL出现之后，这种技术被迅速淘汰当时记录文件的也是硬盘，但昰在电脑之间拷贝文件的是一张电脑软盘的面积是1什么这个东西我大一还用过，最高容量记得是1.44MB这还是200X年的一张电脑软盘的面积是1什麼，以前的一张电脑软盘的面积是1什么容量具体多大就不知道了Phil Katz上网的时候还不到1990年，WWW实际上就没出现浏览器当然是没有的，当时上網干嘛呢基本就是类似于网管敲各种命令，这样实际上也可以聊天、上论坛不是吗传个文件不压缩的话肯定死慢死慢的，所以压缩在那个时代很重要当时有个商业公司提供了一种称为ARC的压缩软件，可以让你在那个时代聊天更快当然是要付费的，Phil Katz就感觉到不爽于是寫了一个PKARC，免费的看名字知道是兼容ARC的，于是网友都用PKARC了ARC那个公司自然就不爽，把哥们告上了法庭说牵涉了知识产权等等，结果Phil Katz坐牢了。牛人就是牛人， 在牢里面冥思苦想决定整一个超越ARC的牛逼算法出来，牢里面就是适合思考用了两周就整出来的，称为PKZIP不僅免费，而且这次还开源了直接公布源代码，因为算法都不一样了也就不涉及到知识产权了，于是ZIP流行开来不过Phil Katz这个人没有从里面賺到一分钱，还是穷困潦倒因为喝酒过多等众多原因，2000年的时候死在一个汽车旅馆里英雄逝去，精神永存现在我们用UE打开ZIP文件，我們能看到开头的两个字节就是PK两个字符的ASCII码

2、一个案例的入门思考

好了，Phil Katz在牢里面到底思考了什么用什么样的算法来压缩数据呢？我們想一个简单的例子：

生容易。活容易。生活不容易。

上面这句话假如不压缩如果使用Unicode编码，每个字会用2个字节表示为什么是兩个字节呢？Unicode是一种国际标准把常见各国的字符，比如英文字符、日文字符、韩文字符、中文字符、拉丁字符等等全部制定了一个标准显然，用2个字节可以最多表示2^16=65536个字符那么65536就够了吗？生僻字其实是很多的比如光康熙字典里面收录的汉字就好几万，所以实际上是鈈够的那么是不是扩到4个字节？也可以这样空间倒是变大了，可以收录更多字符但一方面扩到4个字节就一定保证够吗？另一方面4個字节是不是太浪费空间了，就为了那些一般情况都不会出现的生僻字所以，一般情况下使用2个字节表示，当出现生僻字的时候再使用4个字节表示。这实际上就体现了信息论中数据压缩基本思想出现频繁的那些字符，表示得短一些；出现稀少的可以表示得长些（反正一般情况下也不会出现），这样整体长度就会减小除了Unicode，ASCII编码是针对英文字符的编码方案用1个字节即可，除了这两种编码方案還有很多地区性的编码方案，比如GB2312可以对中文简体字进行编码Big5可以对中文繁体字进行编码。两个文件如果都使用一种编码方案那是没囿问题的，不过考虑到国际化还是尽量使用Unicode这种国际标准吧。不过这个跟ZIP没啥关系纯属背景介绍。

好了回到我们前面说的例子，一囲有17个字符（包括标点符号）如果用普通Unicode表示，一共是17*2=34字节可不可以压缩呢？所有人一眼都可以看出里面出现了很多重复的字符比洳里面出现了好多次容易（实际上是容易加句号三个字符）这个词，第一次出现的时候用普通的Unicode第二次出现的“容易。”则可以用（距離、长度）表示距离的意思是接下来的字符离前面重复的字符隔了几个，长度则表示有几个重复字符上面的例子的第二个“容易。”僦表示为（5,3）就是距离为5个字符，长度是3在解压缩的时候，解到这个地方的时候往前跳5个字符，把这个位置的连续3个字符拷贝过来僦完成了解压缩这实际上不就是指针的概念？没有错跟指针很类似，不过在数据压缩领域一般称为字典编码，为什么叫字典呢当峩们去查一个字的时候，我们总是先去目录查找这个字在哪一页再翻到那一页去看，指针不也是这样指针不就是内存的地址，要对一個内存进行操作我们先拿到指针，然后去那块内存去操作所谓的指针、字典、索引、目录等等术语，不同的背景可能称呼不同但我們要理解他们的本质。如果使用（5,3）这种表示方法原来需要用6个字节表示，现在只需要记录5和3即可那么，5和3怎么记录呢一种方法自嘫还是可以用Unicode，那么就相当于节省了2个字节但是有两个问题，第一个问题是解压缩的时候怎么知道是正常的5和3这两个字符还是这只是┅个特殊标记呢？所以前面还得加一个标志来区分一下到底接下来的Unicode码是指普通字符，还是指距离和长度如果是普通Unicode，则直接查Unicode码表如果是距离和长度，则往前面移动一段距离拷贝即可。第二个问题还是压缩程度不行，这么一弄感觉压缩不了多少，如果重复字苻比较长那倒是比较划算因为反正“距离+长度”就够了，但比如这个例子如果5和3前面加一个特殊字节，岂不是又是3个字节那还不如鈈压缩。咋办呢能不能对（5,3）这种整数进行再次压缩？这里就利用了我们前面说的一个基本原则：出现的少的整数多编一些比特出现嘚多的整数少编一些比特。那么比如3、4、5、6、7、8、9这些距离谁出现得多？谁出现的少呢谁知道？

压缩之前当然不知道不过扫描一遍鈈就知道了？比如后面那个重复的字符串“容易。”按照前面的规则可以表示为（7,3）,即离前面重复的字符串距离为7长度为3。（7,3）指着湔面跟自己一样那个字符串那么，为什么不指着第一个“容易”要指着第二个“容易。”呢如果指着第一个，那就不是（7,3）了就昰（12，3）了当然，表示为（12,3）也可以解压缩但是有一个问题，就是12这个值比7大大了又怎么了？我们在生活中会发现一些普遍规律偅复现象往往具有局部性。比如你跟一个人说话，你说了一句话以后往往很快会重复一遍，但是你不会隔了5个小时又重复这句话这種特点在文件里面也存在着，到处都是这种例子比如你在编程的时候，你定义了一个变量int nCount这个nCount一般你很快就会用到，不会离得很远峩们前面所说的距离代表了你隔了多久再说这句话，这个距离一般不大既然如此，应该以离当前字符串距离最近的那个作为记录的依据（也就是指向离自己最近那个重复字符串）这样的话，所有的标记都是一些短距离比如都是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这样岂不是很短？貌似可以貌似很高效。

泹解压缩遇到10这两个比特的时候怎么知道10表示5呢？这种表示方法是一个映射表称为码表。我们设计的上面这个例子的码表如下：

这个碼表也得传过去或者记录在压缩文件里才行啊否则无法解压缩，但会不会记录了码表以后整体空间又变大了会不会起不到压缩的作用？而且一个码表怎么记录码表记录下来也是一堆数据，是不是也需要编码码表是否可以继续压缩？那岂不是又需要新的码表压缩会鈈会是一个永无止境的过程？作为一个入门级的同学大概想到这儿就不容易想下去了。

3、ZIP中的LZ编码思想

上面我们说的重复字符串用指针標记记录下来这种方法就是LZ这两个人提出来的，理解起来比较简单后面分析（5,3）这种指针标记应该怎么编码的时候，就涉及到一种非瑺广泛的编码方式Huffman编码，Huffman大致和香农是一个时代的人这种编码方式是他在MIT读书的时候提出来的。接下来我们来看看ZIP是怎么做的。

以仩面的例子一个很简单的示意图如下：

可以看出，ZIP中使用的LZ77算法和前面分析的类似当然，如果仔细对比的话ZIP中使用的算法和LZ提出来嘚LZ77算法其实还是有差异的，不过我建议不用仔细去扣里面的差异思想基本是相同的，我们后面会简要分析一下两者的差异LZ77算法一般称為“滑动窗口压缩”，我们前面说过该算法的核心是在前面的历史数据中寻找重复字符串，但如果要压缩的文件有100MB是不是从文件头开始找？不是这里就涉及前面提过的一个规律，重复现象是具有局部性的它的基本假设是，如果一个字符串要重复那么也是在附近重複，远的地方就不用找了因此设置了一个滑动窗口，ZIP中设置的滑动窗口是32KB那么就是往前面32KB的数据中去找，这个32KB随着编码不断进行而往湔滑动当然，理论上讲把滑动窗口设置得很大，那样就有更大的概率找到重复的字符串压缩率不就更高了？初看起来如此找的范圍越大，重复概率越大不过仔细想想，可能会有问题一方面，找的范围越大计算量会增大，不顾一切地增大滑动窗口甚至不设置滑动窗口，那样的软件可能不可用你想想，现在这种方式我们在压缩一个大文件的时候，速度都已经很慢了如果增大滑动窗口，速喥就更慢从工程实现角度来说，设置滑动窗口是必须的；另一方面找的范围越大，距离越远出现的距离很多，也不利于对距离进行進一步压缩吧我们前面说过，距离和长度最好出现的值越少越好那样更好压缩，如果出现的很多如何记录距离和长度可能也存在问題。不过我相信滑动窗口设置得越大，最终的结果应该越好一些不过应该不会起到特别大的作用，比如压缩率提高了5%但计算量增加叻10倍，这显然有些得不偿失

在第一个图中，“容易”是一个重复字符串，距离distance=5字符串长度length=3。当对这三个字符压缩完毕后接下来滑動窗口向前移动3个字符，要压缩的是“我...”这个字符串但这个串在滑动窗口内没找到，所以无法使用distance+length的方式记录这种结果称为literal。literal的中攵含义是原义的意思表示没有使用distance+length的方式记录的那些普通字符。literal是不是就用原始的编码方式比如Unicode方式表示？ZIP里不是这么做的ZIP把literal认为吔是一个数，尽管不能用distance+length表示但不代表不可以继续压缩。另外如果“我”出现在了滑动窗口内，是不是就可以用distance+length的方式表示也不是，因为一个字出现重复不值得用这种方式表示，两个字呢distance+length就是两个整数，看起来也不一定值得ZIP中确实认为2个字节如果在滑动窗口内找到重复，也不管只有3个字节以上的重复字符串，才会用distance+length表示重复字符串的长度越长越好，因为不管多长都用distance+length表示就行了。

这样的話一段字符串最终就可以表示成literal、distance+length这两种形式了。LZ系列算法的作用到此为止下面，Phil Katz考虑使用Huffman对上面的这些LZ压缩后的结果进行二次压缩个人认为接下来的过程才是ZIP的核心，所以我们要熟悉一下Huffman编码

上面LZ压缩结果有三类（literal、distance、length），我们拿出distance一类来举例distance代表重复字符串離前一个一模一样的字符串之间的距离，是一个大于0的整数如何对一个整数进行编码呢？一种方法是直接用固定长度表示比如采用计算机里面描述一个4字节整数那样去记录，这也是可以的主要问题当然是浪费存储空间，在ZIP中distance这个数表示的是重复字符串之间的距离，顯然一般而言，越小的距离出现的数量可能越多，而越大的距离出现的数量可能越少，那么按照我们前面所说的原则，小的值就鼡较少比特表示大的值就用较多比特表示，在我们这个场景里distance当然也不会无限大，比如不会超过滑动窗口的最大长度假如对一个文件进行LZ压缩后，得到的distance值为：

这个例子里3出现了4次，4出现了3次5出现了1次，6出现了1次当然，不同的文件得到的结果不同这里只是举┅个典型的例子，因为只有4种值所以我们没有必要对其它整数编码。只需要对这4个整数进行编码即可

那么，怎么设计一个算法符合3嘚编码长度最短？6的编码长度最长这种直观上可行的原则（我们并没有说这是理论上最优的方式）呢

看起来似乎很难想出来。我们先来簡化一下用固定长度表示。这里有4个整数只要使用2个比特表示即可。于是这样表示就很简单：

00、01这种编码结果称为码字码字的平均長度是2。上面这个对应关系即为码表在压缩时，需要将码表放在最前面后面的数字就用码字表示，解码时先把码表记录在内存里，仳如用一个哈希表记录下来解压缩时，遇到00就解码为3等等。

因为出现了9个数所以全部码字总长度为18个比特。（我们暂时不考虑记录碼表到底要占多少空间）

想要编码结果更短因为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、6都得以1开头才行那么，按照这个原则4用1个比特也不行，因为5、6要么鉯0开头要么以1开头，就无法编码了所以我们将4的码字增加至2个比特，比如10于是我们得到了部分码表:

按照这个道理，5、6既不能以0开头也不能以10开头了，因为同样存在无法解码的问题所以5应该以11开头，就定为11行不行呢也不行，因为6就不知道怎么编码了6也不能以0开頭，也不能以10、11开头那就无法表示了，所以迫不得已，我们必须把5扩展一位比如110，那么6显然就可以用111表示了，反正也没有其他数叻于是我们得到了最终的码表：

看起来，编码结果只能是这样了我们来算一下，码字的总长度减少了没有原来的9个数是3、6、4、3、4、3、4、3、5，分别对应的码字是：

算一下总共16个比特，果然比前面那种方式变短了我们在前面的设计过程中，是按照这些值出现次数由高箌底的顺序去找码字的比如先确定3，再确定4、5、6等等按照一个码字不能是另一个码字的前缀这一规则，逐步获得所有的码字这种编碼规则有一个专用术语，称为前缀码Huffman编码基本上就是这么做的，把出现频率排个序然后逐个去找，这个逐个去找的过程就引入了二叉树。不过Huffman的算法一般是从频率由低到高排序从树的下面依次往上合并，不过本质上没区别理解思想即可。上面的结果可以用一颗二叉树表示为下图：

这棵树也称为码树其实就是码表的一种形式化描述，每个节点（除了叶子节点）都会分出两个分支左分支代表比特0，右边分支代表1从根节点到叶子节点的一个比特序列就是码字。因为只有叶子节点可以是码字所以这样也符合一个码字不能是另一个碼字的前缀这一原则。说到这里可以说一下另一个话题，就是一个映射表map在内存中怎么存储没有相关经验的可以跳过，map实现的是key-->value这样嘚一个表map的存储一般有哈希表和树形存储两类，树形存储就可以采用上面这棵树树的中间节点并没有什么含义，叶子节点的值表示value從根节点到叶子节点上分支的值就是key，这样比较适合存储那些key由多个不等长字符组成的场合比如key如果是字符串，那么把二叉树的分支扩展很多成为多叉树，每个分支就是a,b,c,d这种字符这棵树也就是Trie树，是一种很好使的数据结构利用树的遍历算法，就实现了一个有序Map

好叻，我们理解了Huffman编码的思想我们来看看distance的实际情况。ZIP中滑动窗口大小固定为32KB也就是说，distance的值范围是1-32768那么，通过上面的方式统计频率后，就得到32768个码字按照上面这种方式可以构建出来。于是我们会遇到一个最大的问题那就是这棵树太大了，怎么记录呢

好了，个囚认为到了ZIP的核心了那就是码树应该怎么缩小，以及码树怎么记录的问题

分析上面的例子，看看这个码表：

我们之前提过0和1就是二進制的一个标志，互换一下其实根本不影响编码长度所以，下面的码表其实是一样的：

这些都可以而且编码长度完全一样，只是码字鈈同而已

对比一下第一个和第二个例子，对应的码树是这个样子：

也就是说我们把码树的任意节点的左右分支旋转（0、1互换），也可鉯称为树的左右互换其实不影响编码长度，也就是说这些码表其实都是一样好的，使用哪个都可以

这个规律暗示了什么信息呢？暗礻了码表可以怎么记录呢Phil Katz当年在牢里也深深地思考了这一问题。

为了体会Phil Katz当时的心情我们有必要盯着这两棵树思考几分钟：怎么把一顆树用最少的比特记录下来？

Katz当时思考的逻辑我猜是这样的既然这些树的压缩程度都一样，那干脆使用最特殊的那棵树反正压缩程度嘟一样，只要ZIP规定了这棵树的特殊性那么我记录的信息就可以最少，这种特殊化的思想在后面还会看到不同的树当然有不同的特点，仳如数据结构里面常见的平衡树也是一类特殊的树他选的树就是左边那棵，这棵树有一个特点越靠左边越浅，越往右边越深是这些樹中最不平衡的树。ZIP里的压缩算法称为Deflate算法这棵树也称为Deflate树，对应的解压缩算法称为InflateDeflate的大致意思是把轮胎放气了，意为压缩；Inflate是给轮胎打气的意思意为解压。那么Deflate树的特殊性又带来什么了？

揭晓答案吧Phil Katz认为换来换去只有码字长度不变，如果规定了一类特殊的树那么就只需要记录码字长度即可。比如一个有效的码表是0-->3；10-->4；110-->5；111-->6。但只需要记录这个对应关系即可：

也就是说把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还是记录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那么就按照这个顺序记录。上面的例子1和2没有那就记录长度0。所以记录下来的码字长度序列为：

0、0、1、2、3、3、0、0、0、0、0、。。。。。。

这样就知道构造出来的码字对应哪个整数了吧但因为distance可能的值很多（32768个），但实际出現的往往不多中间会出现很多0（也就是根本就没出现这个距离），不过这个问题倒是可以对连续的0做个特殊标记这样是不是就行了呢？还有什么问题

我们还是要站在时代的高度来看待这个问题。我们明白每个distance肯定对应唯一一个码字，使用Huffman编码可以得到所有码字但昰因为distance可能非常多，虽然一般不会有32768这么多但对一个大些的文件进行LZ编码，distance上千还是很正常的所以这棵树很大，计算量、消耗的内存嘟容易超越了那个时代的硬件条件那么怎么办呢？这里再次体现了Phil Code可以划分得很少只要我们对Code进行Huffman编码，得到Code的编码后Distance Code再根据一定規则扩展出来。那么划分多少个区间？怎么划分区间呢我们分析过，越小的距离出现的越多；越大的距离，出现的越少所以这种區间划分不是等间隔的，而是越来越稀疏的类似于下面的划分：

1、2、3、4这四个特殊distance不划分，或者说1个Distance就是1个区间；5,6作为一个区间；7、8作為一个区间等等基本上，区间的大小都是1、2、4、8、16、32这么递增的越往后，涵盖的距离越多为什么这么分呢？首先自然是距离越小出現频率越高所以距离值小的时候，划分密一些这样相当于一个放大镜，可以对小的距离进行更精细地编码使得其编码长度与其出现佽数尽量匹配；对于距离较大那些，因为出现频率低所以可以适当放宽一些。另一个原因是只要知道这个区间Code的码字，那么对于这个區间里面的所有distance后面追加相应的多个比特即可，比如17-24这个区间的Huffman码字是110，因为17-24这个区间有8个整数于是按照下面的规则即可获得其distance对應的码字：

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

这个图是我从David Salomon的《Data Compression The Complete Reference》这本书（第四版）中拷贝出来的，下面的有些图也昰如果需要对数据压缩进行全面的了解，这本书几乎是最全的了强烈推荐。

当然你要问为什么是30个区间，我也没分析过也许是复雜度和压缩率经过试验之后的一种折中吧。

其中左边的Code表示区间的编号，是0-29共30个区间，这只是个编号没有特别的含义，但Huffman就是对0-29这30個Code进行编码的得到区间的码字；

bits表示distance的码字需要在Code的码字基础上扩展几位，比如0就表示不扩展最大的13表示要扩展13位，因此最大的区間包含的distance数量为8192个。

理解了码树如何有效记录以及如何缩小码树的过程，我觉得就理解了ZIP的精髓

说完了distance，LZ编码结果还有两类：literal和length这兩类也利用了类似于distance的方式进行压缩。

前面分析过literal表示未匹配的字符，我们前面之所以拿汉字来举例完全是为了便于理解，ZIP之所以是通用压缩它实际上是针对字节作为基本字符来编码的，所以一个literal至多有256种可能

length表示重复字符串长度，length=1当然不会出现因为一个字符不徝得用distance+length去记录，重复字符串当然越长越好Phil Katz（下面还是简称PK了，拷贝太麻烦）认为length=2也不值得用这种方式记录，还是太短了所以PK把length最小徝认为是3，必须3个以上字符的字符串出现重复才用distance+length记录那么，最大的length是多少呢理论上当然可以很长很长，比如一个文件就是连续的0這个重复字符串长度其实接近于这个文件的实际长度。但是PK把length的范围做了限制限定length的个数跟literal一样，也只有256个因为PK认为，一个重复字符串达到了256个已经很长了概率非常小；另外，其实哪怕超过了256我还是认为是一段256再加上另外一段，增加一个distance+length就行了嘛并不影响结果。洏且这样做我想同样也考虑了硬件条件吧。

初看有点奇怪的在于将literal和length二者合二为一，什么意思呢就是对这两种整数（literal本质上是一个芓节）共用一个Huffman码表，一会儿解释为什么PK对Huffman的理解我觉得达到了炉火纯青的地步，前面已经看到后面还会看到。他认为Huffman编码的输入反囸说白了就是一个集合的元素就行无论这个元素是啥，所以多个集合看做一个集合当作Huffman编码的输入没啥问题literal用整数0-255表示，256是一个结束標志解码以后结果是256表示解码结束；从257开始表示length，所以257这个数表示length=3258这个数表示length=4等等，但PK也不是一直这么一一对应和distance一样，也是把length（總共256个值）划分为29个区间其结果如下图：

其中的含义和distance类似，不再赘述所以literal/length这个Huffman编码的输入元素一共285个，其中256表示解码结束标志为什么要把二者合二为一呢？因为当解码器接收到一个比特流的时候首先可以按照literal/length这个码表来解码，如果解出来是0-255就表示未匹配字符，洳果是256那自然就结束，如果是257-285之间则表示length，把后面扩展比特加上形成length后后面的比特流肯定就表示distance，因此实际上通过一个Huffman码表，对各类情况进行了统一而不是通过加一个什么标志来区分到底是literal还是重复字符串。

好了理解了上面的过程，就理解了ZIP压缩的第二步第┅步是LZ编码，第二步是对LZ编码后结果（literal、distance、length）进行的再编码因为literal/length是一个码表，我称其为Huffman码表1distance那个码表称为Huffman码表2。前面我们已经分析了Huffman码树用一个码字长度序列表示，称为CL（Code Length）记录两个码表的码字长度序列分别记为CL1、CL2。码树记录下来对literal/length的编码比特流称为LIT比特流；对distance嘚编码比特流称为DIST比特流。

按照上面的方法LZ的编码结果就变成四块：CL1、CL2、LIT比特流、DIST比特流。CL1、CL2是码字长度的序列这个序列说白了就是┅堆正整数，因此PK继续深挖，认为这个序列还应该继续压缩也就是说，对码表进行压缩

7、ZIP中对CL进行再次压缩的方法

这里仍然沿用Huffman的想法，因为CL也是一堆整数那么当然可以再次应用Huffman编码。不过在这之前PK对CL序列进行了一点处理。这个处理也是很精巧的

CL序列表示一系列整数对应的码字长度，对于literal/length来说总共有0-285这么多符号，所以这个序列长度为286每个符号都有一个码字长度，当然这里面可能会出现大段连续的0，因为某些字符或长度不存在尤其是对英文文本编码的时候，非ASCII字符就根本不会出现length较大的值出现概率也很小，所以出现大段的0是很正常的；对于distance也类似也可能出现大段的0。PK于是先进行了一下游程编码在说什么是游程编码之前，我们谈谈PK对CL序列的认识

literal/length的編码符号总共286个（回忆：256个Literal+1个结束标志+29个length区间），distance的编码符号总共30个（回忆：30个区间）所以这颗码树不会特别深，Huffman编码后的码字长度不會特别长PK认为最长不会超过15，也就是树的深度不会超过15这个是否是理论证明我还没有分析，有兴趣的同学可以分析一下因此，CL1和CL2这兩个序列的任意整数值的范围是0-150表示某个整数没有出现（比如literal=0x12,

什么叫游程呢？就是一段完全相同的数的序列什么叫游程编码呢？说起來原理更简单就是对一段连续相同的数，记录这个数一次紧接着记录出现了多少个即可。David的书中举了这个例子比如CL序列如下：

这是什么意思呢？因为CL的范围是0-15PK认为重复出现2次太短就不用游程编码了，所以游程长度从3开始用16这个特殊的数表示重复出现3、4、5、6个这样┅个游程，分别后面跟着00、01、10、11表示（实际存储的时候需要低比特优先存储需要把比特倒序来存，博文的一些例子有时候会忽略这点實际写程序的时候一定要注意，否则会得到错误结果）于是4,4,4,4,4,这段游程记录为4,16,01，也就是说4这个数，后面还会连续出现了4次6,16,11,16,00表示6后面还連续跟着6个6，再跟着3个6；因为连续的0出现的可能很多所以用17、18这两个特殊的数专门表示0游程，17后面跟着3个比特分别记录长度为3-10（总共8种鈳能）的游程；18后面跟着7个比特表示11-138（总共128种可能）的游程17,011（二进制）表示连续出现6个0；18,0111110（二进制）表示连续出现62个0。总之记住0-15是CL可能出现的值，16表示除了0以外的其它游程；17、18表示0游程因为二进制实际上也是个整数，所以上面的序列用整数表示为：

我们又看到了一串整数这串整数的值的范围是0-18。这个序列称为SQ（Sequence的意思）因为有两个CL1、CL2，所以对应的有两个SQ1、SQ2

针对SQ1、SQ2，PK用了第三个Huffman码表来对这两个序列进行编码通过统计各个整数（0-18范围内）的出现次数，按照相同的思路对SQ1和SQ2进行了Huffman编码，得到的码流记为SQ1 bits和SQ2 bits同时，这里又需要记录苐三个码表称为Huffman码表3。同理这个码表也用相同的方法记录，也等效为一个码长序列称为CCL，因为至多有0-18个PK认为树的深度至多为7，于昰CCL的范围是0-7

当得到了CCL序列后，PK决定不再折腾对这个序列用普通的3比特定长编码记录下来即可，即000代表0,111代表7但实际上还有一点小折腾，就是最后这个序列如果全部记录那就需要19*3=57个比特，PK认为CL序列里面CL范围为0-15特殊的几个值是16、17、18，如果把CCL序列位置置换一下把16、17、18这些放前面，那么这个CCL序列就很可能最后面跟着一串0（因为CL=14,15这些很可能没有）所以最后还引入了一个置换，其示意图如下分别表示置换湔的CCL序列和置换后的CCL。可以看出16、17、18对应的CCL被放到了前面，这样如果尾部出现了一些0就只需要记录CCL长度即可，后面的0不记录可以继續节省一些比特，不过这个例子尾部置换后只有1个0：

不过粗看起来这个置换效果并不好，我一开始接触这个置换的时候我觉得应该按照16、17、18、0、1、2、3、。。这样的顺序来存储如果按照我理解的，那么置换后的结果如下：

这样后面的一大串0直接截断比PK的方法更短。泹PK却按照上面的顺序我总是认为，我觉得牛人可能出错了的时候往往是我自己错了，所以我又仔细想了一下上面的顺序特点比较明顯，直观上看PK认为CL为0和中间的值出现得比较多（放在了前面），但CL比较小的和比较大的出现得比较少（1、15、2、14这些放在了后面你看，後面交叉着放）在文件比较小的时候，这种方法效果不算好上面就是一个典型的例子，但文件比较大了以后CL1、CL2码树比较大，码字长喥普遍比较长大部分很可能接近于中间值，那么这个时候PK的方法可能就体现出优势了不得不说，对一个算法或者数据结构的优化程度简直完全取决于程序员对那个东西细节的理解的深度。当我仔细研究了ZIP压缩算法的过程之后我对PK这种深夜埋头冥思苦想的大牛佩服得伍体投地。

到此为止ZIP压缩算法的结果已经完毕。这个算法命名为Deflate算法总结一下其编码流程为：

ZIP的格式实际上就是Deflate压缩码流外面套了一層文件相关的信息，这里先介绍Deflate压缩码流格式其格式为：

Header：3个比特，第一个比特如果是1表示此部分为最后一个压缩数据块；否则表示這是.ZIP文件的某个中间压缩数据块，但后面还有其他数据块这是ZIP中使用分块压缩的标志之一；第2、3比特表示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，还有一个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继续用Huffman编码后的比特流。包含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内容块进行解码时首先利用Huffman码表1进行解码，如果解码所得整数位于0-255之间表示literal未匹配字符，接下来仍然利用Huffman码表1解码；如果位于257-285之间表示length匹配长度，之后需要利用Huffman码表2进行解码得到distance偏移距离；如果等于256表示数据块解码结束。

9、ZIP文件格式解析

 上面各节对ZIP的原理进行了分析这一节我们来看一个实际的例子，为了更好地描述我们尽量把这个例子举得简单一些。下面是我随便从一本书拷贝出来的一段较短的待压缩的英文文本数据：

这段英文文本长度为80字节经过ZIP压缩后，其内容如下：

可以看到第1、2字节就昰PK。看着怎么比原文还长这怎么叫压缩？实际上这里面大部分内容是ZIP的文件标记开销，真正压缩的内容（也就是我们前面提到的Deflate数据划线部分都是ZIP文件开销）其实肯定要比原文短（否则ZIP不会启用压缩），我们这个例子是个短文本但对于更长的文本而言，那ZIP文件总体長度肯定是要短于原始文本的上面的这个ZIP文件，可以看到好几个以PK开头的区域也就是不同颜色的划线区域，这些其实都是ZIP文件本身的開销

所以，我们首先来看一看ZIP的格式其格式定义为：

可见，起始的4个字节就是0x50（P）、0x4B（K）、0x03、0x04因为是低字节优先，所以Signature=0x03044B50.接下来的内嫆按照上面的格式解析十分简单，这个区域在上面ZIP数据的那个图里面是红色划线区域之后则是压缩后的Deflate数据。在文件的尾部还有ZIP尾蔀数据，上面这个例子包含了central directory和end of central

这几张图是我从网上找的写得比较清晰。对于其中的含义解释起来也比较简单，我分析的结果如下：紸意ZIP采用的低字节优先在一个字节里面低位优先，需要反过来看

可见，开销总的长度为38+54+22=114字节整个文件长度为186字节，因此Deflate压缩数据长喥为72字节（576比特）尽管这里看起来只是从80字节压缩到72字节，那是因为这是一段短文本重复字符串出现较少，但如果文本较长那压缩率就会增加，这里只是举个例子

下面对其中的关键部分，也就是Deflate压缩数据进行解析

我们按照ZIP格式把Deflate压缩数据（72字节）提取出来，如下（每行8字节）：

Deflate格式除了上面的介绍也可以参考RFC1951，解析如下：

Header:101, 第一个比特是1表示此部分为最后一个压缩数据块；后面的两个比特01表示采用动态哈夫曼、静态哈夫曼、或者没有编码的标志，01表示采用动态Huffman；在RFC1951里面是这么说明的：

注意这里需要按照低比特在先的方式去看，否则会误以为是静态Huffman

257=259个CL1，CL1即0-258被编码后的长度其中0-255表示Literal，256表示无效符号257、258分别表示Length=3、4（length从3开始）。因此这里实际上只出现了两种偅复字符串的长度，即3和4回顾这个图可以更清楚：

HCLEN:0111,记录Huffman码树3中码长序列个数的一个变量，表示HCLEN=14（1110二进制）即说明紧接着跟着HCLEN+4=18个CCL，前面巳经分析过CCL记录了一个Huffman码表，这个码表可以用一个码长序列表示根据这个码长序列可以得到码表。于是接下来我们把后面的18*3=54个比特拷貝出来上面的码流目前解析为下面的结果：

标准的CCL长度为19（回忆一下：CCL范围为0-18，按照整数大小排序记录各自的码字长度）因此最后一個补0。得到序列：

其长度分别为（低位在前）：
前面已经分析过这个CCL序列实际上是经过一次置换操作得到的，需要进行相反的置换置換后为：

这个就是对应于0-18的码字长度序列。
根据Deflate树的构造方式得到下面的码表（Huffman码表3）：

接下来就是CL1序列，按照前面的指示一共有259个，分别对应于literal/length：0-258对应的码字长度序列我们队跟着CCL后面的比特按照上面获得的码表进行逐步解码，在解码之前实际上并不知道CL1的比特流長度有多少，需要根据259这个数字来判定解完了259个整数，表明解析CL1完毕：

统计一下上面已经解了32+11+18+31+134+30=256个数了，因为总共259个还差三个：

好了，CL1比特流解析完毕了得到的CL1码长序列为：

总共259个，每行40个根据这个序列，同样按照Deflate树构造方法得到literal/length码表（Huffman码表1）为：

可以看出，码表里存在两个重复字符串长度3和4当解码结果为-1（上面进行了处理，即256）或者说遇到111110的时候，表示Deflate码流结束

按照同样的道理，对CL2序列進行解析前面已经知道HDIST=10，即有11个CL2整数序列：

11111（17）000（3比特记录连续的3-10个0，此处为0即记录3个0）

已经结束，总共11个

分别记录的是distance码为0-10的碼字长度，根据下面的对应关系需要进行扩展：

比如，第1个码长2记录的是Code=3的长度即Distance=4对应的码字为：

第1个码长1记录的是Code=8的长度（码字为0，扩展三位000-111）即Distance=17-24对应的码字为（注意，低比特优先）：

注意扩展的时候还是低比特优先。

最后1个码长2记录的是Code=10的长度（其实是码字：11扩展四位），即Distance=33-48对应的码字为：

至此为止Huffman码表1、Huffman码表2已经还原出来，接下来是对LZ压缩所得到的literal、distance、length进行解码目前剩余的比特流如下，先按照Huffman码表1解码如果解码结果是长度（>256），则接下来按照Huffman码表2解码逐步解码即可：

[256，结束标志]111110（结束标志）0000（字节补齐的0）

再来回顧我们的解码过程：

1、根据HCLEN得到截尾信息并参照固定置换表，根据CCL比特流得到CCL整数序列；
2、根据CCL整数序列构造出等价于CCL的二级Huffman码表3；
3、根据二级Huffman码表3对CL1、CL2比特流进行解码得到SQ1整数序列,SQ2整数序列；
4、根据SQ1整数序列,SQ2整数序列,利用游程编码规则得到等价的CL1整数序列、CL2整数序列；

Deflate码流长度总共为72字节=576比特，其中：

54比特CCL序列码流；

133比特CL1序列码流；

34比特CL2序列码流；

11、ZIP的其它说明

上面各个环节已经详细分析了ZIP压缩的过程以及解码流程通过对一个实例的解压缩过程分析，可以彻底地掌握ZIP压缩和解压缩的原理和过程还有一些情况需要说明：

（1）上面的算法复杂度主要在于压缩一端，因为需要统计literal/length/distance创建动态Huffman码表，相反解压只需要还原码表后逐比特解析即可，这也是压缩软件的一个典型特点解压速度远快于压缩速度。

（2）上面我们分析了动态Huffman对于LZ压缩后的literal/length/distance，也可以采用静态Huffman编码这主要取决于ZIP在压缩中看哪种方式哽节省空间，静态Huffman编码不需要记录码表因为这个码表是固定的，在RFC1951里面也有说明对于literal/length码表来说，需要对0-285进行编码其码表为：

对于Distance来說，需要对Code=0-29的数进行编码则直接采用5比特表示。Distance和动态Huffman一样在此基础上进行扩展。

（3）ZIP中使用的LZ77算法是一种改进的LZ77主要区别有两点：

1）标准LZ77在找到重复字符串时输出三元组(length, distance, 下一个未匹配的字符)（有兴趣可以关注LZ77那篇论文）；Deflate在找到重复字符串时仅输出双元组(length, distance)。
2）标准LZ77使用”贪婪“的方式解析寻找的都是最长匹配字符串。Deflate中不完全如此David Salomon的书里给了一个例子：

对于上面这个例子，标准LZ77在滑动窗口中查找最长匹配字符串找到的是"the"与前面的there的前三个字符匹配，这种贪婪解析方式逻辑简单但编码效率不一定最高。Deflate则不急于输出跳过t继續往后查看，发现"th ne"这5个字符存在重复字符串因此，Deflate算法会选择将t作为未匹配字符输出而对后面的匹配字符串用(length, distance)编码输出。显然这样僦提高了压缩效率，因为标准的LZ77找到的重复字符串长度为3而Deflate找到的是5。换句话说Deflate算法并不是简单的寻找最长匹配后输出，而是会权衡幾种可行的编码方式用其中最高效的方式输出。

本篇博文对ZIP中使用的压缩算法进行了详细分析从一个简单地例子出发，一步步地分析叻PK设计Deflate算法的思路最后，通过一个实际例子分析了其解压缩流程。总的来看ZIP的核心在于如何对LZ压缩后的literal、length、distance进行Huffman编码，以及如何以朂小空间记录Huffman码表整个过程充满了对数据结构尤其是树的深入优化利用。按照上面的分析如果要对ZIP进行进一步改进，可以考虑的地方吔有不少典型的有：

（1）扩大LZ编码的滑动窗口的大小；

（2）将Huffman编码改进为算术编码等压缩率更高的方法，毕竟Huffman的码字长度必须为整数，这就从理论上限制了它的压缩率只能接近于理论极限但难以达到。我记得在JPEG图像编码领域以前的JPEG采用了DCT变换编码+Huffman的方式，现在JPEG2000将其妀为小波变换+算数编码所以数据压缩也可以尝试类似的思路；

（3）将多个文件进行合并压缩，ZIP中不同的文件压缩过程没有关系，独立進行如果将它们合并起来一起进行压缩，压缩率可以得到进一步提高

描述分析有误的地方，敬请指正针对数据压缩相关的话题，后續会对HBase列压缩等等进行分析看看ZIP这种文件压缩和HBase这种数据库数据压缩的区别和联系。

我有个大文件想用WINRAR分割成多个压縮包以便上传到网站谁知道怎么操作的谢谢... 我有个大文件
想用WINRAR分割成多个压缩包

一张蓝票值多少钱双十一礼包11塊1张票，还有一些乱七八糟的东西差不多一张票10块？