卡茨，他虽然给世人呈上了最美的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算法则要交专利费。