虽然是老文了，但仍然推荐阅读：压缩大战真相

大战, 真相, 压缩, 阅读, 推荐

此文章转载自2004.10的《大众软件》，原作者为广东 GZ

前言--王者归来？
等待足足两年之久，压缩霸主WinZip终于在万众期待下发布了9.0正式版。全世界自然一片沸腾，在世界各大知名下载网站中，WinZip9.0再次带起下载狂潮。然而此时国内并没有王者回归的欢呼，却一致委婉或直接地表达出失望地情绪，而下载更新的用户也寥寥无几，这绝对是一道国内独特的风景，它不禁让人想问，为什么？从各种评测报告看，因为不支持RAR格式，所以兼容性更佳的WinRAR3.30全面超越固步自封的WinZip9.0-- 原来这就是国内用户抵触WinZip9.0的唯一理由。

苍天已死，黄天当立。这是国内舆论草率的结论。之所以说草率，是因为甚至都没有出现反面声音的媒体，这绝对不是一个成熟正常的氛围。正是这种一边倒的跟风导致了大量用户极端的心态，于是牵强附会、人云亦云和以讹传讹的声音充斥其间。这不由得让人陷入深思，事实上，看似压缩工具之争的表面下深藏的是压缩格式之争。RAR格式即将或者己经取代了ZIP格式吗？不能仅仅从两者的技术表现和统计数据去回答这个问题，计算机数据压缩格式的发展历程是非常独特的，它的王者之选带有传奇的历史烙印，并一直持续产生着决定性的影响。要正确解答这个问题就必须去了解有关数据压缩的历史，任何试图避开历史环境而做出的结论都是轻率的。因此请不妨先认识数据压缩的历史本来，再来决定这些压缩工具的前程是非。

LZ算法--ZIP与RAR共祖同源
要讲压缩的历史，就不可不提LZ算法，这是一种有关数据压缩的算法，何为数据压缩？从本质上讲，数据压缩的目的就是要消除信息中的冗余。早在LZ算法出现之前，研究员们从理论上探讨了压缩算法的数学基础及模型基础，同时也在这些基础上研究出了一些编码方法，其中的Shannon-Fano编码和Huffman编码非常有影响力。但这些编码，包括后来发展出的"算术编码"，都无法成为理想的编码方法--因为它们无法在编码效率和编码速度上同时满足日益增长的压缩需求。这种情况在LZ算法出现时等到了解决。

Shannon编码
1948年贝尔实验室的Shannon发表的论文《通信的数学理论》中指出，任何信息都存在冗余，冗余大小与信息中每个符号的出现概率或者说不确定性有关。Shannon借鉴了热力学的概念，把信息中排除了冗余后的平均信息量成为信息熵，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵同时也奠定了所有数据压缩算法的理论基础。利用信息熵公式，人们可以计算出信息编码的极限。不过完备的理论并不等于实用的技术，要将理论变为实践，编码方法是极为重要的一步。1948年，Shannon在提出信息熵理论的同时，事实上也给出了一种简单的编码方法--Shannon编码。1952年，麻省理工学院的R.M.Fano又进一步提出了Fano编码。两者后来被称为Shannon-Fano编码，这种早期的编码方法揭示了变长的编码方法揭示了变长编码的基本规律，也也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。

Huffman编码
Huffman编码是第一个真正实用的编码方法，由D.A.Huffman在1952年提出。当时Huffman是麻省理工学院的一名学生，据说为了向老师证明自己可以不参加某门功课的期末考试，他设计了这个看似简单却影响深远的编码方法。Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代直到现在，在数据压缩领域得到了广泛的应用。而20世纪80年代初，Huffman编码又出现在CP/M和DOS系统中，即使在今天，在许多知名的压缩工具和压缩算法里（如WinZip、gzip和JPEG），也都有Huffman编码的身影。不过，Huffman编码所得的编码长度只是对信息熵计算结果的一种近似，并不能真正逼近信息熵的极限。Huffman编码影响力很深远，至今还在计算机大专学生必修课程《数据结构》中被提及。

