数据压缩技术

数据压缩技术用最少的数码来表示信号的技术01技术介绍点评数据压缩的可行性技术简史目录030204基本信息数据压缩技术，就是用最少的数码来表示信号的技术。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大；如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。技术介绍技术介绍在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。1．什么是数据压缩其作用是：能较快地传输各种信号，如传真、Modem通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据存储容量，如CD－ROM、VCD和DVD等；降低发信机功率，这对于多媒体移动通信系统尤为重要。由此看来，通信时间、传输带宽、存储空间甚至发射能量，都可能成为数据压缩的对象。2．数据为何能被压缩首先，数据中间常存在一些多余成分，既冗余度。如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少。冗余度压缩是一个可逆过程，因此叫做无失真压缩，或称保持型编码。数据压缩的可行性数据压缩的可行性数据之所以能被压缩并能保证数据可用，主要是因为数据往往存在着如下几种现象。①数据中间常存在一些多余成分．即冗余度。如在一份计算机文件中．某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等。这些冗余数据便可在数据编码中除去或减少。冗余度压缩是一个可逆过程，因此叫做无失真压缩，或称保持型编码。②数据间尤其是相邻的数据之间，常存在着相关性。如图片中常常有色彩均匀的背景，电视信号的相邻两帧之间可能只有少量的变化景物是不同的，声音信号有时具有一定的规律性和周期性等等。因此，有可能利用某些变换来尽可能地去掉这些相关性数据。但这种变换有时会带来不可恢复的损失和误差．因此叫做不可逆压缩，或称有失真编码、熵压缩等。③人们在欣赏音像节目时，由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限，如人眼对影视节目有视觉暂留效应．人眼或人耳对低于某一极限的幅度变化已无法感知等。因而可将信号中这部分感觉不出的分量压缩掉或“掩蔽掉”。这种压缩同样是一种不可逆压缩。

