第五讲无损数据压缩.ppt

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

1、第五讲无损数据压缩现在学习的是第1页，共65页压缩编码分类（信息）无损压缩无损压缩指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。无损压缩算法一般压缩比24。常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。有损压缩有损压缩指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。现在学

2、习的是第2页，共65页压缩技术分类通用数据压缩（均为无损压缩）通用数据压缩（均为无损压缩）多媒体数据压缩（无损和有损压缩）多媒体数据压缩（无损和有损压缩）基于统计模型基于统计模型的压缩技术的压缩技术基于字典模型基于字典模型的压缩技术的压缩技术HuffmanHuffman编码编码算术编码算术编码LZ77LZ77LZ78LZ78LZWLZW图像压缩图像压缩音频和视频压缩音频和视频压缩MPEGMPEG等等二值图像二值图像CCITTCCITTJBIGJBIG等等灰度图像灰度图像FELICSFELICSJPEGJPEG等等彩色图像彩色图像RLERLE编码编码JPEGJPEG等等矢量图像矢量图像PostS

3、criptPostScriptWMFWMFCADCAD等等现在学习的是第3页，共65页压缩技术的应用电报、传真(CCITT)通讯(Modem/网络协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)现在学习的是第4页，共65页压缩编码分类（原理）预测编码：PCM，DPCM，DM，LPC统计编码：huffman，shannon，REL，词典编码模型编码变换编码子带编码现在学习的

4、是第5页，共65页压缩编码分类（长度）等长编码等长编码ASCII编码编码不等长编码不等长编码编码长度是不等长的编码长度是不等长的常见编码如常见编码如Huffman编码编码现在学习的是第6页，共65页等长与不等长编码例如：符号序列x=“aabbccccddddeeeeeeee采用ASCII编码：a=01100001b=01100010c=01100011d=01100100e=01100101空=00100000等长编码：24*8=192bit如用后3位进行编码只需要3*24=72bit压缩比为：压缩比为：现在学习的是第7页，共65页等长与不等长编码不等长编码方法字符次数概率码字字长E81/30

5、1D41/61003C41/61013空41/61103A21/12 1110 4B21/12 1111 4需要空间：1*8+3*4+3*4+3*4+2*4+2*4=60平均码长平均码长=总位数/字符出现次数=60/24=2.5现在学习的是第8页，共65页不等长码唯一性问题字符码1码2码3A000B101001C11011011D1110 01111对序列010110译码码1abc码2 daca或ddb或abca现在学习的是第9页，共65页压缩技术起源信息压缩技术的起源比计算机的发明早几千年现在学习的是第10页，共65页信息论信息存在冗余信息存在冗余通过采用一定通过采用一定的模型和编码方法，的

6、模型和编码方法，可以降低这种冗余度可以降低这种冗余度贝尔实验室的ClaudeShannon和MIT的R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。现在学习的是第11页，共65页D.A.Huffman1952年发表论文：“最小冗余度代码的构造方法”A Method for the Construction of Minimum Redundancy CodesUNIX系统上一个不太为现代人熟知的压缩程序COMPACT就是Huffman0阶自适应编码的具体实现80年代初，Huffman编码又在CP/M和DOS系统中实现，其代表程序叫SQH

7、uffman时代：时代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期现在学习的是第12页，共65页接近极限熵80年代早期，数学家们设计出算术编码方法(ArithmeticCoding)可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容q但是，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(PredicationbyPartialmatching,PPM)技术的变体现在学习的是第13页，共65页以色列人Jacob ZivJacob Ziv 和 Abraham Lem

8、pelAbraham Lempel1978年发表论文：“通过可变比率编码的独立序列的压缩”Compression of Individual Sequences via Variable-Rate Coding字典编码时代：字典编码时代：LZ77和和LZ78压缩算法压缩算法1977年发表论文：“顺序数据压缩的一个通用算法”A Universal Algorithm for Sequential Data Compression现在学习的是第14页，共65页LZW算法Terry Welch Welch实现了LZ78算法的一个变种LZW算法UNIX：使用LZW算法的Compress程序MS-DOS

