卡茨，他虽然给世人呈上了最美的ZIP编码，但命运却让人扼腕叹息。糟糕的个人生活习惯和长期编写软件的巨大压力使卡茨染上了酗酒的恶习，年仅37岁就英年早逝。



　　“宽带中国”日前上榜了去年的互联网十件大事，在笔者所在小区，电信光纤入户的活动也搞得风风火火。早期的网络用户可能都还记得用56K Modem上网的痛苦，最早的移动存储介质也只能依靠容量仅为1.44MB的软盘，为了节省文件大小，人们绞尽脑汁，压缩也就应运而生。如今带宽虽然迅猛提高，但是压缩软件仍然是必备软件之一，我们也不禁好奇，压缩这样的好办法，是谁创造出来的呢？


压缩算法的先驱


　　压缩算法的原理：将文字串分块，再设法简化重复文字


　　之所以先提到压缩算法的历史，很大程度上因为对于压缩而言，算法是灵魂。算法之重要如同汽车之引擎，而压缩软件不过是基于该引擎而设计的汽车。对算法的研究由来已久，可以追溯到上个世纪前半叶。

　　最早的比较公认的算法是1948 年克劳德·香农在论文《通信的数学理论》中提到Shannon 编码，它提出信息熵概念的同时也奠定了所有数据压缩算法的理论基础。1952 年，R.M.Fano 又进一步提出了Fano编码。两者后来被称为 Shannon-Fano 编码，这种编码虽揭示了变长编码的基本规律，但因实用性较差，还是避免不了扮演“马前卒”或“先驱”的命运。 

　　第一个真正实用的编码方法是由D.A.Huffman 在 1952 年提出Huffman 编码。据说D.A.Huffman提出该编码的目的十分单纯，仅仅是为了向老师证明自己可以不参加某门功课的期末考试。该编码具有效率高、运算速度快、实现方式灵活等优点，故而从诞生伊始，即得到广泛应用。

　　目前流行压缩软件的算法主要是基于LZ算法。LZ 是其发明者 J.Ziv 和 A.Lempel 两个犹太人姓氏的缩写。因1977 年发表题为《顺序数据压缩的一个通用算法》的论文，论文中描述的算法被后人称为 LZ77 算法。1978 年，二人又发表了该论文的续篇， 该算法即被为 LZ78。之后Terry Welch 在1984年改进了 LZ78 算法，提出了LZW 算法。

　　目前的压缩算法都是基于 LZ77、 LZ78 和 LZW 最基础的3种编码算法。该类算法被统称为 Dictionary coders，基本思路如查字典，核心思想在于用字典中的页码和行号代替文章中的每个单词。字典式编码不但在压缩效果上大大超过了 Huffman 编码，而且压缩和解压缩的速度也异常惊人，于是使用LZ系列算法的工具软件数量呈爆炸式增长。今天我们熟悉的 PKZIP、WinZip、WinRAR、gzip 等压缩 工具都是 LZ 系列算法的受益者。

　　一个耐人寻味的现实是 LZ77这个并不最优的算法大行其道，而更优的 LZ78 和 LZW算法却踪迹难觅。这是为何？很简单的原因，三个字， 专利权；一个字，钱。相对于 LZ77 完全没有专利限制来说，使用LZ78和  LZW算法则要交专利费。

 

叛逆斗士的胜利，ZIP格式诞生
 
　　与宽带互联网时代相比，人们在单机时代对数据压缩更加渴求。当时受网络带宽所限，互联网传输文件实在是叫人痛苦的一件事。传说中的信息高速公路竟然比土路上的牛车还慢了不知多少倍。于是，SEA（System Enhancement Associates）公司携ARC压缩软件应运而生。它生逢其时却又命运多舛，先天基因不足最终导致了昙花一现。先天基因不足是因为它采用专利 LZW 算法，使它不得不成为商业软件。说其命运多舛是因其一面世就遇到了死敌，20多岁的愣头青——菲利普·卡茨。

