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

来源:esingchan - 博客园 链接:www.cnblogs.com/esingchan/p/3958962.html(点击尾部阅读原文前往)

最近自己实现了一个ZIP压缩数据的解压程序,觉得有必要把ZIP压缩格式进行一下详细总结,数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,两者本质上没啥区别,在数学家看来,都是映射。

一方面在进行通信的时候,有必要将待传输的数据进行压缩,以减少带宽需求;另一方面,计算机存储数据的时候,为了减少磁盘容量需求,也会将文件进行压缩,尽管现在的网络带宽越来越高,压缩已经不像90年代初那个时候那么迫切,但在很多场合下仍然需要,其中一个原因是压缩后的数据容量减小后,磁盘访问IO的时间也缩短,尽管压缩和解压缩过程会消耗CPU资源,但是CPU计算资源增长得很快,但是磁盘IO资源却变化得很慢,比如目前主流的SATA硬盘仍然是7200转,如果把磁盘的IO压力转化到CPU上,总体上能够提升系统运行速度。

压缩作为一种非常典型的技术,会应用到很多很多场合下,比如文件系统、数据库、消息传输、网页传输等等各类场合。尽管压缩里面会涉及到很多术语和技术,但无需担心,博主尽量将其描述得通俗易懂。另外,本文涉及的压缩算法非常主流并且十分精巧,理解了ZIP的压缩过程,对理解其它相关的压缩算法应该就比较容易了。

1、引子

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

尽管我们不去探讨信息论里面那些复杂的概念,不过我们首先还是要从两位信息论大牛谈起。因为是他们奠基了今天大多数无损数据压缩的核心,包括ZIP、RAR、GZIP、GIF、PNG等等大部分无损压缩格式。这两位大牛的名字分别是Jacob Ziv和Abraham Lempel,是两位以色列人,在1977年的时候发表了一篇论文《A Universal Algorithm for Sequential Data 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.44MB,这还是200X年的软盘,以前的软盘容量具体多大就不知道了,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–>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系列算法的作用到此为止,下面,Phil Katz考虑使用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互换),也可以称为树的左右互换,其实不影响编码长度,也就是说,这些码表其实都是一样好的,使用哪个都可以。

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

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

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

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

3  4  5  6

1  2  3  3

也就是说,把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 Katz对Huffman编码掌握的深度,他把distance划分成多个区间,每个区间当做一个整数来看,这个整数称为Distance Code。当一个distance落到某个区间,则相当于是出现了那个Code,多个distance对应于一个Distance Code,Distance虽然很多,但Distance 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对应的码字:

17–>110 000

18–>110 001

19–>110 010

20–>110 011

21–>110 100

22–>110 101

23–>110 110

24–>110 111

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

具体来说,Phil Katz把distance划分为30个区间,如下图:

这个图是我从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个。

Distance一列则表示这个区间涵盖的distance范围。

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

6、ZIP中literal和length的压缩方式

说完了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=3,258这个数表示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码表1,distance那个码表称为Huffman码表2。前面我们已经分析了,Huffman码树用一个码字长度序列表示,称为CL(Code Length),记录两个码表的码字长度序列分别记为CL1、CL2。码树记录下来,对literal/length的编码比特流称为LIT比特流;对distance的编码比特流称为DIST比特流。

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

免责声明:本文系网络转载,版权归原作者所有。如涉及版权,请联系删除!

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2016-10-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏take time, save time

你所能用到的无损压缩编码(二)

     上个月项目荷兰大佬要检查,搞的我想写的东西不断推迟,现在检查完了,我决定继续把我想写的这整个一个系列写完,上一次写的是最简单的无损编码行程编码,这一次...

38690
来自专栏大史住在大前端

野生前端的数据结构基础练习(8)——图

图是由边的集合和点的集合组成的。如果图的边有方向(或者说图中的顶点对是有序的)则成为有向图,如果边没有方向则称为无向图。

11230
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(二)No.50

上一次我们说完了用 HashSet 来进行计数了。我们可以发现,如果我们估计有N个数,那么我们至少需要N*32bit(按照int在32位操作系统下占用32个bi...

21280
来自专栏杨建荣的学习笔记

Python之Numpy初识

今天翻了下计划,要学习Numpy了,所以得调动脑细胞的积极性,看看能有什么收获。 首先得了解下什么是Numpy,从我的印象中,一般提到这个工具都会和机器学习关...

370110
来自专栏小红豆的数据分析

小蛇学python(17)时间序列的数据处理

不管是在金融学、经济学的社会学科领域,还是生态学、系统神经的自然学科领域,时间序列数据都是一种重要的结构化数据形式。

22050
来自专栏小樱的经验随笔

CDOJ 1330 柱爷与远古法阵【高斯消元,卡精度】

柱爷与远古法阵 Time Limit: 125/125MS (Java/Others)     Memory Limit: 240000/240000KB (J...

27870
来自专栏代码永生,思想不朽

utf8中文字符串的多模式匹配算法的优化

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

56430
来自专栏简书专栏

基于python的冒泡排序和选择排序

装饰器是python的高级用法,初学者需要单独学习1天才能理解并且熟练运用。 读者如果不理解本节内容,不影响后续内容的理解。 此装饰器只是计算函数运行花费的...

12440
来自专栏c#开发者

设计模式之策略模式(Strategy)

策略模式: 策略模式属于对象行为模式[GOF95]。其用意是针对一组算法,将每一个算法封装到具体共同缄口的独立的类中,从来是的他们可以相互替换。策略模式使得算法...

377140
来自专栏JAVA高级架构

程序员必须掌握的600个英语单词

12420

扫码关注云+社区

领取腾讯云代金券