数据压缩技术简史new

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

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第一次用数学语言阐明了概率与

4、信息冗余度的关系。在1948年发表的论文“通信的数学理论（AMathematicalTheoryofCommunication）”中，Shannon指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。Shannon借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定

5、理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。     有了完备的理论，接下来的事就是要想办法实现具体的算法，并尽量使算法的输出接近信息熵的极限了。当然，大多数工程技术人员都知道，要将一种理论从数学公式发展成实用技术，就像仅凭一个E=mc2的公式就要去制造核武器一样，并不是一件很容易的事。     数学游戏     设计具体的压缩算法的过程通常更像是一场数学游戏。开发者首先要寻找一种能尽量精确地

6、统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型、自适应模型、Markov模型、部分匹配预测模型等概率统计模型。相对而言，编码方法的发展历程更为曲折一些。     1948年，Shannon在提出信息熵理论的同时，也给出了一种简单的编码方法——Shannon编码。1952年，R.M.Fano又进一步提出了Fano编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果

7、，但离真正实用的压缩算法还相去甚远。     第一个实用的编码方法是由D.A.Huffman在1952年的论文“最小冗余度代码的构造方法（AMethodfortheConstructionofMinimumRedundancyCodes）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为Huffman编码的方法。Huffman编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说，1952年时，年轻的Huffman还是麻省理工学院的一名学生，他为了向老师

8、证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。     Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。例如，早期UNIX系统上一个不太为现代人熟知的压缩程序COMPACT实际就是Huffman0阶自适应编码的具体实现。20世纪80年代初，Huffman编码又出现在CP/M和DOS系统中，其代表程序叫S