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

《《数据压缩简史》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据压缩简史》PPT课件.ppt（33页珍藏版）》请在三一办公上搜索。

1、数据压缩简史,数据压缩简史（1）,算起来，数据压缩的起源要比计算机的起源早得多，有兴趣的读者可以翻阅一下任何一本成语辞典，查查诸如“二桃三士”、“萧规曹随”之类的短语涵盖了多少信息内容。,数据压缩简史（2）,认真一点：数据压缩技术在计算机技术的萌芽时期就已经被提上了议事日程，有关信息如何被高效存储和传递的话题不断被军事科学家、数学家、电子学家讨论来、讨论去。终于，随着信息论的产生和发展，数据压缩也由热门话题演变成了真正的技术。,通用无损数据压缩（1）,科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。贝尔实验室的 Claude Shan

2、non 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。,通用无损数据压缩（2）,D.A.Huffman 于 1952 年第一次发表了他的论文“最小冗余度代码的构造方法”(A Method for the Construction of Minimum Redundancy Codes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现。,通用无损数据压缩（3）,80 年代初，Huffman 编

3、码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQ。在数据压缩领域，Huffman 的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60 年代、70 年代乃至 80 年代的早期，数据压缩领域几乎一直被 Huffman 编码及其分支所垄断。如果不是后面将要提到的那两个以色列人，也许Huffman 编码的 0 和 1 的组合中仍在压缩技术中流连忘返。,通用无损数据压缩（4）,让我们沿着 Huffman 的轨迹再向后跳跃几年，80 年代，数学家们不满足于 Huffman 编码中的某些致命弱点，他们从新的角度入手，遵循 Huffman 编码的主导思想，设计出另一种更为精确，更能接近信息

4、论中“熵”极限的编码方法算术编码。凭借算术编码的精妙设计和卓越表现，人们终于可以向着数据压缩的极限前进了。,通用无损数据压缩（5）,可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。当然，算术编码同时也给程序员和计算机带来了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快速的计算机系统。,通用无损数据压缩（6）,也就是说，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。这就是为什么算术编码不能在我们日常使用的压缩工具中实现的主要原因。,通用无损数据压缩（7）,那么，能不能既在压缩效果上超越 H

5、uffman，又不增加程序对系统资源和时间的需求呢？我们必须感谢下面将要介绍的两个以色列人。直到 1977 年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们一直在绞尽脑汁为使用 Huffman 编码的程序找出更快、更好的改进方法。1977 年以后，一切都改变了。,通用无损数据压缩（8）,1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。1978 年，他们发表了该论文的续篇“通过可变比率

6、编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。,通用无损数据压缩（9）,所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为 LZ77 和 LZ78(不知为什么，作者名字的首字母被倒置了)。简单地说，这两种压缩方法的思路完全不同于从 Shannon 到 Huffman 到算术压缩的传统思路，倒是和本章开头所举的成语辞典的例子颇为相似，因此，人们将基于这一思路的编码方法称作“字典”式编码。,通用无损数据压缩（10）,字典式编码不但在压缩效果上大大超过了 Huffman，而且，对于好的实现，

7、其压缩和解压缩的速度也异常惊人。,通用无损数据压缩（11）,1984 年，Terry Welch 发表了名为“高性能数据压缩技术”(A Technique for High-Performance Data Compression)的论文，描述了他在 Sperry Research Center(现在是 Unisys 的一部分)的研究成果。他实现了 LZ78 算法的一个变种 LZW。,通用无损数据压缩（12）,LZW 继承了 LZ77 和 LZ78 压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受（有的研究者认为是由于 Welch 的论文比 Ziv 和 Lempel 的更容易理解），

8、实现也比较简单。不久，UNIX 上出现了使用 LZW 算法的 Compress 程序，该程序性能优良，并有高水平的文档，很快成为了 UNIX 世界的压缩程序标准。,通用无损数据压缩（13）,紧随其后的是 MS-DOS 环境下的 ARC 程序(System Enhancement Associates,1985)，还有象 PKWare、PKARC 等仿制品。LZ78 和 LZW 一时间统治了 UNIX 和 DOS 两大平台。,通用无损数据压缩（14）,80 年代中期以后，人们对 LZ77 进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。Haruyasu Yoshizaki(Yoshi)

9、的 LHarc 和 Robert Jung 的 ARJ 是其中两个著名的例子。LZ77 得以和 LZ78、LZW 一起垄断当今的通用数据压缩领域。,通用无损数据压缩（15）,目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的 PKZip 到现在的 WinZip，特别是随着 Internet 上文件传输的流行，ZIP 格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持 ZIP 格式。,多媒体信息的压缩（1）,今天的程序员们和设计师们往往乐此不疲地为计算机更换更大的硬盘，增加更多的内存，其主要目的是为了存放和处理越来越多的声音、图像和视频数据。,多媒体信息的压缩（2）

10、,对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。事实上，人们在两条道路上都作了卓有成效的探索。,多媒体信息的压缩（3）,还记得 GIF 格式吗？GIF 可以把原始图形文件以非常小数据量存储，可以在同一个文件中存储多幅图像从而实现动画效果。知道 GIF 中的图像使用什么方法压缩的吗？LZW!原来如此啊。,多媒体信息的压缩（4）,GIF 大概是使用通用压缩技术压缩图像信息的最成功的例子，当然，GIF 文件中除了经过 LZW 压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。GIF 精确地保留

11、了原始图像的每一个像素信息，是无损图像压缩的代表。,多媒体信息的压缩（5）,根据媒体特性量身定制的压缩方法中，行程编码(RLE:Run-Length Encoding)是最为简单、最容易被想到的一种。大多数计算机中产生的图像(和现实世界的图像例如照片不同)都具有着大面积重复的颜色块，为什么非要用无数个完全相同的颜色值来表示某块图像呢？,多媒体信息的压缩（6）,我们完全可以用一个颜色值加一个重复次数来表示这一块图像，冗余度由此减小了，这就是 RLE 方法的基本思路。显然，它不适于用来压缩照片、声音等很少连续重复信息的数据。RLE 方法最有代表性的实现有 PCX 和 Targa 图形格式。,多媒体

12、信息的压缩（7）,如果分别考察的话，只有黑白两种颜色的二值图像以及只有 256 级灰度变化的图像具有一些独特的地方，可以被压缩算法加以利用。我们知道，传真图像是一种典型的二值图像。国际电报电话咨询委员会(CCITT)为此建立了一系列的压缩标准，专门用于压缩传递二值图像（可以是无损的或有损的）。,多媒体信息的压缩（8）,对于灰度图像，除了著名的 JPEG 标准以外，后文将要介绍的一种叫 FELICS 的算法可以实现效果非常好的无损压缩。,多媒体信息的压缩（9）,在此基础上，国际标准化组织(ISO)和 CCITT 联合组成了两个委员会。委员会的名字我们大概都已经非常熟悉了：静态图像联合专家小组(J

13、PEG)和动态图像联合专家小组(MPEG)。,多媒体信息的压缩（10）,JPEG 的压缩目标是静止图像（灰度的和彩色的），MPEG 的目标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的数据。他们都取得了令人赞叹的成就。,多媒体信息的压缩（11）,你刚看完 VCD 吗？那么你刚刚享用过他们为我们带来的乐趣了。知道普通 VCD 每一帧有多少彩色像素吗？知道每秒钟播放多少帧吗？知道的话，算一算一部 100 分钟的电影不压缩的话需要多少空间。每张光盘的容量是 640M，那么，不压缩的电影需要多少张光盘来存放呢？你该知道 JPEG

14、或是 MPEG 的厉害了吧。,多媒体信息的压缩（12）,最后，必须简单地提到与图像压缩领域相关的电子出版印刷领域中的一种叫做 PostScript 的东西。PostScript是作为电子印刷业的标准页面描述语言被设计出来的，它起源于 1976 年的 Evans&Sutherland 计算机公司，当时的名字是 Design System。,多媒体信息的压缩（13）,1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，并第三次设计和实现了

15、这个语言，并将其称为 PostScript。,多媒体信息的压缩（14）,PostScript 的主要思路是存储和传输预先定义的命令来“画”出图像，而不是存储和传输图像的每一个像素，这特别适用于在激光打印机上的输出。采用类似“从(10,10)到(100,100)画一条红色直线”或是“在（50，50）以 40 为半径画一个蓝色的圆”之类的命令存储图像显然比直接存储每个像素节省了不少地方。,多媒体信息的压缩（15）,所以，从压缩技术的角度来看，PostScript 也可以算是压缩方法的一种。根据类似的原理，Windows 中的 WMF 格式、HP 的 HPGL 语言、AutoCAD 中使用的 DXF 格式等等，都可以对某种特定的图像进行有效的压缩。,