　　那时的菲利普·卡茨整天沉迷于BBS，喜欢尝鲜，还穷，根本买不起 ARC 软件。穷则思变，何况是才华横溢的愤青小伙。小伙不满ARC的收费，但他搞到一套ARC软件。他仔细阅读了软件附带 的C语言源代码，并用汇编语言重写，将其改头换面为PKARC（（Philip Katz'ARC）。该程序与 ARC完全兼容，且因使用汇编语言而速度更快。当然这事件本身没错，作为个人行为，没人会理会，也不会有人去追究。不过卡茨醉翁之意不在酒，不仅自己和朋友用，而且将其以非强迫性注册的共享软件（免费软件）形式向他人发放，大批ARC用户自然跟风。玩火可以，玩过头了则自然会引火烧身。为生存计，SEA公司曾私下接洽过菲利普·卡茨，希望通过授权的方式将PKARC收编。视收费为敌人的菲利普·卡茨当然一口回绝，让PKARC成为商业软件来赚钱不是他的初衷。 SEA公司一纸诉状将其告上法庭，卡茨也不出意外地输掉了官司。

　　但判决并没有压跨卡茨他选择了对PKPRC完全重写。当然这次不能去触犯任何有专利权的编码算法了，自己完全重写编码也不太现实，别无选择，只能是LZ77。几周后，他就创造出一个全新的压缩编码算法，该算法完美地结合 LZ77 和 Huffman 编码，这就是后来大名鼎鼎的 DEFLATE 算法了。 基于该算法的压缩软件被命名为PKZIP，而其文件格式扩展名叫作“.zip”。PKZIP在性能上全面超过了商业软件ARC，加上作为自由软件免费发放，使其以星火燎原之势在互联网上蔓延，用户以几何级数增长。而SEA公司半年内就无声无息了。

　　更值得世人尊重的是，卡茨脑子完全没有国人的先上车理论，他宣布开放ZIP格式，任何人使用ZIP编码算法都不需要缴纳任何专利费用。而曾经的ZIP王者WinZIP正是利用ZIP的免费，利用其良好的易用性获得了成功。令人扼腕的是，他只是想成为英雄，却成为了落漠的英雄。他获得了精神，却败给了物质。2000年4月14号，年仅37岁的他离开了人世。


RAR，靠破解取得的胜利


　　另外，或许还有一个不是原因的原因：那就是WinRAR的图标（左）很漂亮，而WinZip（右）的一直很丑陋…

　　风水轮流转，吊诡的是，目前的压缩软件市场远不是ZIP一家独大，而是RAR的独霸天下，还有7Z的虎视眈眈。关于RAR编码并没有太多过于神奇的传说，它只是一个70后的叫做Eugene Roshal的俄罗斯青年才俊的个人作品。不过Roshal公开了解码器源码，而RAR编码器一直是有专利的。也就是说别的压缩软件如果不想对RAR编码器专利付费，那对不起，你只能解压RAR格式文件，却不能将文件压缩成RAR格式。

　　与ZIP编码相比，RAR拥有更强的压缩率和高安全性，但这并不足以成为RAR战胜ZIP的理由。软件的收费总是在免费面前显得弱不禁风，但RAR做到了。这主要在于一方面采用ZIP编码的WinZip不兼容采用RAR编码的WinRAR，而WinRAR则是全面兼容WinZip。另一方面，WinRAR面对侵权睁只眼闭只眼，使得RAR格式得到迅速普及。甚至有人说WinRAR当初为了市场，故意放出破解版软件。当WinZip回过神来兼容WinRAR时，WinRAR已占据了市场的半壁江山。RAR的胜利，与其说是技术的胜利，倒不如说是市场策略的胜利。



1948 年 克劳德·香农提出香农压缩编码
1952 年 第一个真正实用的编码方法Huffman 编码出现
1985年 ARC无损压缩软件应运而生
1989年 卡茨编写的PKZIP第一版出现在DOS上
1991年 WinZIP以PKZIP图形版的形式出现在Windows上
1993年 俄罗斯人Eugene编写了WinRAR