无损数据压缩算法的历史

(点击上方公众号，可快速关注我们)

英文：IEEE HN

译者：伯乐在线 - kimylrong

链接：http://blog.jobbole.com/77247/

引言

有两种主要的压缩算法：有损和无损。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节，从而使文件变小。在有损压缩里，因某些必要数据的移除，恢复原文件是不可能的。有损压缩主要用来存储图像和音频文件，同时通过移除数据可以达到一个比较高的压缩率，不过本文不讨论有损压缩。无损压缩，也使文件变小，但对应的解压缩功能可以精确的恢复原文件，不丢失任何数据。无损数据压缩被广泛的应用在计算机领域，从节省你个人电脑的空间，到通过web发送数据。使用Secure Shell交流，查看PNG或GIF图片。

无损压缩算法可行的基本原理是，任意一个非随机文件都含有重复数据，这些重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计模型可以用来为特定的字符或者短语生成代码，基于它们出现的频率，配置最短的代码给最常用的数据。这些技术包括熵编码(entropy encoding)、游程编码(run-length encoding)以及字典压缩。运用这些技术以及其它技术，一个8-bit长度的字符或者字符串可以用很少的bit来表示，从而大量的重复数据被移除。

历史

直到20世纪70年代，数据压缩才在计算机领域开始扮演重要角色，那时互联网变得更加流行，Lempel-Ziv算法被发明出来，但压缩算法在计算机领域之外有着更悠久的历史。发明于1838年的Morse code，是最早的数据压缩实例，为英语中最常用的字母比如”e”和”t”分配更短的Morse code。之后，随着大型机的兴起，Claude Shannon和Robert Fano发明了Shannon-Fano编码算法。他们的算法基于符号(symbol)出现的概率来给符号分配编码(code)。一个符号出现的概率大小与对应的编码成反比，从而用更短的方式来表示符号。

两年后，David Huffman在MIT学习信息理论并上了一门Robert Fano老师的课，Fano给班级的同学两个选项，写一篇学期论文或者参加期末考试。Huffman选择的是写学期论文，题目是寻找二叉编码的最优算法。经过几个月的努力后依然没有任何成果，Huffman决定放弃所有论文相关的工作，开始学习为参加期末考试做准备。正在那时，灵感爆发，Huffman找到一个与Shannon-Fano编码相类似但是更有效的编码算法。Shannon-Fano编码和Huffman编码的主要区别是构建概率树的过程不同，前者是自下而上，得到一个次优结果，而后者是自上而下。

早期的Shannon-Fano编码和Huffman编码算法实现是使用硬件和硬编码完成的。直到20世纪70年代互联网以及在线存储的出现，软件压缩才被实现为Huffman编码依据输入数据动态产生。随后，1977年Abraham Lempel 和 Jacob Ziv发表了他们独创性的LZ77算法，第一个使用字典来压缩数据的算法。特别的，LZ77使用了一个叫做slidingwindow的动态字典。1978年，这对搭档发表了同样使用字典的LZ78算法。与LZ77不同，LZ78解析输入数据，生成一个静态字典，不像LZ77动态产生。

法律问题

LZ77和LZ78都快速的流行开来，衍生出多个下图中所示的压缩算法。其中的大多数已经沉寂了，只有那么几个现在被大范围的使用，包括DEFLATE，LZMA以及LZX。绝大多数常用的压缩算法都衍生于LZ77，这不是因为LZ77技术更好，只是由于Sperry在1984年申请了LZ78衍生算法LZW的专利，从而发展受到了专利的阻碍，Sperry开始因专利侵权而起诉软件提供商，服务器管理员，甚至是使用GIF格式但没有License的终端用户。

