《数据压缩简史》PPT课件.ppt

数据压缩简史,数据压缩简史（1）,算起来，数据压缩的起源要比计算机的起源早得多，有兴趣的读者可以翻阅一下任何一本成语辞典，查查诸如“二桃三士”、“萧规曹随”之类的短语涵盖了多少信息内容。,数据压缩简史（2）,认真一点：数据压缩技术在计算机技术的萌芽时期就已经被提上了议事日程，有关信息如何被高效存储和传递的话题不断被军事科学家、数学家、电子学家讨论来、讨论去。终于，随着信息论的产生和发展，数据压缩也由热门话题演变成了真正的技术。,通用无损数据压缩（1）,科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。贝尔实验室的ClaudeShannon和MIT的R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。,通用无损数据压缩（2）,D.A.Huffman于1952年第一次发表了他的论文“最小冗余度代码的构造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。UNIX系统上一个不太为现代人熟知的压缩程序COMPACT就是Huffman0阶自适应编码的具体实现。,通用无损数据压缩（3）,80年代初，Huffman编码又在CP/M和DOS系统中实现，其代表程序叫SQ。在数据压缩领域，Huffman的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60年代、70年代乃至80年代的早期，数据压缩领域几乎一直被Huffman编码及其分支所垄断。如果不是后面将要提到的那两个以色列人，也许Huffman编码的0和1的组合中仍在压缩技术中流连忘返。,通用无损数据压缩（4）,让我们沿着Huffman的轨迹再向后跳跃几年，80年代，数学家们不满足于Huffman编码中的某些致命弱点，他们从新的角度入手，遵循Huffman编码的主导思想，设计出另一种更为精确，更能接近信息论中“熵”极限的编码方法算术编码。凭借算术编码的精妙设计和卓越表现，人们终于可以向着数据压缩的极限前进了。,通用无损数据压缩（5）,可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。当然，算术编码同时也给程序员和计算机带来了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快速的计算机系统。,通用无损数据压缩（6）,也就是说，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。这就是为什么算术编码不能在我们日常使用的压缩工具中实现的主要原因。,通用无损数据压缩（7）,那么，能不能既在压缩效果上超越Huffman，又不增加程序对系统资源和时间的需求呢？我们必须感谢下面将要介绍的两个以色列人。直到1977年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们一直在绞尽脑汁为使用Huffman编码的程序找出更快、更好的改进方法。1977年以后，一切都改变了。,通用无损数据压缩（8）,1977年，以色列人JacobZiv和AbrahamLempel发表了论文“顺序数据压缩的一个通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(CompressionofIndividualSequencesviaVariable-RateCoding)。,通用无损数据压缩（9）,所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78(不知为什么，作者名字的首字母被倒置了)。简单地说，这两种压缩方法的思路完全不同于从Shannon到Huffman到算术压缩的传统思路，倒是和本章开头所举的成语辞典的例子颇为相似，因此，人们将基于这一思路的编码方法称作“字典”式编码。,通用无损数据压缩（10）,字典式编码不但在压缩效果上大大超过了Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。,通用无损数据压缩（11）,1984年，TerryWelch发表了名为“高性能数据压缩技术”(ATechniqueforHigh-PerformanceDataCompression)的论文，描述了他在SperryResearchCenter(现在是Unisys的一部分)的研究成果。他实现了LZ78算法的一个变种LZW。,通用无损数据压缩（12）,LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受（有的研究者认为是由于Welch的论文比Ziv和Lempel的更容易理解），实现也比较简单。不久，UNIX上出现了使用LZW算法的Compress程序，该程序性能优良，并有高水平的文档，很快成为了UNIX世界的压缩程序标准。,通用无损数据压缩（13）,紧随其后的是MS-DOS环境下的ARC程序(SystemEnhancementAssociates,1985)，还有象PKWare、PKARC等仿制品。LZ78和LZW一时间统治了UNIX和DOS两大平台。,通用无损数据压缩（14）,80年代中期以后，人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中两个著名的例子。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。,通用无损数据压缩（15）,目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的PKZip到现在的WinZip，特别是随着Internet上文件传输的流行，ZIP格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持ZIP格式。,多媒体信息的压缩（1）,今天的程序员们和设计师们往往乐此不疲地为计算机更换更大的硬盘，增加更多的内存，其主要目的是为了存放和处理越来越多的声音、图像和视频数据。,多媒体信息的压缩（2）,对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。事实上，人们在两条道路上都作了卓有成效的探索。,多媒体信息的压缩（3）,还记得GIF格式吗？GIF可以把原始图形文件以非常小数据量存储，可以在同一个文件中存储多幅图像从而实现动画效果。知道GIF中的图像使用什么方法压缩的吗？LZW!原来如此啊。,多媒体信息的压缩（4）,GIF大概是使用通用压缩技术压缩图像信息的最成功的例子，当然，GIF文件中除了经过LZW压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。GIF精确地保留了原始图像的每一个像素信息，是无损图像压缩的代表。,多媒体信息的压缩（5）,根据媒体特性量身定制的压缩方法中，行程编码(RLE:Run-LengthEncoding)是最为简单、最容易被想到的一种。大多数计算机中产生的图像(和现实世界的图像例如照片不同)都具有着大面积重复的颜色块，为什么非要用无数个完全相同的颜色值来表示某块图像呢？,多媒体信息的压缩（6）,我们完全可以用一个颜色值加一个重复次数来表示这一块图像，冗余度由此减小了，这就是RLE方法的基本思路。显然，它不适于用来压缩照片、声音等很少连续重复信息的数据。RLE方法最有代表性的实现有PCX和Targa图形格式。,多媒体信息的压缩（7）,如果分别考察的话，只有黑白两种颜色的二值图像以及只有256级灰度变化的图像具有一些独特的地方，可以被压缩算法加以利用。我们知道，传真图像是一种典型的二值图像。国际电报电话咨询委员会(CCITT)为此建立了一系列的压缩标准，专门用于压缩传递二值图像（可以是无损的或有损的）。,多媒体信息的压缩（8）,对于灰度图像，除了著名的JPEG标准以外，后文将要介绍的一种叫FELICS的算法可以实现效果非常好的无损压缩。,多媒体信息的压缩（9）,在此基础上，国际标准化组织(ISO)和CCITT联合组成了两个委员会。委员会的名字我们大概都已经非常熟悉了：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。,多媒体信息的压缩（10）,JPEG的压缩目标是静止图像（灰度的和彩色的），MPEG的目标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的数据。他们都取得了令人赞叹的成就。,多媒体信息的压缩（11）,你刚看完VCD吗？那么你刚刚享用过他们为我们带来的乐趣了。知道普通VCD每一帧有多少彩色像素吗？知道每秒钟播放多少帧吗？知道的话，算一算一部100分钟的电影不压缩的话需要多少空间。每张光盘的容量是640M，那么，不压缩的电影需要多少张光盘来存放呢？你该知道JPEG或是MPEG的厉害了吧。,多媒体信息的压缩（12）,最后，必须简单地提到与图像压缩领域相关的电子出版印刷领域中的一种叫做PostScript的东西。PostScript是作为电子印刷业的标准页面描述语言被设计出来的，它起源于1976年的Evans&Sutherland计算机公司，当时的名字是DesignSystem。,多媒体信息的压缩（13）,1978年，JohnWarnock和MartinNewel将其演变为JAM语言。1982年，JohnWarnock和ChuckGeschke创建了著名的AdobeSystem公司，并第三次设计和实现了这个语言，并将其称为PostScript。,多媒体信息的压缩（14）,PostScript的主要思路是存储和传输预先定义的命令来“画”出图像，而不是存储和传输图像的每一个像素，这特别适用于在激光打印机上的输出。采用类似“从(10,10)到(100,100)画一条红色直线”或是“在（50，50）以40为半径画一个蓝色的圆”之类的命令存储图像显然比直接存储每个像素节省了不少地方。,多媒体信息的压缩（15）,所以，从压缩技术的角度来看，PostScript也可以算是压缩方法的一种。根据类似的原理，Windows中的WMF格式、HP的HPGL语言、AutoCAD中使用的DXF格式等等，都可以对某种特定的图像进行有效的压缩。,