数据压缩

数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,两者本质上没啥区别,在数学家看来,都是映射。

一方面在进行通信的时候,有必要将待传输的数据进行压缩,以减少带宽需求;另一方面,计算机存储数据的时候,为了减少磁盘容量需求,也会将文件进行压缩,尽管现在的网络带宽越来越高,压缩已经不像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 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码。

实测

PK。。
    。。。
    。。。

这里也提供了一种思路,可以根据 pk 的开头,确定这是一种 zip 算法。

一个案例的入门思考

好了,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

这个码表也得传过去或者记录在压缩文件里才行啊,否则无法解压缩,但会不会记录了码表以后整体空间又变大了,会不会起不到压缩的作用?

而且一个码表怎么记录?

码表记录下来也是一堆数据,是不是也需要编码?

码表是否可以继续压缩?那岂不是又需要新的码表?压缩会不会是一个永无止境的过程?

作为一个入门级的同学,大概想到这儿就不容易想下去了。

ZIP中的LZ编码思想

上面我们说的重复字符串用指针标记记录下来,这种方法就是LZ这两个人提出来的,理解起来比较简单。

后面分析(5,3)这种指针标记应该怎么编码的时候,就涉及到一种非常广泛的编码方式,Huffman编码,Huffman大致和香农是一个时代的人,这种编码方式是他在MIT读书的时候提出来的。

接下来,我们来看看ZIP是怎么做的。

以上面的例子,一个很简单的示意图如下:

示意图

可以看出,ZIP中使用的LZ77算法和前面分析的类似,当然,如果仔细对比的话,ZIP中使用的算法和LZ提出来的LZ77算法其实还是有差异的,不过我建议不用仔细去扣里面的差异,思想基本是相同的,我们后面会简要分析一下两者的差异。

LZ77 算法

LZ77 算法一般称为“滑动窗口压缩”,我们前面说过,该算法的核心是在前面的历史数据中寻找重复字符串,但如果要压缩的文件有100MB,是不是从文件头开始找?

不是,这里就涉及前面提过的一个规律,重复现象是具有局部性的,它的基本假设是,如果一个字符串要重复,那么也是在附近重复,远的地方就不用找了,因此设置了一个滑动窗口,ZIP中设置的滑动窗口是32KB,那么就是往前面32KB的数据中去找,这个32KB随着编码不断进行而往前滑动。

当然,理论上讲,把滑动窗口设置得很大,那样就有更大的概率找到重复的字符串,压缩率不就更高了?

初看起来如此,找的范围越大,重复概率越大,不过仔细想想,可能会有问题,一方面,找的范围越大,计算量会增大,不顾一切地增大滑动窗口,甚至不设置滑动窗口,那样的软件可能不可用,你想想,现在这种方式,我们在压缩一个大文件的时候,速度都已经很慢了,如果增大滑动窗口,速度就更慢,从工程实现角度来说,设置滑动窗口是必须的;另一方面,找的范围越大,距离越远,出现的距离很多,也不利于对距离进行进一步压缩吧,我们前面说过,距离和长度最好出现的值越少越好,那样更好压缩,如果出现的很多,如何记录距离和长度可能也存在问题。

不过,我相信滑动窗口设置得越大,最终的结果应该越好一些,不过应该不会起到特别大的作用,比如压缩率提高了5%,但计算量增加了10倍,这显然有些得不偿失。

在第一个图中,“容易。”是一个重复字符串,距离distance=5,字符串长度length=3。

当对这三个字符压缩完毕后,接下来滑动窗口向前移动3个字符,要压缩的是“我…”这个字符串,但这个串在滑动窗口内没找到,所以无法使用distance+length的方式记录。这种结果称为literal。literal的中文含义是原义的意思,表示没有使用distance+length的方式记录的那些普通字符。literal是不是就用原始的编码方式,比如Unicode方式表示?

ZIP 处理

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编码。

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个整数进行编码即可。

Huffman 树

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当时的心情,我们有必要盯着这两棵树思考几分钟:怎么把一颗树用最少的比特记录下来?

怎么用最少的 bit 记录下来

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个区间,如下图:

distance

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

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个区间,其结果如下图:

literal

其中的含义和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继续深挖,认为这个序列还应该继续压缩,也就是说,对码表进行压缩。

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-15。

0表示某个整数没有出现(比如literal=0x12, length Code=8, distance Code=15等等)。

游程编码

什么叫游程呢?就是一段完全相同的数的序列。

什么叫游程编码呢?说起来原理更简单,就是对一段连续相同的数,记录这个数一次,紧接着记录出现了多少个即可。

David的书中举了这个例子,比如CL序列如下:

4, 4, 4, 4, 4, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2

那么,游程编码的结果为:

4, 16, 01(二进制), 3, 3, 3, 6, 16, 11(二进制), 16, 00(二进制), 17,011(二进制), 2, 16, 00(二进制)

这是什么意思呢?

因为CL的范围是0-15,PK认为重复出现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游程。因为二进制实际上也是个整数,所以上面的序列用整数表示为:

4, 16, 1, 3, 3, 3, 6, 16, 3, 16, 0, 17, 3, 2, 16, 0

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

ZIP 的处理

针对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、。。。这样的顺序来存储,如果按照我理解的,那么置换后的结果如下:

2、4、0、4、5、5、1、5、0、6、0、0、0、0、0、0、0、0、0

这样后面的一大串0直接截断,比PK的方法更短。但PK却按照上面的顺序。

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

不得不说,对一个算法或者数据结构的优化程度,简直完全取决于程序员对那个东西细节的理解的深度。

当我仔细研究了ZIP压缩算法的过程之后,我对PK这种深夜埋头冥思苦想的大牛佩服得五体投地。

整体流程

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

算法

Deflate 压缩数据格式

ZIP 的格式实际上就是Deflate压缩码流外面套了一层文件相关的信息,这里先介绍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,表示数据块解码结束。

拓展阅读

香农信息论

《A Universal Algorithm for Sequential Data Compression》

《Data Compression The Complete Reference》

  • 压缩算法

Huffman 树

算数编码

游程编码

个人收获

  1. 重复现象具有局部性

  2. 所有的设计都是一种 trade-off

  3. 这位博主的认真态度,值得学习。

参考资料

无意间看到一篇非常好的文档。

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