同时，UNIX压缩工具使用了一个叫LZC的LZW算法微调整版本，之后由于专利问题而被弃用。其他的UNIX开发者也开始放弃使用LZW。这导致UNIX社区采用基于DEFLATE的gzip和基于Burrows-Wheeler Transform的bzip2算法。长远来说，对于UNIX社区这是有好处的，因为gzip和bzip2格式几乎总是比LZW有更好的压缩比。围绕LZW的专利问题已经结束，因为LZW的专利2003年就到期了。尽管这样，LZW算法已经很大程度上被替代掉了，仅仅被使用于GIF压缩中。自那以后，也有一些LZW的衍生算法，不过都没有流行开来，LZ77算法仍然是主流。

另外一场法律官司发生于1993，关于LZS算法。LZS是由Stac Electronics开发的，用于硬盘压缩软件，如Stacker。微软在开发影片压缩软件时使用了LZS算法，开发的软件随着MS-DOS 6.0一起发布，声称能够使硬盘容量翻倍。当Stac Electronics发现自己的知识财产被使用后，起诉了微软。微软随后被判专利侵权并赔偿Stac Electronics1亿2000万美元，后因微软上诉因非故意侵权而减少了1360万美元。尽管Stac Electronics和微软发生了一个那么大的官司，但它没有阻碍Lempel-Ziv算法的开发，不像LZW专利纠纷那样。唯一的结果就是LZS没有衍生出任何算法。

Deflate的崛起

自从Lempel-Ziv算法被发表以来，随着对存储需求的不断增长，一些公司及其他团体开始使用数据压缩技术，这能让他们满足这些需求。然而，数据压缩并没有被大范围的使用，这一局面直到20世纪80年代末期随着互联网的腾飞才开始改变，那时数据压缩的需求出现了。带宽限额，昂贵，数据压缩能够帮助缓解这些瓶颈。当万维网发展起来之后人们开始分享更多的图片以及其它格式的数据，这些数据远比文本大得多，压缩开始变得极其重要。为了满足这些需求，几个新的文件格式被开发出来，包括ZIP，GIF，和PNG。

Thom Henderson通过他的公司发布了第一个成功的商业存档格式，叫做ARC，公司名为为System Enhancement Associates。ARC在BBS社区尤为流行，这是因为它是第一个既可以打包又可以压缩的程序，此外还开放了源代码。ARC格式使用一个LZW的衍生算法来压缩数据。一个叫做Phil Katz的家注意到了ARC的流行并决定用汇编语言来重写压缩和解压缩程序，希望改进ARC。他于1987发布了他的共享软件PKARC程序，不久被Henderson以侵犯版权为由起诉。Katz被认定为有罪，并被迫支付版权费用以及其它许可协议费用。他之所以被认定侵权，是由于PKARC是明显抄袭ARC，甚至于一些注释里面的错别字都相同。

Phil Katz自1988年之后就因许可证问题不能继续出售PKARC，所以1989年他创建了一个PKARC的修改版，就是现在大家熟知的ZIP格式。由于使用了LZW，它被认为专利侵权的，之后Katz选择转而使用新的IMPLODE算法，这种格式于1993年再次被修改，那时Kata发布了PKZIP的2.0版本，那个版本实现了DEFLATE算法以及一些其它特性，如分割容量等。这个ZIP版本也是我们现在随处可见的格式，所有的ZIP文件都遵循PKZIP 2.0格式，尽管它年代久远。

GIF格式，全称Graphics Interchange Format，于1987年由CompuServe创建，允许图像无失真地被共享(尽管这种格式被限定每一帧最多256种颜色)，同时减小文件的大小以允许通过数据机传输。然而，像ZIP格式一样，GIF也是基于LZW算法。尽管专利侵权，Unisys没有办法去阻止GIF的传播。即使是现在，20年后的今天，GIF仍然被使用着，特别是它的动画能力。

