数据压缩的发展历程[摘要]从最早的莫尔斯电报码到香农第一次用数学语言阐明了概率与信息冗余度的关系;从第一个实用的编码方法到算术编码;从LZ系列算法到JPEG有损压缩编码做了简要介绍,使读者了解数据压缩技术发展历程。[关键词]数据压缩;压缩算法;编码方法;信息冗余;多媒体信息DataCompressionandItsDevelopmentCourse[Abstract]TherelationshipbetweenprobabilityandinformationredundancydegreehasexpoundedfromearliestMorsetelegraphcodetoShannon.Ithasmadethesimpleintroduction,fromfirstpracticalcodemethodtoarithmeticcode,fromLZseriesalgorithmtoJPEGdamagecompressioncode,whichmakesthereadertounderstandthedatacompressiontechnologicaldevelopmentcourse.[Keywords]datacompression;compressionalgorithm;codemethod;informationredundancy;multimediainformation0前言在当今的电子信息技术领域,正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频和音频信号的数据量特别庞大,如果不对其进行有效的压缩就难以得到实际的应用。简单地说,如果没有数据压缩技术,我们就没有办法压缩网页中的图象,也许打开一个网页需要半个小时;如果没有数据压缩技术,从Internet上下载一部电影也许要花半年的时间......,现实中可比这快多了。可是这一切究竟是如何实现的呢?数据压缩技术又是怎样从无到有发展起来的呢?一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固和司马迁,用这种崇尚简约的风俗一直延续到了今天的Internet时代:当我们在QQ上用“886”代表“拜拜”的时候,至少应该知道,这其实就是一种最简单的数据压缩。1数据压缩的发展严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时,如果为出现概率较高的字母赋予较短的编码,为出现概率较低的字母赋予较长的编码,总的编码长度就能缩短不少。远在计算机出现之前,著名的莫尔斯电报码就已经成功地实践了这一准则[1]。在莫尔斯码表中,每个字母都对应于一个唯一的点划组合,出现概率最高的字母e被编码为一个点“.”,而出现概率较低的字母z则被编码为“--..”。显然,这可以有效缩短最终的电码长度[1]。111数据压缩的起源信息论之父香农第一次用数学语言阐明了概率与信息冗余度的关系。在1948年发表的论文“通信的数学理论”中,香农指出,任何信息都存在冗余,冗余大小与信息中每个符号(数字、字母或单词)的出现概率或者说不确定性有关。香农借鉴了热力学的概念,把信息中排除了冗余后的平均信息量称为“信息熵”,并给出了计算信息熵的数学表达式[2]。这篇伟大的论文后来被誉为信息论的开山之作,信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲,数据压缩的目的就是要消除信息中的冗余,而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式,人们可以计算出信息编码的极限,即在一定的概率模型下,无损压缩的编码长度不可能小于信息熵公式给出的结果[3]。1948年香农在提出信息熵理论的同时,也给出了一种简单的编码方法--香农编码。这些早期的编码方法揭示了变长编码的基本规律,也确实可以取得一定的压缩效果,但离真正实用的压缩算法还相差很远。112真正的编码第一个实用的编码方法是由哈夫曼在1952年的论文“最小冗余度代码的构造方法”中提出的。直到今天,许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为哈夫曼编码的方法。哈夫曼编码在计算机界是如此著名,以至于连编码的发明过程本身也成了人们津津乐道的话题。据说,1952年年轻的哈夫曼还是麻省理工学院的一名学生,他为了向老师证明自己可以不参加某门功课的期末考试,才设计了这个看似简单,但却影响深远的编码方法。哈夫曼编码效率高,运算速度快,实现方式灵活,从20世纪60年代至今,在数据压缩领域得到了广泛的应用。例如,早期UNIX系统上一个不太为现代人熟知的压缩程序COMPACT实际就是哈夫曼0阶自适应编码的具体实现。20世纪80年代初,哈夫曼编码又出现在CP/M和DOS系统中,其代表程序叫SQ。今天,在许多知名的压缩工具和压缩算法(如WinRAR、gzip)中,都有哈夫曼编码的身影。不过哈夫曼编...