9、：ARC程序，以及PKWare、PKARC等仿制品。1984年发表论文：“高性能数据压缩技术”A Technique for High-Performance Data Compression 现在学习的是第15页，共65页通用数据压缩80年代中期以后，对LZ77算法进行改进HaruyasuYoshizaki(Yoshi)的LHarcRobertJung的ARJ从PKZip到WinZip：通用数据压缩格式标准 ZIPLZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域一起垄断当今的通用数据压缩领域现在学习的是第16页，共65页多媒体数据压缩q国际电报电话咨询委员会(CCITT)：针对二值

10、图像的一系列压缩标准，如CCITTGroup3、CCITTGroup4等(此外还包括CCITT与ISO共同制订的JBIG标准)。q70年代末80年代初：数学家们提出了损失压缩精度以换取压缩率损失压缩精度以换取压缩率的崭新思路的崭新思路。国际标准化组织(ISO)和CCITT联合组成了两个委员会：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。诞生了JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7等系列标准。qPostScript矢量图形格式：起源于1976年的Evans&Sutherland计算机公司，当时的名字是DesignSystem。1978年，John

11、Warnock和MartinNewel将其演变为JAM语言。1982年，JohnWarnock和ChuckGeschke创建了著名的AdobeSystem公司，第三次设计和实现了这个语言，并称其为PostScript。现在学习的是第17页，共65页无损压缩模型使用模型：得到字符或单词在信息中出现的概率静态/半静态模型自适应模型静态字典模型自适应字典模型统计模型字典模型现在学习的是第18页，共65页信息熵及基本概念1信息量信息量信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量，也就是在辨识N个事件中特定的一个事件的过程中所需要提问“是或否”的最少次数。设从N个数中选定任一个数x

12、j的概率为p（xj），假定选定任意一个数的概率都相等，即p（xj）1/N，因此定义其信息量为:式中，P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发出xj这个消息（随机事件）后，接收端收到信息量的量度。现在学习的是第19页，共65页信息熵熵熵来源于40年代由ClaudeShannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量。信源S发出的xj（j=1,2,n）共n个随机事件的自信息统计平均，即H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。其中：等概率事件的熵最大，为：当P(x1)1时，

13、P(x2)P(x3)P(xj)0，由（4-6）式得此时熵为由上可得熵的范围为：由上可得熵的范围为：现在学习的是第20页，共65页在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，则当LcH(S)有冗余，不是最佳。LcH(S)不可能。LcH(S)最佳编码（Lc稍大于H(S)）。熵值为平均码长Lc的下限。平均码长Lc的计算公式为：（j=1,2,n）其中：P(xj)是信源X发出xj的概率，L(xj)为xj的编码长。平均码长与熵关系现在学习的是第21页，共65页熵的计算范例例：对信息aabbaccbaa，字符串长度为10，字符a、b、c分别出现了5、3、2次，则Ia=-log2

14、(0.5)=1Ib=-log2(0.3)=1.737Ic=-log2(0.2)=2.322H（S）=0.5Ia+0.3Ib+0.2Ic=1.4855如采用等长编码，则每个字符需要位；总的码长:L=5*+3*+2*=位对比一下，我们用ASCII编码表示该信息需要80位现在学习的是第22页，共65页统计编码（熵）统计编码是根据消息出现概率的分布特性而进行的压缩编码在消息和码字间找到明确的一一对应关系，以便恢复时能准确无误再现出来现在学习的是第23页，共65页技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的

15、位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符字符编码编码A0B10C110D1110E111101110010101110110111100010 D A B B D C E A A B 现在学习的是第24页，共65页技术准备：压缩=模型+编码输入模型编码输出符号概率代码现在学习的是第25页，共65页Shannon-Fano编码采用从上到下的方法进行编码。仙农-范诺(Shannon-Fano)算法：首先按照符号出现的频度或概率排序，使用递归方法分成两个部分，每一部分具有近似相同的次数（概率）当概率和为1，进行编码现在学习的是第26页，共65

16、页Shannon-Fano编码例有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。符 号ABCDE出现的次数157765H(S)=(15/40)*(40/15)+(7/40)*(40/7)+(5/40)*(40/5)=2.196这就是说每个符号用2.196位表示，40个象素需用87.84位现在学习的是第27页，共65页Shannon-Fano编码例符号出现的次数()分配的代码需要的

