数据压缩技术简史

《数据压缩技术简史》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据压缩技术简史来源:2003年9月《CSDN开发高手》作者:王咏刚     电脑里的数据压缩其实类似于美眉们的瘦身运动，不外有两大功用。第一，可以节省空间。拿瘦身美眉来说，要是八个美眉可以挤进一辆出租车里，那该有多省钱啊！第二，可以减少对带宽的占用。例如，我们都想在不到100Kbps的GPRS网上观看DVD大片，这就好比瘦身美眉们总希望用一尺布裁出七件吊带衫，前者有待于数据压缩技术的突破性进展，后者则取决于美眉们的恒心和毅力。     简单地说，如果没有数据压缩技术，我们就没法用WinRAR为Email中的附件瘦身；如果没有数据压缩技术，市

2、场上的数码录音笔就只能记录不到20分钟的语音；如果没有数据压缩技术，从Internet上下载一部电影也许要花半年的时间……可是这一切究竟是如何实现的呢？数据压缩技术又是怎样从无到有发展起来的呢？      概率奇缘     一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固和司马迁，这种崇尚简约的风俗一直延续到了今天的Internet时代：当我们在BBS上用“7456”代表“气死我了”，或是用“B4”代表“Before”的时候，我们至少应该知道，这其实就是一种最简单的数据压缩呀。     严格意义上的数据压缩起源于人们对概率的认识。当

3、我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。远在计算机出现之前，著名的Morse电码就已经成功地实践了这一准则。在Morse码表中，每个字母都对应于一个唯一的点划组合，出现概率最高的字母e被编码为一个点“.”，而出现概率较低的字母z则被编码为“--..”。显然，这可以有效缩短最终的电码长度。     信息论之父C.E.Shannon第一次用数学语言阐明了概率与信息冗余度的关系。在1948年发表的论文“通信的数学理论（AMathematicalTheoryofC

4、ommunication）”中，Shannon指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。Shannon借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能

5、小于信息熵公式给出的结果。     有了完备的理论，接下来的事就是要想办法实现具体的算法，并尽量使算法的输出接近信息熵的极限了。当然，大多数工程技术人员都知道，要将一种理论从数学公式发展成实用技术，就像仅凭一个E=mc2的公式就要去制造核武器一样，并不是一件很容易的事。     数学游戏     设计具体的压缩算法的过程通常更像是一场数学游戏。开发者首先要寻找一种能尽量精确地统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型

6、、自适应模型、Markov模型、部分匹配预测模型等概率统计模型。相对而言，编码方法的发展历程更为曲折一些。     1948年，Shannon在提出信息熵理论的同时，也给出了一种简单的编码方法——Shannon编码。1952年，R.M.Fano又进一步提出了Fano编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。     第一个实用的编码方法是由D.A.Huffman在1952年的论文“最小冗余度代码的构造方法（AMethodfortheConstructionofMinimu

7、mRedundancyCodes）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为Huffman编码的方法。Huffman编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说，1952年时，年轻的Huffman还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。     Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。例如，早期UNIX系统上一个不太为现

8、代人熟知的压缩程序COMPACT实际就是Huffman0阶自适应编码的具体实现。20世纪80年代初，Huffman编码又出现在CP/M和DOS系统中，其代表程序叫S