LZ是其发明者J.Ziv和A.Lempel两个犹太人姓氏的缩写。此二人于1977年发表题为《顺序数据压缩的一个通用算法》的论文，论文中描述的算法被后人称为LZ77算法。1978年，二人又发表了该论文的续篇，描述了后来被命名为LZ78的压缩算法。其实LZ系列的算法并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式。它们只是简单的延续了千百年来人们对字典的追崇和喜好，并用一种极为巧妙的方式将字典技术运用于通用数据压缩领域。简单的说如果你习惯用字典中的页码和行号代替文章中的每个单词的时候，那实际上你已经掌握了LZ系列算法的真谛，因此这类编码算法被统称为Dictionary coders。

在1984年，Terry Welch发表论文描述了他在Sperry研究中心（现在Unisys公司的一部分）的研究成果，也就是后来非常有名的LZW算法。它实质上是LZ78算法的一个变种，但被认为是一个独立的编码算法。LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受，实现也相对简单。而在其后发展出来的各式各样的字典编码算法，基本上都是这三种编码算法的分支或变体。也就是说LZ77、LZ78和LZW是字典编码中最基础的3种编码算法。今天我们熟悉的PKZIP、WinZip、WinRAR、gzip等压缩工具都是LZ系列算法的受益者，甚至连PGP这样的加密文件格式也选择了LZ系列算法作为其数据压缩的标准。

字典式编码不但在压缩效果上大大超过了Huffman编码，而且在实现上，压缩和解压缩的速度也异常惊人。于是LZ系列算法的优越性很快就在数据压缩领域里体现出来，使用LZ系列算法的工具软件数量呈爆炸式增长。UNIX系统上最先出现了使用LZW算法的Compress程序，该程序性能优良，很快成为UNIX世界的压缩程序标准。紧随其后的是MS-DOS环境下的ARC程序，还有像PKARC等仿制品。LZ78和LZW一时间几乎统治了UNIX和DOS两大平台。然而随着时间流逝，事情变得耐人寻味。目前为止占据个人用户计算机的主流压缩工具几乎都采用LZ77变种算法，为什么？

叛逆斗士的胜利--ZIP格式诞生
为什么技术实现上更为优秀的LZ78和LZW没有成为最主流的算法？LZ77与它们有什么不同？答案是--专利权。

相对于LZ77完全没有专利限制来说，LZ78在美国稍稍涉及到一些专利禁止区，而LZW正像上文所说的专利权最终归属于Unisys公司。因此直接应用LZ78的算法可能会带来意想不到的麻烦，而所有使用LZW算法（哪怕是他的变体）的人都要获得Unisys公司的专利许可。这种专利限制是相当广泛的，例如GIF图像格式使用了LZW算法，那么所有开发GIF编码/解码器的人都必须要有LZW专利使用许可，这意味着缴纳大笔的专利费。

在DOS年代由于计算机存储介质容量的微小，个人用户对数据压缩软件的渴望是现在的用户无法想象的。例如在1984年，个人计算机的标配不过是容量360kB的5.25寸软盘而已，如果个人能将数据压缩数倍后存储，不啻于节省了一大笔钱。这种渴望在1988年时达到了顶峰，这正是互联网刚刚形成雏形的年代，网络数据交换开始出现。当时最流行的是使用电话线拨号登录别人在家里搭建的服务平台--BBS系统，当时中国也曾有几十个这样的BBS存在，比如水木清华BBS。这种方式不但可以传递文本信息，也可由用户上传文件到站点的计算机以供其他用户下载。不过由于电话线的接入速度慢的可怜，那时的接入标准仅仅是14.4kbit/s，通过BBS传输稍大一点的文件就叫人万分痛苦。于是数据压缩软件就成为了BBS用户一项必须的工具还记得上文提到1985年SEA公司开发的MS-DOS环境下第一个应用LZW算法的ARC压缩软件吗？它是当时MS-DOS下统治性的压缩软件。从技术角度来说ARC确实不错，但使用了专利LZW算法的ARC当然是标准的商业软件，使用这种软件工作就必须付费。不过当时许多玩家根本买不起ARC软件，顺便说一句题外话，那时大多PC玩家基本都没什么富裕的钱，事实上个人计算机本身的发展就是被穷玩家精打细算所推动。不过个人计算机从诞生之日起就充满了叛逆、自由的精神，这也是推动整个个人计算机世界前行的主要动力。此时一个年轻的程序员出现并试图改变压缩世界，这个人叫Phillip W.Katz（菲利普·卡兹）。