17、位数A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115现在学习的是第28页，共65页Shannon-Fano编码例例题：例题：cabcedeacacdeddaaabaababaaabbacdebaceada 例子中的信息编码为：例子中的信息编码为：10 00 01 10 111 110 111 00 10 00 10.码长共码长共91位，而使用位，而使用ASCII编码表示上述信息共需要编码表示上述信息共需要240位位a 16b 7c 6d 6e-5

18、a 16b 7-c 6-d 6e-5 a 00b 01c 10d 110e 111root0010111abcde0现在学习的是第29页，共65页Huffman编码依据信源字符出现的概率大小来构造代码，对出现概率较大的信源字符，给予较短码长，而对于出现概率较小的信源字符，给予较长的码长，最后使得编码的平均码字最短。现在学习的是第30页，共65页编码过程编码过程编码过程编码过程 出现频率高的数据编码长度短，反之亦然出现频率高的数据编码长度短，反之亦然出现频率高的数据编码长度短，反之亦然出现频率高的数据编码长度短，反之亦然 1 1 信号源的数据按照出现概率递减的顺序排列信号源的数据按照出现概率递减

19、的顺序排列信号源的数据按照出现概率递减的顺序排列信号源的数据按照出现概率递减的顺序排列 2 2 合并两个最小出现概率，作为新数据出现概率合并两个最小出现概率，作为新数据出现概率合并两个最小出现概率，作为新数据出现概率合并两个最小出现概率，作为新数据出现概率 3 3 重复进行重复进行重复进行重复进行1212，直至概率相加为，直至概率相加为，直至概率相加为，直至概率相加为1 1为止为止为止为止 4 4 合并运算时，概率大者取合并运算时，概率大者取合并运算时，概率大者取合并运算时，概率大者取0 0，概率小者取，概率小者取，概率小者取，概率小者取1 1 5 5 记录概率为记录概率为记录概率为记录概率为

20、1 1处到信号源的处到信号源的处到信号源的处到信号源的0 0、1 1序列序列序列序列编码特点编码特点编码特点编码特点 1 1 编码长度可变，压缩与解压缩较慢编码长度可变，压缩与解压缩较慢编码长度可变，压缩与解压缩较慢编码长度可变，压缩与解压缩较慢 2 2 硬件实现困难硬件实现困难硬件实现困难硬件实现困难 3 3 编码效率取决于信号源的数据出现概率编码效率取决于信号源的数据出现概率编码效率取决于信号源的数据出现概率编码效率取决于信号源的数据出现概率Huffman编码现在学习的是第31页，共65页例4-1：设输入图像的灰度级a1,a2,a3,a4,a5,a6出现的概率分别是0.4、0.2、0.12

21、、0.15、0.1、0.03。试进行哈夫曼编码，并计算编码效率、压缩比、冗余度。编码步骤：编码步骤：（1 1）初始化，根据符号概率的大小按由大）初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如图到小顺序对符号进行排序，如图4-24-2所示。所示。（2 2）把概率小的两个符号组成一个节点，如图）把概率小的两个符号组成一个节点，如图4-24-2中的中的a5a5、a6a6组成节点组成节点P1P1。（3 3）重复步骤）重复步骤2 2，得到节点，得到节点P2P2、P3P3、P4P4、P5P5，形成一棵形成一棵“树树”，其中，其中P5P5为根节点。为根节点。（4 4）从根节点）从根节点P5P5开

22、始到相应于每个符号的开始到相应于每个符号的“树树叶叶”，从上到下标上，从上到下标上1 1（上枝）或者（上枝）或者0 0（下枝），（下枝），至于哪个为至于哪个为1 1哪个为哪个为0 0则无关紧要，最后的结果仅则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同仅是分配的代码不同，而代码的平均长度是相同的。的。最终编码结果为：最终编码结果为：a1=1,a2=000,a1=1,a2=000,a3=011,a3=011,a4=001,a5=0100,a4=001,a5=0100,a6=0101a6=0101 现在学习的是第32页，共65页由公式可求得图像信源熵是：H(X)=-（0.4lo

