数据压缩.ppt

《数据压缩.ppt》由会员分享，可在线阅读，更多相关《数据压缩.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据压缩简史 数据压缩技术在计算机技术的萌芽时期就已经被提上了议事日程，有关信息如何被高效存储和传递的话题不断被军事科学家、数学家、电子学家讨论来、讨论去。终于，随着信息论的产生和发展，数据压缩也由热门话题演变成了真正的技术。通用无损数据压缩通用无损数据压缩科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的 Shannon-Fano 编码方法。通用无损数据压缩通用无损数据压缩D.A.Huffman 于 1

2、952 年第一次发表了他的论文“最小冗余度代码的构造方法”(A Method for the Construction of Minimum Redundancy Codes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现。80 年代初，Huffman 编码又在 CP/M 和 DOS 系统中实现，其代表程序叫 SQ。在数据压缩领域，Huffman 的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60 年代、70 年代乃至 80 年代的早期，数据压缩领域几乎一直被

3、Huffman 编码及其分支所垄断。如果不是后面将要提到的那两个以色列人，也许我们今天还要在 Huffman 编码的 0 和 1 的组合中流连忘返。让我们沿着 Huffman 的轨迹再向后跳跃几年，80 年代，数学家们不满足于 Huffman 编码中的某些致命弱点，他们从新的角度入手，遵循 Huffman 编码的主导思想，设计出另一种更为精确，更能接近信息论中“熵”极限的编码方法算术编码。凭借算术编码的精妙设计和卓越表现，人们终于可以向着数据压缩的极限前进了。可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。当然，算术编码同时也给程序员和计算机带来

4、了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快速的计算机系统。也就是说，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。这就是为什么算术编码不能在我们日常使用的压缩工具中实现的主要原因。那么，能不能既在压缩效果上超越 Huffman，又不增加程序对系统资源和时间的需求呢？我们必须感谢下面将要介绍的两个以色列人。直到 1977 年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们一直在绞尽脑汁为使用 Huffman 编码的程序找出更快、更好的改进方法。1977 年以后，一切都改变了。1977 年，以色列人 Ja

5、cob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。1978 年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为 LZ77 和 LZ78(不知为什么，作者名字的首字母被倒置了)。简单地说，这两种压缩方法的思路完全不同于从 Shannon 到 Huffm

6、an 到算术压缩的传统思路，倒是和本章开头所举的成语辞典的例子颇为相似，因此，人们将基于这一思路的编码方法称作“字典”式编码。字典式编码不但在压缩效果上大大超过了 Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。1984 年，Terry Welch 发表了名为“高性能数据压缩技术”(A Technique for High-Performance Data Compression)的论文，描述了他在 Sperry Research Center(现在是 Unisys 的一部分)的研究成果。他实现了 LZ78 算法的一个变种 LZW。LZW 继承了 LZ77 和 LZ78 压

7、缩效果好、速度快的优点，而且在算法描述上更容易被人们接受（有的研究者认为是由于 Welch 的论文比 Ziv 和 Lempel 的更容易理解），实现也比较简单。不久，UNIX 上出现了使用 LZW 算法的 Compress 程序，该程序性能优良，并有高水平的文档，很快成为了 UNIX 世界的压缩程序标准。紧随其后的是 MS-DOS 环境下的 ARC 程序(System Enhancement Associates,1985)，还有象 PKWare、PKARC 等仿制品。LZ78 和 LZW 一时间统治了 UNIX 和 DOS 两大平台。80 年代中期以后，人们对 LZ77 进行了改进，随之诞生

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

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

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

11、的图像具有一些独特的地方，可以被压缩算法加以利用。我们知道，传真图像是一种典型的二值图像。国际电报电话咨询委员会(CCITT)为此建立了一系列的压缩标准，专门用于压缩传递二值图像（可以是无损的或有损的）。对于灰度图像，除了著名的 JPEG 标准以外，后文将要介绍的一种叫 FELICS 的算法可以实现效果非常好的无损压缩。70 年代末 80 年代初，人们逐渐意识到，对到多数灰度或是彩色图像乃至声音文件，没有必要忠实地保留其所有信息，在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。到 80 年代末，许多人已经在这一领域取得了不小的收获，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩

12、算法。在此基础上，国际标准化组织(ISO)和 CCITT 联合组成了两个委员会。委员会的名字我们大概都已经非常熟悉了：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。JPEG 的压缩目标是静止图像（灰度的和彩色的），MPEG 的目标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的数据。他们都取得了令人赞叹的成就。你刚看完 VCD 吗？那么你刚刚享用过他们为我们带来的乐趣了。知道普通 VCD 每一帧有多少彩色像素吗？知道每秒钟播放多少帧吗？知道的话，算一算一部 100 分钟的电影不压缩的话需要多少空间。每张

13、光盘的容量是 640M，那么，不压缩的电影需要多少张光盘来存放呢？你该知道 JPEG 或是 MPEG 的厉害了吧。最后，必须简单地提到与图像压缩领域相关的电子出版印刷领域中的一种叫做 PostScript 的东西。PostScript是作为电子印刷业的标准页面描述语言被设计出来的，它起源于 1976 年的 Evans&Sutherland 计算机公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe Syste

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

15、定的图像进行有效的压缩。概率、模型和编码概率、模型和编码什么是熵什么是熵数据压缩不仅起源于 40 年代由 Claude Shannon 首创的信息论，而且其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量：考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数位为：En=-log2(Pn)整条信息的熵也即表示整条信息所需的位数为：E=En举个例子，对下面这条只出现了 a b c 三个字符

16、的字符串：aabbaccbaa字符串长度为 10，字符 a b c 分别出现了 5 3 2 次，则 a b c 在信息中出现的概率分别为 0.5 0.3 0.2，他们的熵分别为：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322整条信息的熵也即表达整个字符串需要的位数为：E=Ea*5+Eb*3+Ec*2=14.855 位回想一下如果用计算机中常用的 ASCII 编码，表示上面的字符串我们需要整整 80 位呢！现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。细心的读

17、者马上会想到，我们该怎样用 0 1 这样的二进制数码表示零点几个二进制位呢？确实很困难，但不是没有办法不是没有办法。一旦我们找到了准确表示零点几个二进制位的方法，我们就有权利向无损压缩的极限挑战了。概率、模型和编码概率、模型和编码模型模型从上面的描述，我们明白，要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。不同的压缩程序通过不同的方法确定符号的出现概率，对符号的概率计算得越准确，也就越容易得到好的压缩效果。在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。概率、模型和编码概率、模型和编码难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模

18、型吗？对上面的字符串我们不是很容易就知道每个字符的概率了吗？是的是的，不过上面的字符串仅有 10 个字符长呀，那只是例子而已。考虑我们现实中要压缩的文件，大多数可是有几十 K 甚至几百 K 长，几 M 字节的文件不是也屡见不鲜吗？概率、模型和编码概率、模型和编码我们可以预先扫描文件中的所有字符，统计出每个字符出现的概率，这种方法在压缩术语里叫做“静态统计模型”。但是，不同的文件中，字符有不同的分布概率，我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。糟糕的是，不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了

19、不少。所以，在实际应用中，“静态统计模型”应用的很少。真正的压缩程序中使用的大多是一种叫“自适应模型”的东西。自适应模型可以说是一台具有学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。也就是说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。上面提到的模型可以统称为“统计模型”，因为他们都是基于对每个字

20、符出现次数的统计得到字符概率的。另一大类模型叫做“字典模型”。实际上，当我们在生活中提到“工行”这个词的时候，我们都知道其意思是指“中国工商银行”，类似的例子还有不少，但共同的前提是我们心中都有一本约定俗成的缩写字典。字典模型也是如此，他并不直接计算字符出现的概率，而是使用一本字典，随着输入信息的读入，模型找出输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信息。匹配越长，压缩效果越好。事实上，字典模型本质上仍然是基于对字符概率的计算的，只不过，字典模型使用整个字符串的匹配代替了对某一字符重复次数的统计。可以证明，字典模型得到的压缩效果仍然无法突破熵的极限。当然，对通用的压缩

21、程序来说，保存一本大字典所需的空间仍然是无法让人忍受的，况且，任何一本预先定义的字典都无法适应不同文件中数据的变化情况。对了，字典模型也有相应的“自适应”方案。我们可以随着信息的不断输入，从已经输入的信息中建立合适的字典，并不断更新这本字典，以适应数据的不断变化。让我们从另一个角度理解一下自适应模型。Cluade Shannon 曾试图通过一个“聚会游戏”(party game)来测定英语的真实信息容量。他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符是什么，一次猜一个，直到猜对为止。然后，Shannon 使用猜测次数来确定整个信息的熵。在这个实验中，一种根据前面出现过的字符

22、估计下一个字符概率的模型就存在于听众的头脑中，比计算机中使用的自适应模型更为高级的是，听众除了根据字符出现过的次数外，还可以根据他们对语言的经验进行猜测。编码编码通过模型，我们已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。最先被考虑的问题是，如果对 a 用 3 个二进制位就可以表示，而对 b 用 4 个二进制位就可以表示，那么，在解码时，面对一连串的二进制流，我怎么知道哪三个位是 a，哪四个位是 b 呢？所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的

23、技术。该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位 0 或 1 组成。看一下前缀编码的一个最简单的例子：符号 编码 A 0 B 10 C 110 D 1110 E 11110 有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：1110010101110110111100010-DABBDCEAAB不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的熵；然后使用不同的编码方法，尽量接近我们期望得到的熵值。所以，压缩效果的好坏一方面取决于模型能否准确地得到字符概率，另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。换句话说，压缩=模型+编码。如下图所示：符号 概率 代码|输入|-|模型|-|编码|-|输出|