＋设为首页 ＋添加到收藏夹
数据压缩技术简史
电脑里的数据压缩其实类似于美眉们的瘦身运动,不外有两大功用.第一,可以节省空间.拿瘦身美眉来说,要是八个美眉可以挤进一辆出租车里,那该有多省钱啊！第二,可以减少对带宽的占用.例如,我们都想在不到 100kbps 的 gprs 网上观看 dvd 大片,这就好比瘦身美眉们总希望用一尺布裁出七件吊带衫,前者有待于数据压缩技术的突破性进展,后者则取决于美眉们的恒心与毅力. 【程序编程相关:常用到的几个linux命令】 【推荐阅读:探索软件设计模式（二）】概率奇缘 【扩展信息:Win32程序设计初步之线程】
简单地说,如果没有数据压缩技术,我们就没法用 winrar 为 email 中的附件瘦身;如果没有数据压缩技术,市场上的数码录音笔就只能记录不到 20 分钟的语音;如果没有数据压缩技术,从 internet 上下载一部电影也许要花半年的时间……可是这一切究竟是如何实现的呢?数据压缩技术又是怎样从无到有发展起来的呢?
一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固与司马迁,这种崇尚简约的风俗一直延续到了今天的 internet 时代:当我们在 bbs 上用“ 7456 ”代表“气死我了”,或是用“ b4 ”代表“ before ”的时候,我们至少应该知道,这其实就是一种最简单的数据压缩呀.严格意义上的数据压缩起源于人们对概率的认识.当我们对文字信息进行编码时,如果为出现概率较高的字母赋予较短的编码,为出现概率较低的字母赋予较长的编码,总的编码长度就能缩短不少.远在计算机出现之前,著名的 morse 电码就已经成功地实践了这一准则.在 morse 码表中,每个字母都对应于一个唯一的点划组合,出现概率最高的字母 e 被编码为一个点“ . ”,而出现概率较低的字母 z 则被编码为“ --.. ”.显然,这可以有效缩短最终的电码长度.
信息论之父 c. e. shannon 第一次用数学语言阐明了概率与信息冗余度的关系.在 1948 年发表的论文“通信的数学理论（ a mathematical theory of communication ）”中, shannon 指出,任何信息都存在冗余,冗余大小与信息中每个符号（数字.字母或单词）的出现概率或者说不确定性有关. shannon 借鉴了热力学的概念,把信息中排除了冗余后的平均信息量称为“信息熵”,并给出了计算信息熵的数学表达式.这篇伟大的论文后来被誉为信息论的开山之作,信息熵也奠定了所有数据压缩算法的理论基础.从本质上讲,数据压缩的目的就是要消除信息中的冗余,而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度.利用信息熵公式,人们可以计算出信息编码的极限,即在一定的概率模型下,无损压缩的编码长度不可能小于信息熵公式给出的结果.
有了完备的理论,接下来的事就是要想办法实现具体的算法,并尽量使算法的输出接近信息熵的极限了.当然,大多数工程技术人员都知道,要将一种理论从数学公式发展成实用技术,就像仅凭一个 e=mc 2 的公式就要去制造核武器一样,并不是一件很容易的事.
数学游戏
设计具体的压缩算法的过程通常更像是一场数学游戏.开发者首先要寻找一种能尽量精确地统计或估计信息中符号出现概率的方法,然后还要设计一套用最短的代码描述每个符号的编码规则.统计学知识对于前一项工作相当有效,迄今为止,人们已经陆续实现了静态模型.半静态模型.自适应模型. markov 模型.部分匹配预测模型等概率统计模型.相对而言,编码方法的发展历程更为曲折一些. ... 下一页