23、g20.4+0.2log20.2+0.12log20.12+0.15log20.15+0.1log20.1+0.03log20.03）=2.25bit根据哈夫曼编码过程图给出的结果，由公式（4-7）可求出它的平均码字长度：Lc=0.41+0.23+0.153+0.123+0.14+0.034=2.33压缩之前8个符号需要3个比特量化，经过压缩之后的平均码字长度为2.33，由公式（4-10）得其压缩比为：现在学习的是第33页，共65页Huffman编码例题例题2：cabcedeacacdeddaaabaababaaabbacdebaceada 例子中的信息编码为：例子中的信息编码为：101 0

24、100 101 111 110 111 0 101 0 101.码长码长88位，比位，比Shannon-Fano编码略短一些编码略短一些a 16b 7c 6d 6e-5 a 0b 100c 101d 110e 111root00111abcde001现在学习的是第34页，共65页整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada该信息的熵经计算可知为86.601位符号符号理想位数理想位数（熵）（熵）S-F编码需编码需要位数要位数Huffman编编码需要位数码需要位数a1.32221b2.51523c2.73723d2.73733e3.00033总

25、计总计86.6019188现在学习的是第35页，共65页采用哈夫曼编码时有两个问题值得注意：采用哈夫曼编码时有两个问题值得注意：（1）哈夫曼编码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个的正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，更糟糕的是后面的译码可能全错，这种现象称为错误传播（Error Propagation）。（2）哈夫曼编码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。与仙农-范诺编码相比，这两种方法都自含同步码同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时

26、分割符号的特殊代码。现在学习的是第36页，共65页算术编码假设某个字符的出现概率为80%，该字符事实上只需要-log2(0.8)=0.322个二进制位进行编码难道真的能只输出0.322个0或0.322个1吗？算术编码的输出是：一个小数算术编码的输出是：一个小数算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64现在学习的是第37页，共65页算术编码算术编码（arithmetic coding AC）是利用0和1之间的间隔来表示信源编码的一

27、种方法，其编码值是间隔的上、下限包含的相同二进制。编码过程中的间隔决定了符号压缩后的输出。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。算术编码器的编码过程可用例4-2加以解释。现在学习的是第38页，共65页算术编码例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb第一步第一步：在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现概率相等，也就是都为1/3，我们将0-1区间按照概率的

28、比例分配给三个字符，即a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到1.0000。用图形表示就是：1.00000.66670.33330.0000Pc=1/3Pb=1/3Pa=1/3现在学习的是第39页，共65页算术编码第二步第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：0.66670.58340.41670.3333Pc=1/4Pb

29、=2/4Pa=1/4例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb现在学习的是第40页，共65页算术编码第三步第三步：接着我们拿到字符c，我们现在要关注上一步中得到的c的区间 0.5834-0.6667。新添了c以后，三个字符的概率分布变成Pa=1/5，Pb=2/5，Pc=2/5。我们用这个概率分布划分区间0.5834-0.6667：0.66670.63340.60010.5834Pc=2/5Pb=2/5Pa=1/5例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb现在学习的是第41页，共65页算术编码第四

30、步第四步：现在输入下一个字符c，三个字符的概率分布为：Pa=1/6，Pb=2/6，Pc=3/6。我们来划分c的区间0.6334-0.6667：0.66670.65010.63900.6334Pc=3/6Pb=2/6Pa=1/6例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb现在学习的是第42页，共65页算术编码第五步第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前

31、面没有太多意义的0和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程0.66670.65010.63900.6334Pc=3/6Pb=2/6Pa=1/6例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的原始信息为 bccb输出输出:(0.64)10=(0.1010001111)2现在学习的是第43页，共65页例2：假设信源符号为A,B,C,D，这些符号的概率分别为 0.1,0.4,0.2,0.3，根据这些概率可把间隔0,1分成4个子间隔：0,0.1,0.1,0.5,0.5,0.7,0.7,1，其中x,y表示半开放间隔，

