电脑里的数据压缩其实类似于美眉们的瘦身运动，不外有两大功用。第一，可以节省空间。拿瘦身美眉来说，要是八个美眉可以挤进一辆出租车里，那该有多省钱啊！第二，可以减少对带宽的占用。例如，我们都想在不到 100Kbps 的 GPRS 网上观看 DVD 大片，这就好比瘦身美眉们总希望用一尺布裁出七件吊带衫，前者有待于数据压缩技术的突破性进展，后者则取决于美眉们的恒心和毅力。
简单地说，如果没有数据压缩技术，我们就没法用 WinRAR 为 Email 中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到 20 分钟的语音；如果没有数据压缩技术，从 Internet 上下载一部电影也许要花半年的时间……可是这一切究竟是如何实现的呢？数据压缩技术又是怎样从无到有发展起来的呢？
概率奇缘
一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固和司马迁，这种崇尚简约的风俗一直延续到了今天的 Internet 时代：当我们在 BBS 上用“ 7456 ”代表“气死我了”，或是用“ B4 ”代表“ Before ”的时候，我们至少应该知道，这其实就是一种最简单的数据压缩呀。
严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。远在计算机出现之前，著名的 Morse 电码就已经成功地实践了这一准则。在 Morse 码表中，每个字母都对应于一个唯一的点划组合，出现概率最高的字母 e 被编码为一个点“ . ”，而出现概率较低的字母 z 则被编码为“ --.. ”。显然，这可以有效缩短最终的电码长度。
信息论之父 C. E. Shannon 第一次用数学语言阐明了概率与信息冗余度的关系。在 1948 年发表的论文“通信的数学理论（ A Mathematical Theory of Communication ）”中， Shannon 指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。 Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。
1948 年， Shannon 在提出信息熵理论的同时，也给出了一种简单的编码方法―― Shannon 编码。 1952 年， R. M. Fano 又进一步提出了 Fano 编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。
第一个实用的编码方法是由 D. A. Huffman 在 1952 年的论文“最小冗余度代码的构造方法（ A Method for the Construction of Minimum Redundancy Codes ）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为 Huffman 编码的方法。 Huffman 编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说， 1952 年时，年轻的 Huffman 还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。
科学家们一直没有放弃向信息熵极限挑战的理想。 1968 年前后， P. Elias 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路， 1976 年， J. Rissanen 提出了一种可以成功地逼近信息熵极限的编码方法――算术编码。 1982 年， Rissanen 和 G. G. Langdon 一起改进了算术编码。之后，人们又将算术编码与 J. G. Cleary 和 I. H. Witten 于 1984 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。今天，那些名为 PPMC 、 PPMD 或 PPMZ 并号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。
对于无损压缩而言， PPM 模型与算术编码相结合，已经可以最大程度地逼近信息熵的极限。看起来，压缩技术的发展可以到此为止了。不幸的是，事情往往不像想象中的那样简单：算术编码虽然可以获得最短的编码长度，但其本身的复杂性也使得算术编码的任何具体实现在运行时都慢如蜗牛。即使在摩尔定律大行其道， CPU 速度日新月异的今天，算术编码程序的运行速度也很难满足日常应用的需求。没办法，如果不是后文将要提到的那两个犹太人，我们还不知要到什么时候才能用上 WinZIP 这样方便实用的压缩工具呢。
异族传说
逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进 Huffman 或算术编码，以获得一种兼顾了运行速度和压缩效果的“完美”编码的时候，两个聪明的犹太人 J. Ziv 和 A. Lempel 独辟蹊径，完全脱离 Huffman 及算术编码的设计思路，创造出了一系列比 Huffman 编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为 LZ 系列算法。
按照时间顺序， LZ 系列算法的发展历程大致是： Ziv 和 Lempel 于 1977 年发表题为“顺序数据压缩的一个通用算法（ A Universal Algorithm for Sequential Data Compression ）”的论文，论文中描述的算法被后人称为 LZ77 算法。 1978 年，二人又发表了该论文的续篇“通过可变比率编码的独立序列的压缩（ Compression of Individual Sequences via Variable Rate Coding ）”，描述了后来被命名为 LZ78 的压缩算法。 1984 年， T. A. Welch 发表了名为“高性能数据压缩技术（ A Technique for High Performance Data Compression ）”的论文，描述了他在 Sperry 研究中心（该研究中心后来并入了 Unisys 公司）的研究成果，这是 LZ78 算法的一个变种，也就是后来非常有名的 LZW 算法。 1990 年后， T. C. Bell 等人又陆续提出了许多 LZ 系列算法的变体或改进版本。