点评点评随着数据量的不断海量，CPU的不断强劲，双核四核的叫个不停，一种叫做时间换空间的优化技术应该会越来越流行。所以，数据压缩对于今后的数据库来说，应该会从核武器变成常规武器。Oracle从9i开始羞羞答答的引入表级压缩，一直以来都是像中国的核电站一样，宣传的用处大，论实际的贡献就不怎么样了。Oracle11g似乎是正儿八经的要推广数据压缩技术了，专门推出了一个叫做AdvanceCompression的组件，全面支持普通表压缩，非结构化数据压缩（SecureFile数据压缩），DataPump数据压缩，以及RMAN备份压缩，数据压缩技术从此名正言顺的登上历史舞台。既然是专门做为一个Option推出，Oracle一定是对该特性相当有信心，所以需要单独为该特性购买License。在Oracle9i中虽然引入了表压缩，但是有很大的限制。只能对批量装载操作（比如直接路径装载，CTAS等）涉及的数据进行压缩，普通的DML操作的数据是无法压缩的。这应该是对于写操作的压缩难题没有解决，一直遗留到Oracle11g，总算是解决了关系数据压缩的写性能问题。Oracle的表压缩是针对Block级别的数据压缩，主要技术和Oracle9i差不多，还是在Block中引入symbol表，将block中的重复数据在symbol中用一个项表示。Oracle会对block进行批量压缩，而不是每次在block中写入数据时都进行压缩，通过这种方式，可以尽量降低数据压缩对于DML操作的性能影响。这样，在block级别应该会引入一个新的参数，用于控制block中未压缩的数据量达到某个标准以后进行压缩操作。技术简史概率奇缘数学游戏异族传说音画时尚回到未来12345技术简史概率奇缘一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固和司马迁，这种崇尚简约的风俗一直延续到了今天的Internet时代：当我们在BBS上用“7456”代表“气死我了”，或是用“B4”代表“Before”的时候，我们至少应该知道，这其实就是一种最简单的数据压缩呀。严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。远在计算机出现之前，著名的Morse电码就已经成功地实践了这一准则。在Morse码表中，每个字母都对应于一个唯一的点划组合，出现概率最高的字母e被编码为一个点“.”，而出现概率较低的字母z则被编码为“--..”。显然，这可以有效缩短最终的电码长度。信息论之父non第一次用数学语言阐明了概率与信息冗余度的关系。在1948年发表的论文“通信的数学理论（AMathematicalTheoryofCommunication）”中，Shannon指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。Shannon借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。数学游戏设计具体的压缩算法的过程通常更像是一场数学游戏。开发者首先要寻找一种能尽量精确地统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型、自适应模型、Markov模型、部分匹配预测模型等概率统计模型。相对而言，编码方法的发展历程更为曲折一些。1948年，Shannon在提出信息熵理论的同时，也给出了一种简单的编码方法——Shannon编码。1952年，又进一步提出了Fano编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。第一个实用的编码方法是由man在1952年的论文“最小冗余度代码的构造方法（AMethodfortheConstructionofMinimumRedundancyCodes）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为Huffman编码的方法。Huffman编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说，1952年时，年轻的Huffman还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。异族传说逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进Huffman或算术编码，以获得一种兼顾了运行速度和压缩效果的“完美”编码的时候，两个聪明的犹太人J.Ziv和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为LZ系列算法。按照时间顺序，LZ系列算法的发展历程大致是：Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法（AUniversalAlgorithmforSequentialDataCompression）”的论文，论文中描述的算法被后人称为LZ77算法。1978年，二人又发表了该论文的续篇“通过可变比率编码的独立序列的压缩（CompressionofIndividualSequencesviaVariableRateCoding）”，描述了后来被命名为LZ78的压缩算法。1984年，h发表了名为“高性能数据压缩技术（ATechniqueforHighPerformanceDataCompression）”的论文，描述了他在Sperry研究中心（该研究中心后来并入了Unisys公司）的研究成果，这是LZ78算法的一个变种，也就是后来非常有名的LZW算法。1990年后，等人又陆续提出了许多LZ系列算法的变体或改进版本。说实话，LZ系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是简单地延续了千百年来人们对字典的追崇和喜好，并用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。通俗地说，当你用字典中的页码和行号代替文章中每个单词的时候，你实际上已经掌握了LZ系列算法的真谛。音画时尚LZ系列算法基本解决了通用数据压缩中兼顾速度与压缩效果的难题。但是，数据压缩领域里还有另一片更为广阔的天地等待着我们去探索。Shannon的信息论告诉我们，对信息的先验知识越多，我们就可以把信息压缩得越小。换句话说，如果压缩算法的设计目标不是任意的数据源，而是基本属性已知的特种数据，压缩的效果就会进一步提高。这提醒我们，在发展通用压缩算法之余，还必须认真研究针对各种特殊数据的专用压缩算法。比方说，在今天的数码生活中，遍布于数码相机、数码录音笔、数码随身听、数码摄像机等各种数字设备中的图像、音频、视频信息，就必须经过有效的压缩才能在硬盘上存储或是通过USB电缆传输。实际上，多媒体信息的压缩一直是数据压缩领域里的重要课题，其中的每一个分支都有可能主导未来的某个技术潮流，并为数码产品、通信设备和应用软件开发商带来无限的商机。让我们先从图像数据的压缩讲起。通常所说的图像可以被分为二值图像、灰度图像、彩色图像等不同的类型。每一类图像的压缩方法也不尽相同。传真技术的发明和广泛使用促进了二值图像压缩算法的飞速发展。CCITT（国际电报**咨询委员会，是国际电信联盟ITU下属的一个机构）针对传真类应用建立了一系列图像压缩标准，专用于压缩和传递二值图像。这些标准大致包括20世纪70年代后期的CCITTGroup1和Group2，1980年的CCITTGroup3，以及1984年的CCITTGroup4。为了适应不同类型的传真图像，这些标准所用的编码方法包括了一维的MH编码和二维的MR编码，其中使用了行程编码（RLE）和Huffman编码等技术。回到未来从信息熵到算术编码，从犹太人到WinRAR，从JPEG到MP3，数据压缩技术的发展史就像是一个写满了“创新”、“挑战”、“突破”和“变革”的羊皮卷轴。也许，我们在这里不厌其烦地罗列年代、人物、标准和文献，其目的只是要告诉大家，前人的成果只不过是后人有望超越的目标而已，谁知道在未来的几年里，还会出现几个Shannon，几个Huffman呢？谈到未来，我们还可以补充一些与数据压缩技术的发展趋势有关的话题。1994年，M.Burrows和ler共同提出了一种全新的通用数据压缩算法。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换，类似的变换算法被称为Burrows-Wheeler变换，简称BWT。与Ziv和Lempel另辟蹊径的做法如出一辙，Burrows和Wheeler设计的BWT算法与以往所有通用压缩算法的设计思路都迥然不同。如