32、即包含x不包含y，如表4-1所示。符号ABCD概率0.10.40.20.3初始编码间隔0,0.10.1,0.50.5,0.70.7,1表表4-1 信源符号、概率和初始编码间隔信源符号、概率和初始编码间隔如果消息序列的输入为：CADACDB，其编码过程如下：首先输入的符号是C，找到它的编码范围是0.5,0.7；由于消息中第2个符号A的编码范围是0,0.1，因此它的间隔就取0.5,0.7的第一个1/10作为新间隔0.5,0.52；编码第3个符号D时取新间隔为0.514,0.52；编码第4个符号A时，取新间隔为0.514,0.5146，。现在学习的是第44页，共65页消息的编码输出可以是最后一个间隔

33、中的任意数，整个编码过程如图4-3所示。最后在0.5143876,0.51442中选择一个数作为编码输出值：0.5143876。解码时，解码器由编码输出值：0.5143876，可马上解得一个字符为C，然后依次得到唯一解A,D,A,C,D,B。现在学习的是第45页，共65页在算术编码中需要注意的几个问题在算术编码中需要注意的几个问题：（1）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。（2）算术编码器对整个消息只产生一个码字，这个码字是在间隔0,1)中的一个实数，因此译码器在接受到表示这个实数

34、的所有位之前不能进行译码。（3）算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。现在学习的是第46页，共65页行程长度编码是一个针对包含有顺序排列的多次重复的数据的压缩方案。其原理就是把一系列的重复值用一个单独的值再加上一个计数值来取代，行程长度就是连续且重复的单元数目。如果想得到原始数据，只需展开这个编码就可以了。例如，计算机制作图像中，常常具有许多颜色相同的图块，而且在行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。这时，就不需要存储每一个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数目就可以，或者存储一个像素的颜色值，

35、以及具有相同颜色值的行数，这种压缩编码称为行程编码。具有相同颜色的连续的像素数目称为行程长度。现在学习的是第47页，共65页行程长度编码如图所示，假定一幅灰度图像，第n行的像素值为：用RLE编码方法得到的代码为：3150841160。代码斜黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值，它的颜色值是8。对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用10个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且编码技术实用。现在学

36、习的是第48页，共65页行程编码RLE的性能好坏主要取决于图像本身的特点。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少，如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE属于无损压缩技术。现在学习的是第49页，共65页词典编码属于无损压缩技术，其根据是数据本身包含有重复代码序列这个特性。词典编码的种类较多，归纳起来有两类：第一类词

37、典编码的基本思想是查找正在压缩的字符序列是否在前面输入的数据中出现过，如果是，则用指向早期出现过的字符串的“指针”替代重复的字符串。这种编码思想如图。词典编码词典编码现在学习的是第50页，共65页词典编码词典编码“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以AbrahamLempel和JakobZiv在1977年开发和发表的称为LZ77算法为基础的，1982年由Storer和Szymanski改进的称为LZSS算法。第二类算法的思想是从输入的数据中创建一个“短语词典”（dictionaryofthephrases。编码数据过程中，遇到已经在词典中出现的

38、“短语”时，编码器就输出这个词典中该短语的“索引号”，而不是短语本身。现在学习的是第51页，共65页词典编码词典编码J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。在他们研究的基础上，TerryA.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW（Lempel-ZivWalch）压缩编码。这种算法首先在高速硬盘控制器上得到了应用。在众多的压缩技术中，LZW算法时一种通用的、性能优良并得到广泛应用的压缩算法。LZW是一种完全可逆的算法，与其他算法比较，往往具有更高的压缩效率，因此被广泛应用于多种流行的压缩软件中。现在学习的是第52页，共

39、65页LZ77算法字典模型：现代汉语词典以及下面的例子现在学习的是第53页，共65页LZ77算法几个术语：几个术语：输入数据流(inputstream)：要被压缩的字符序列。字符(character)：输入数据流中的基本单元。编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。指针(pointer)：指向窗口中的匹配串且含长度的指针。现在学习的是第5

40、4页，共65页LZ77编码算法编码算法的具体执行步骤如下：（）把编码位置设置到输入数据流的开始位置。（）查找窗口中最长的匹配串。（）以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。（）如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。现在学习的是第55页，共65页编码举例位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AA AB BC CB BB BA AB BC