20世纪七八十年代出售软件的方式和现在截然不同，以ARC软件来说，它不仅包括了一份EXE可执行文件，还包括它的C语言源代码。经常混迹于BBS上的菲利普·卡兹同样买不起ARC,于是他自己将ARC的C语言源代码进行复制并用汇编语言重写,并将这个压缩工具称作PKARC,这个程序自然与ARC完全兼容,而且由于使用汇编使得速度较ARC更快.在当时的计算机世界里这是一种很普遍的现象,并没有程序员认为这种行为不对,甚至只要不与自己冲突, 被改写者通常也不在乎.不过这次不太一样,菲利普·卡兹不仅仅是自己和朋友用,而是将这个软件以非强迫性注册的共享软件形式向他人发放,但即使是不注册,一样可以毫无限制地使用下去,大批ARC用户自然也就转而使用菲利普·卡兹的软件.SEA其实不是什么大企业,它只是个3人起家的小公司,当然无法接受这种毁灭性打击.以现在的眼光看来,最初SEA的方式是温和的,它接洽菲利普·卡兹并希望通过授权的方式将PKARC纳入旗下,然而并不认为自己有什么过错的菲利普·卡兹一口拒绝,他不想让PKARC成为商业软件, 他制作这个工具的初衷并不是为了赚钱.最终菲利普·卡兹被SEA以侵犯ARC压缩格式编码算法的罪名告上了法庭,并输掉了官司.叛逆倔强的卡兹在败诉后依然拒绝将PKARC授权给SEA公司,而选择了支付法律费用和停止发放PKARC。

这场官司对菲利普·卡兹的人生观和信念影响巨大，追求自由平等的精神并不意味着盲目和法律对抗，试图劫富济贫的少年侠客行为只能逞一时快意，实质上帮助不了任何人。在官司的进行中，菲利普·卡兹一直在持续开发PKARC的后续产品PKPRC，败诉后菲利普·卡兹决定将PKPRC完全重写。很显然，这次再也不能去触犯任何编码算法的专利权了，从3个基本编码算法来衍生自己的算法是必然的，于是去掉有专利权的LZW和LZ78，剩下的就只有LZ77。也许是被激怒后带来了惊人的动力，只用了几周的时间菲利普·卡兹就创造出一个全新的压缩编码算法，该算法完美地结合LZ77和Huffman编码，也就是后来大名鼎鼎的DEFLATE算法了。新压缩软件被命名为PKZIP，而其文件格式扩展名叫作".zip"。PKZIP可将多个文件压缩到一个文件中，无论压缩比、压缩速度都全面超过了商业软件ARC。菲利普·卡兹将PKZIP作为自由软件免费发放，使其如野火般在全美各大BBS上蔓延开来，用户以几何级数增长，遭受毁灭性打击的SEA公司半年内就无声无息。这段故事最后演变为用自由软件打败商业软件的传奇，菲利普·卡兹更是成为充满幻想的年轻程序员心中十步杀一人的偶像。

然而事情如果仅仅到此为止，那么这也不过是菲利普·卡兹为私人恩怨而快意恩仇的行为，未必能得到后人的真正尊重。不过他做出了一个让所有计算机用户都收益无穷的举动，那就是宣布开放ZIP格式，任何人都可以自由使用ZIP编码算法而不需要缴纳任何专利费用。这个决定最终改变了压缩的世界，使得通用数据无损压缩领域再无法出现垄断的商业巨鳄，真正意义上帮助了每个需要压缩的计算机用户。凭借这个无私的行为，菲利普·卡兹真正成为他想成为的英雄。