尽管GIF没有办法被叫停，CompuServe需找一种不受专利束缚的格式，并于1994年引入了Portable Network Graphics (PNG) 格式。像ZIP一样，PNG使用DEFLATE算法来处理压缩。尽管DELLATE的专利属于Katz，这个专利并不是强性制的，正是这样，PNG以及其它基于DEFLATE的格式避免了专利侵权。尽管LZW在压缩历史的初期占据霸主位置，由于Unisys公司的好诉讼作为，LZW慢慢的淡出主流，大家转而使用更快更高效的DEFLATE算法。现在DEFLATE是使用得最多的算法，有些压缩世界里瑞士军刀的味道。

除了用于PNG和ZIP格式之外，计算机世界里DEFLATE也被频繁的用在其它地方。例如gzip(.gz)文件格式也使用DEFLATE，gzip是ZIP的一个开源版本。其它还包括HTTP, SSL, 以及其它的高效压缩网络传输数据的技术。

遗憾的是，Phil Katz英年早逝，没能看到他的DEFLATE算法统治计算机世界。有几年的时间他酗酒成性，生活也于20世纪90年代末期开始支离破碎，好几次因酒驾或者其它违法行为而被逮捕。Katz于2000年4月14号被发现死于一个酒店的房间，终年37岁。死因是酒精导致的严重胰腺出血，身旁是一堆的空酒瓶。

当前的一些归档软件

ZIP以及其它基于DEFLATE的格式一直占据主导地位，直到20世纪90年代中期，一些新的改进的格式开始出现。1993年，Eugene Roshal发布了一个叫做WinRAR的归档软件，该软件使用RAR格式。最新的RAR结合了PPM和LZSS算法，前面的版本就不太清楚了。RAR开始在互联网分享文件方面成为事实标准，特别是盗版影像的传播。1996年一个叫bzip2d的Burrows-Wheeler Transform算法开源实现发布，并很快在UNIX平台上面流行开来，大有对抗基于DEFLATE算法的gzip格式。1999年另外一个开源压缩程序发布了，以7-Zip或.7z的格式存在，7-Zip应该是第一个能够挑战ZIP和RAR霸主地位的格式，这源于它的高压缩比，模块化以及开放性。这种格式并不仅限于使用一种压缩算法，而是可以在bzip2, LZMA, LZMA2, 和 PPMd算法之间任意选择。最后，归档软件中较新的一个格式是PAQ*格式。第一个PAQ版本于2002年由Matt Mahoney发布，叫做PAQ1。PAQ主要使用一种叫做context mixing的技术来改进PPM算法，context mixing结合了两个甚至是多个统计模型来产生一个更好的符号概率预测，这要比其中的任意一个模型都要好。

压缩技术

有许多不同的技术被用来压缩数据。大多数技术都不能单独使用，需要结合起来形成一套算法。那些能够单独使用的

技术比需要结合的技术通常更加有效。其中的绝大部分都归于entropy编码类别下面，但其它的一些技术也挺常用，如Run-Length Encoding和Burrows-Wheeler Transform。

Run-Length Encoding

Run-Length Encoding是一个非常简单的压缩技术，把重复出现的多个字符替换为重复次数外加字符。单个字符次数为1。RLE非常适合数据重复度比较高的数据，同一行有很多像素颜色相同的渐进图片，也可以结合Burrows-Wheeler Transform等其它技术一起使用。

下面是RLE的一个简单例子:

输入: AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

输出: 3A2B4C1D6E38A

Burrows-Wheeler Transform

Burrows-Wheeler Transform是1994年发明的技术，目的是可逆的处理一段输入数据，使得相同字符连续出现的次数最大化。BWT自身并不做任何的压缩操作，仅简单地转化数据，让Run-Length Encoder等压缩算法可以更有效的编码。

BWT算法很简单:

创建一个字符串数组。

把输入字符串的所有排列组合塞入上述字符串数组。

按照字符顺序为字符串数组排序。

返回数组的最后一列。

BWT通常处理有很多交叉重复字符的长字符串时效果很好。下面是一个有着理想输入的例子，注意