41、 C步骤位置匹配串 字符 输出 11-A(0,0)A22AB(1,1)B34-C(0,0)C45BB(2,1)B57A BC(5,2)C现在学习的是第56页，共65页LZ77编码算法“步骤”栏表示编码步骤。“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。“匹配串”栏表示窗口中找到的最长的匹配串。“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。“输出”栏以“(Back_chars,Chars_length)Explicit_character”格式输出。其中，(Back_chars,Chars_length)是指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_char

42、s个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。例如，表4-10中的输出“(5,2)C”告诉译码器回退5个字符，然后拷贝2个字符“AB”现在学习的是第57页，共65页LZSS编码LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了

43、区分它们就需要有额外的标志位，即ID位。现在学习的是第58页，共65页LZSS算法LZSS编码算法的具体执行步骤如下：把编码位置置于输入数据流的开始位置。在前向缓冲存储器中查找与窗口中最长的匹配串Pointer：=匹配串指针。Length：=匹配串长度。判断匹配串长度Length是否大于等于最小匹配串长度(LengthMIN_LENGTH)，如果“是”：输出指针，然后把编码位置向前移动Length个字符。如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。如果前向缓冲存储器不是空的，就返回到步骤2。现在学习的是第59页，共65页LZSS举例位置123456789101

44、1字符 AABBCBBAABC步骤位置 匹配串输出11-A22AA33-B44BB55-C66B B(3,2)78A A B(7,3)811CC现在学习的是第60页，共65页LZSS算法解释“步骤”栏表示编码步骤。“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。“匹配”栏表示窗口中找到的最长的匹配串。“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。“输出”栏的输出为：如果匹配串本身的长度LengthMIN_LENGTH，输出指向匹配串的指针，格式为(Back_chars,Chars_length)。该指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Cha

45、rs_length个字符到输出”。如果匹配串本身的长度LengthMIN_LENGTH，则输出真实的匹配串。现在学习的是第61页，共65页内存词典：内存词典：第二步：压缩串第二步：压缩串“AD.”在内存词典中仍无法找到匹配串，则输出二元组在内存词典中仍无法找到匹配串，则输出二元组(0，“A”)并将字串并将字串“A”置入内存词典置入内存词典第一步：压缩串第一步：压缩串“DAD.”在内存词典中无法找到匹配串，则输出二元组在内存词典中无法找到匹配串，则输出二元组(0，“D”)二元组中第一个元素表示词典的索引，第二个元素表示后续字符。二元组中第一个元素表示词典的索引，第二个元素表示后续字符。并将字串并

46、将字串“D”置入内存词典置入内存词典内存词典：内存词典：LZW算法LZW算法是LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.索引索引0词条词条null索引索引01词条词条null“D”现在学习的是第62页，共65页第三步：压缩串第三步：压缩串“D D.”在内存词典中可以找到最大匹配串在内存词典中可以找到最大匹配串“D”，输出，输出二元组二元组(1，“”)以此对字串以此对字串“D”进行了编码，然后将进行了编码，然后将“D”置入内存词典置入内存词典内存词典：内存词典：内存词典：内存词典：

47、第四步：压缩串第四步：压缩串“DAD.”在内存词典中可以找到最大匹配串在内存词典中可以找到最大匹配串“D”，则输，则输出出二元组二元组(1，“A”)以此对字串以此对字串“DA”进行了编码，然后将进行了编码，然后将“DA”置入内存词典置入内存词典LZW算法例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.索引索引012词条词条null“D”“A”索引索引0123词条词条null“D”“A”“D”现在学习的是第63页，共65页LZW算法例：待压缩的信息为例：待压缩的信息为 DAD DADA DADDY DADO.第九步后，内存词典的情况如下：第九步后，内存词典的情况如下：索引索引01234词条词条null“D”“A”“D”“DA”索引索引56789词条词条“DA”“DAD”“DY”“”“DADO”每一步的输出如下（每一步输出均为二元组）：每一步的输出如下（每一步输出均为二元组）：步骤步骤12345输出输出(0,”D”)(0,”A”)(1,”)(1,”A”)(4,”)步骤步骤6789输出输出(4,”D”)(1,”Y”)(0,”)(6,”O”)现在学习的是第64页，共65页谢谢，再见！现在学习的是第65页，共65页