ZIP压缩算法详细分析及解压实例解释.docx
《ZIP压缩算法详细分析及解压实例解释.docx》由会员分享，可在线阅读，更多相关《ZIP压缩算法详细分析及解压实例解释.docx（31页珍藏版）》请在冰点文库上搜索。
ZIP压缩算法详细分析及解压实例解释
ZIP压缩算法详细分析及解压实例解释
最近自己实现了一个ZIP压缩数据的解压程序，觉得有必要把ZIP压缩格式进行一下详细总结，数据压缩是一门通信原理和计算机科学都会涉及到的学科，在通信原理中，一般称为信源编码，在计算机科学里，一般称为数据压缩，两者本质上没啥区别，在数学家看来，都是映射。
一方面在进行通信的时候，有必要将待传输的数据进行压缩，以减少带宽需求；另一方面，计算机存储数据的时候，为了减少磁盘容量需求，也会将文件进行压缩，尽管现在的网络带宽越来越高，压缩已经不像90年代初那个时候那么迫切，但在很多场合下仍然需要，其中一个原因是压缩后的数据容量减小后，磁盘访问IO的时间也缩短，尽管压缩和解压缩过程会消耗CPU资源，但是CPU计算资源增长得很快，但是磁盘IO资源却变化得很慢，比如目前主流的SATA硬盘仍然是7200转，如果把磁盘的IO压力转化到CPU上，总体上能够提升系统运行速度。
压缩作为一种非常典型的技术，会应用到很多很多场合下，比如文件系统、数据库、消息传输、网页传输等等各类场合。
尽管压缩里面会涉及到很多术语和技术，但无需担心，博主尽量将其描述得通俗易懂。
另外，本文涉及的压缩算法非常主流并且十分精巧，理解了ZIP的压缩过程，对理解其它相关的压缩算法应该就比较容易了。
1、引子
压缩可以分为无损压缩和有损压缩，有损，指的是压缩之后就无法完整还原原始信息，但是压缩率可以很高，主要应用于视频、话音等数据的压缩，因为损失了一点信息，人是很难察觉的，或者说，也没必要那么清晰照样可以看可以听；无损压缩则用于文件等等必须完整还原信息的场合，ZIP自然就是一种无损压缩，在通信原理中介绍数据压缩的时候，往往是从信息论的角度出发，引出香农所定义的熵的概念，这方面的介绍实在太多，这里换一种思路，从最原始的思想出发，为了达到压缩的目的，需要怎么去设计算法。
而ZIP为我们提供了相当好的案例。
尽管我们不去探讨信息论里面那些复杂的概念，不过我们首先还是要从两位信息论大牛谈起。
因为是他们奠基了今天大多数无损数据压缩的核心，包括ZIP、RAR、GZIP、GIF、PNG等等大部分无损压缩格式。
这两位大牛的名字分别是JacobZiv和AbrahamLempel，是两位以色列人，在1977年的时候发表了一篇论文《AUniversalAlgorithmforSequentialDataCompression》，从名字可以看出，这是一种通用压缩算法，所谓通用压缩算法，指的是这种压缩算法没有对数据的类型有什么限定。
不过论文我觉得不用仔细看了，因为博主作为一名通信专业的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的作者是一个叫PhilKatz的人，这个人算是开源界的一个具有悲剧色彩的传奇人物。
虽然二三十年前，开源这个词还没有现在这样风起云涌，但是总有一些具有黑客精神的牛人，内心里面充满了自由，无论他处于哪个时代。
PhilKatz这个人是个牛逼程序员，成名于DOS时代，我个人也没有经历过那个时代，我是从Windows98开始接触电脑的，只是从书籍中得知，那个时代网速很慢，拨号使用的是只有几十Kb（比特不是字节）的猫，56Kb实际上是这种猫的最高速度，在ADSL出现之后，这种技术被迅速淘汰。
当时记录文件的也是硬盘，但是在电脑之间拷贝文件的是软盘，这个东西我大一还用过，最高容量记得是1.44MB，这还是200X年的软盘，以前的软盘容量具体多大就不知道了，PhilKatz上网的时候还不到1990年，WWW实际上就没出现，浏览器当然是没有的，当时上网干嘛呢？
基本就是类似于网管敲各种命令，这样实际上也可以聊天、上论坛不是吗，传个文件不压缩的话肯定死慢死慢的，所以压缩在那个时代很重要。
当时有个商业公司提供了一种称为ARC的压缩软件，可以让你在那个时代聊天更快，当然是要付费的，PhilKatz就感觉到不爽，于是写了一个PKARC，免费的，看名字知道是兼容ARC的，于是网友都用PKARC了，ARC那个公司自然就不爽，把哥们告上了法庭，说牵涉了知识产权等等，结果PhilKatz坐牢了。
。
。
牛人就是牛人，在牢里面冥思苦想，决定整一个超越ARC的牛逼算法出来，牢里面就是适合思考，用了两周就整出来的，称为PKZIP，不仅免费，而且这次还开源了，直接公布源代码，因为算法都不一样了，也就不涉及到知识产权了，于是ZIP流行开来，不过PhilKatz这个人没有从里面赚到一分钱，还是穷困潦倒，因为喝酒过多等众多原因，2000年的时候死在一个汽车旅馆里。
英雄逝去，精神永存，现在我们用UE打开ZIP文件，我们能看到开头的两个字节就是PK两个字符的ASCII码。
2、一个案例的入门思考
好了，PhilKatz在牢里面到底思考了什么？
用什么样的算法来压缩数据呢？
我们想一个简单的例子：
生，容易。
活，容易。
生活，不容易。
上面这句话假如不压缩，如果使用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个小时又重复这句话，这种特点在文件里面也存在着，到处都是这种例子，比如你在编程的时候，你定义了一个变量intnCount，这个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-->0
5-->10
7-->11
这个码表也得传过去或者记录在压缩文件里才行啊，否则无法解压缩，但会不会记录了码表以后整体空间又变大了，会不会起不到压缩的作用？
而且一个码表怎么记录？
码表记录下来也是一堆数据，是不是也需要编码？
码表是否可以继续压缩？
那岂不是又需要新的码表？
压缩会不会是一个永无止境的过程？
作为一个入门级的同学，大概想到这儿就不容易想下去了。
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系列算法的作用到此为止，下面，PhilKatz考虑使用Huffman对上面的这些LZ压缩后的结果进行二次压缩。
个人认为接下来的过程才是ZIP的核心，所以我们要熟悉一下Huffman编码。
4、ZIP中的Huffman编码思想
上面LZ压缩结果有三类（literal、distance、length），我们拿出distance一类来举例。
distance代表重复字符串离前一个一模一样的字符串之间的距离，是一个大于0的整数。
如何对一个整数进行编码呢？
一种方法是直接用固定长度表示，比如采用计算机里面描述一个4字节整数那样去记录，这也是可以的，主要问题当然是浪费存储空间，在ZIP中，distance这个数表示的是重复字符串之间的距离，显然，一般而言，越小的距离，出现的数量可能越多，而越大的距离，出现的数量可能越少，那么，按照我们前面所说的原则，小的值就用较少比特表示，大的值就用较多比特表示，在我们这个场景里，distance当然也不会无限大，比如不会超过滑动窗口的最大长度，假如对一个文件进行LZ压缩后，得到的distance值为：
3、6、4、3、4、3、4、3、5
这个例子里，3出现了4次，4出现了3次，5出现了1次，6出现了1次。
当然，不同的文件得到的结果不同，这里只是举一个典型的例子，因为只有4种值，所以我们没有必要对其它整数编码。
只需要对这4个整数进行编码即可。
那么，怎么设计一个算法，符合3的编码长度最短？
6的编码长度最长这种直观上可行的原则（我们并没有说这是理论上最优的方式）呢？
看起来似乎很难想出来。
我们先来简化一下，用固定长度表示。
这里有4个整数，只要使用2个比特表示即可。
于是这样表示就很简单：
00-->3；01-->4；10-->5; 11-->6。
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，于是我们得到了部分码表:
0-->3；10-->4。
按照这个道理，5、6既不能以0开头，也不能以10开头了，因为同样存在无法解码的问题，所以5应该以11开头，就定为11行不行呢？
也不行，因为6就不知道怎么编码了，6也不能以0开头，也不能以10、11开头，那就无法表示了，所以，迫不得已，我们必须把5扩展一位，比如110，那么，6显然就可以用111表示了，反正也没有其他数了。
于是我们得到了最终的码表：
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编码基本上就是这么做的，把出现频率排个序，然后逐个去找，这个逐个去找的过程，就引入了二叉树。
不过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的核心了，那就是码树应该怎么缩小，以及码树怎么记录的问题。
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。
。
。
。
。
。
这些都可以，而且编码长度完全一样，只是码字不同而已。
对比一下第一个和第二个例子，对应的码树是这个样子：
也就是说，我们把码树的任意节点的左右分支旋转（0、1互换），也可以称为树的左右互换，其实不影响编码长度，也就是说，这些码表其实都是一样好的，使用哪个都可以。
这个规律暗示了什么信息呢？
暗示了码表可以怎么记录呢？
PhilKatz当年在牢里也深深地思考了这一问题。
为了体会PhilKatz当时的心情，我们有必要盯着这两棵树思考几分钟：
怎么把一颗树用最少的比特记录下来？
PhilKatz当时思考的逻辑我猜是这样的，既然这些树的压缩程度都一样，那干脆使用最特殊的那棵树，反正压缩程度都一样，只要ZIP规定了这棵树的特殊性，那么我记录的信息就可以最少，这种特殊化的思想在后面还会看到。
不同的树当然有不同的特点，比如数据结构里面常见的平衡树也是一类特殊的树，他选的树就是左边那棵，这棵树有一个特点，越靠左边越浅，越往右边越深，是这些树中最不平衡的树。
ZIP里的压缩算法称为Deflate算法，这棵树也称为Deflate树，对应的解压缩算法称为Inflate，Deflate的大致意思是把轮胎放气了，意为压缩；Inflate是给轮胎打气的意思，意为解压。
那么，Deflate树的特殊性又带来什么了？
揭晓答案吧，PhilKatz认为换来换去只有码字长度不变，如果规定了一类特殊的树，那么就只需要记录码字长度即可。
比如，一个有效的码表是0-->3；10-->4；110-->5；111-->6。
但只需要记录这个对应关系即可：
3456
1233
也就是说，把1、2、3、3记录下来，解压一边照着左边那棵树的形状构造一颗树，然后只需要1、2、3、3这个信息自然就知道是0、10、110、111。
这就是PhilKatz想出来的ZIP最核心的一点：
这棵码树用码字长度序列记录下来即可。
当然，只把1、2、3、3这个序列记录下来还不行，比如不知道111对应5还是对应6？
所以，构造出树来只是知道了有哪些码字了，但是这些码字到底对应哪些整数还是不知道。
PhilKat
升级会员 