多媒体技术基础3版2章数据无损压缩.ppt

《多媒体技术基础3版2章数据无损压缩.ppt》由会员分享，可在线阅读，更多相关《多媒体技术基础3版2章数据无损压缩.ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多媒体技术基础3版2章数据无损压缩 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2022年9月24日第2章 数据无损压缩2 of 72第第2章章 数据无损压缩目录数据无损压缩目录2.1 数据的冗余数据的冗余2.1.1 冗余概念2.1.2 决策量2.1.3 信息量2.1.4 熵2.1.5 数据冗余量2.2 统计编码2.2.1 香农-范诺编码2.2.2 霍夫曼编码2.2.3 算术编码2.3 RLE编码2.4 词典典编码2.4.1 词典编码的思想2.4.2 LZ77算

2、法2.4.3 LZSS算法2.4.4 LZ78算法2.4.5 LZW算法参考文献和站点参考文献和站点2022年9月24日第2章 数据无损压缩3 of 722.0 数据无损压缩概述数据无损压缩概述n数据可被数据可被压缩的依据的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限n三种多媒体数据三种多媒体数据类型型文字(text)数据无损压缩n根据数据本身的冗余(Based on data redundancy)声音(audio)数据有损压缩n根据数据本身的冗余(Based on data redundancy)n根据人的听觉系统特性(Based on human hearing syst

3、em)图像(image)/视像(video)数据有损压缩n根据数据本身的冗余(Based on data redundancy)n根据人的视觉系统特性(Based on human visual system)2022年9月24日第2章 数据无损压缩4 of 722.0 数据无损压缩概述数据无损压缩概述(续续1)n数据无数据无损压缩的理的理论信息信息论(information theory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储该术语源于Claude Shannon(香农)发表的“A Mathematical Theory of Communication”论文题目

4、，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。n数据无数据无损压缩的方法的方法霍夫曼编码(Huffman coding)算术编码(arithmetic coding)行程长度编码(run-length coding)词典编码(dictionary coding)2022年9月24日第2章 数据无损压缩5 of 722.0 数据无损压缩概述数据无损压缩概述(续续2)nThe Father of Information TheoryClaude Elwoo

5、d ShannonBorn:30 April 1916 in Gaylord,Michigan,USADied:24 Feb 2001 in Medford,Massachusetts,USAhttp:/www.bell- 数据无损压缩6 of 722.0 数据无损压缩概述数据无损压缩概述(续续3)nClaude Shannon The founding father of electronic communications age；American mathematical engineerIn 19361940,MIT:nMasters thesis,A symbolic analysis

6、 of relay and switching circuitsnDoctoral thesis:on theoretical geneticsIn 1948:nA mathematical theory of communication,landmark,climax(An important feature of Shannons theory:concept of entropy)2022年9月24日第2章 数据无损压缩7 of 722.1 数据的冗余数据的冗余n冗余概念冗余概念人为冗余n在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施n在数据存储和传输中，为了检测

7、和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余n由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余n不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达 2022年9月24日第2章 数据无损压缩8 of 722.1 数据的冗余数据的冗余(续续1)n决策量决策量(decision content)在

8、有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为 H0=log(n)其中，n是事件数决策量的单位由对数的底数决定nSh(Shannon):用于以2为底的对数nNat(natural unit):用于以e为底的对数nHart(hartley)：用于以10为底的对数2022年9月24日第2章 数据无损压缩9 of 722.1 数据的冗余数据的冗余(续续2)n信息量信息量(information content)具有确定概率事件的信息的定量度量在数学上定义为 其中，是事件出现的概率 举例：假设X=a,b,c是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25

9、分别是事件a,b和c出现的概率，这些事件的信息量分别为，I(a)=log2(1/0.50)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh一个等概率事件的集合，每个事件的信息量等于该集合的决策量2022年9月24日第2章 数据无损压缩10 of 722.1 数据的冗余数据的冗余(续续3)n熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content)用数学表示为2022年9月24日第2章 数据无损压缩11 of 72

10、2.1 数据的冗余数据的冗余(续续4)n数据的冗余量数据的冗余量2022年9月24日第2章 数据无损压缩12 of 722.2 统计编码统计编码n统计编码给已知统计信息的符号分配代码的数据无损压缩方法n编码方法方法香农-范诺编码霍夫曼编码算术编码n编码特性特性香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵2022年9月24日第2章 数据无损压缩13 of 722.2.1 统计编码统计编码香农香农-范诺编码范诺编码n香香农-范范诺

11、编码(ShannonFano coding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”。“位”是1948年Shannon首次使用的术语。例如最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon-Fano)编码法2022年9月24日第2章 数据无损压缩14 of 722.2.1 香农香农-范诺编码范诺编码n香香农-范范诺编码举例例 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素

12、中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1n(1)计算该图像可能获得的压缩比的理论值n(2)对5个符号进行编码n(3)计算该图像可能获得的压缩比的实际值表表2-1 符号在符号在图像中出像中出现的数目的数目符号ABCDE出现的次数157765出现的概率15/407/407/406/405/402022年9月24日第2章 数据无损压缩15 of 722.2.1 香农香农-范诺编码范诺编码(续续1)(1)压缩比的理比的理论值按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，100表示E，其余3个代码(101，110

13、，111)不用。这就意味每个像素用3位，编码这幅图像总共需要120位。按照香农理论，这幅图像的熵为这个数值表明，每个符号不需要用3位构成的代码表示，而用2.196位就可以，因此40个像素只需用87.84位就可以，因此在理论上，这幅图像的的压缩比为120:87.841.37:1，实际上就是3:2.1961.37 2022年9月24日第2章 数据无损压缩16 of 722.2.1 香农香农-范诺编码范诺编码(续续2)(2)符号编码符号编码对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同

14、的次数，如图2-1所示 2022年9月24日第2章 数据无损压缩17 of 722.2.1 香农香农-范诺编码范诺编码(续续3)（3）压缩比的实际值）压缩比的实际值按照这种方法进行编码需要的总位数为30+14+14+18+1591，实际的压缩比为120:911.32:1 图2-1 香农-范诺算法编码举例 2022年9月24日第2章 数据无损压缩18 of 722.2.2 统计编码统计编码霍夫曼编码霍夫曼编码n霍夫曼霍夫曼编码(Huffman coding)霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编

15、码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中2022年9月24日第2章 数据无损压缩19 of 722.2.2 霍夫曼编码 Case Study 1n霍夫曼霍夫曼编码举例例1现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比2022年9月24日第2章 数据无损压缩20 of 722.2.2 霍夫曼编码 Case Study 1(续续1)符号出现的次数 log2(1/pi）分

16、配的代码需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出符号出现的概率的概率2022年9月24日第2章 数据无损压缩21 of 722.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续2)(1)计算算该字符串的霍夫曼字符串的霍夫曼码步骤：按照符号出现概率大小的顺序对符号进行排序步骤：把概率最小的两个符号组成一个节点P1步骤：重复步骤，得到节点P2，P3，P4，PN，形成一棵树，其中的PN称为根节点步骤：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的标

17、成1，概率小的 标成0步骤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码2022年9月24日第2章 数据无损压缩22 of 722.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续3)符号符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代码代码B(11)A(10)E(00)D(011)C(010)2022年9月24日第2章 数据无损压缩23 of 722.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续4)符号出现的次数log2(1/pi）分配的代码需要的位数B101.5851120A81.907

18、1016C33.3220109D42.90701112E52.5850010合计301.06730个字符组成的字符串需要个字符组成的字符串需要67位位5个符号的代码2022年9月24日第2章 数据无损压缩24 of 722.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续5)(2)计算算该字符串的字符串的熵 其中，是事件 的集合，并满足H(S)=(8/30)log2(30/8)+(10/30)log2(30/10)+(3/30)log2(30/3)+(4/30)log2(30/4)+(5/30)log2(30/5)=30lg30 (8lg8 10lg10 3lg3 4 lg4 5

19、lg5)/(30log22)=(44.313624.5592)/9.0308 2.1874 (Sh)2022年9月24日第2章 数据无损压缩25 of 722.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续6)(3)计算算该字符串的平均字符串的平均码长平均码长：(28210333425)/30 2.233 位/符号 压缩比压缩比:90/67=1.34:1 平均码长：平均码长：67/30=2.233位位(4)计算编码前后的压缩比计算编码前后的压缩比n编码前：5个符号需3位，30个字符，需要90位n编码后：共67位2022年9月24日第2章 数据无损压缩26 of 722.2.2 霍

20、夫曼编码霍夫曼编码 Case Study 2n霍夫曼霍夫曼编码举例例2编码前nN=8 symbols:a,b,c,d,e,f,g,h,n3 bits per symbol(N=23=8)nP(a)=0.01,P(b)=0.02,P(c)=0.05,P(d)=0.09,P(e)=0.18,P(f)=0.2,P(g)=0.2,P(h)=0.25计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码效率2022年9月24日第2章 数据无损压缩27 of 722.2.2 霍夫曼编码霍夫曼编码 Case Study 2(续续1)2022年9月24日第2章 数据无损压缩28 of

21、 722.2.2 霍夫曼编码霍夫曼编码 Case Study 2(续续2)Average length per symbol(before coding):(2)Entropy:(3)Average length per symbol(with Huffman coding):(4)Efficiency of the code:2022年9月24日第2章 数据无损压缩29 of 722.2.3 统计编码统计编码算术编码算术编码n算算术编码(arithmetic coding)给已知统计信息的符号分配代码的数据无损压缩技术基本思想是用0和1之间的一个数值范围表示输入流中的一个字符，而不是给输入流

22、中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵 2022年9月24日第2章 数据无损压缩30 of 722.2.3 算术编码举例算术编码举例n例例2.3（取自教材）（取自教材）假设信源符号为00,01,10,11，它们的概率分别为 0.1,0.4,0.2,0.3 对二进制消息序列10 00 11 00 10 11 01 进行算术编码2022年9月24日第2章 数据无损压缩31 of 722.2.3 算术编码举例算术编码举例(续续1)符号00011011概率0.10.40.20.3初始编码间隔0,0.1)0.1,0.5)0.5,0.7)0.7,1

23、表表2-4 例例2.3的信源符号概率和初始的信源符号概率和初始编码间隔隔 n初始化初始化根据信源符号的概率把间隔0,1)分成如表2-4所示的4个子间隔：0,0.1),0.1,0.5),0.5,0.7),0.7,1)。其中x,y)的表示半开放间隔，即包含x不包含y，x称为低边界或左边界，y称为高边界或右边界2022年9月24日第2章 数据无损压缩32 of 722.2.3 算术编码举例算术编码举例(续续2)n确定符号的确定符号的编码范范围编码时输入第1个符号是10，找到它的编码范围是0.5,0.7消息中第2个符号00的编码范围是0,0.1)，它的间隔就取0.5,0.7)的第一个十分之一作为新间隔

24、0.5,0.52)编码第3个符号11时，取新间隔为0.514,0.52)编码第4个符号00时，取新间隔为0.514,0.5146)依此类推消息的编码输出可以是最后一个间隔中的任意数n整个整个编码过程如程如图2-3所示所示n编码和和译码的全的全过程分程分别见表表2-5和表和表2-6 2022年9月24日第2章 数据无损压缩33 of 722.2.3 算术编码举例算术编码举例(续续3)图2-3 例2.3的算术编码过程2022年9月24日第2章 数据无损压缩34 of 722.2.3 算术编码举例算术编码举例(续续4)2022年9月24日第2章 数据无损压缩35 of 722.2.3 算术编码举例算

25、术编码举例(续续5)2022年9月24日第2章 数据无损压缩36 of 722.3 RLE编码编码n行程长度编码(Run-Length Coding)一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数。在JPEG，MPEG，H.261和H.263等压缩方法中，RLE用来对图像数据变换和量化后的系数进行编码例:假设有一幅灰度图像第n行的像素值如图2-5所示。用RLE编码方法得到的代码为：80315084180图2-5 RLE编码概念2022年9月24日第2章 数据无损压缩37 of 722.3 RLE编码编码(

26、续续)nAssumption:Long sequences of identical symbols.Example,2022年9月24日第2章 数据无损压缩38 of 722.4 词典编码词典编码n词典典编码(dictionary coding)文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时,编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典两种类型的编码算法n具体算法具体算法LZ77算法LZSS算法LZ78算法LZW算法2022年9月24日第2章 数据无损压缩3

27、9 of 722.4 词典编码词典编码(续续1)n第一第一类编码算法算法用已经出现过的字符串替代重复的部分 编码器的输出仅仅是指向早期出现过的字符串的“指针”图2-6 第一类词典编码概念2022年9月24日第2章 数据无损压缩40 of 722.4 词典编码词典编码(续续2)n第二第二类编码算法算法从输入的数据中创建一个“短语词典(dictionary of the phrases)”编码器输出词典中的短语“索引号”，而不是短语图2-7 第二类词典编码概念41LZ77算法算法n第一类词典编码里：所指的第一类词典编码里：所指的“词典词典”是指用以是指用以前处理过的数据来表示编码过程中遇到的重复前

28、处理过的数据来表示编码过程中遇到的重复部分。部分。n这类编码中的所有算法都是以这类编码中的所有算法都是以Abraham Lempel和和Jakob Ziv在在1977年开发和发表的称年开发和发表的称为为LZ77算法为基础的算法为基础的nJacob Ziv,Abraham Lempel,A Universal Algorithm for Sequential Data Compression,IEEE Transactions on Information Theory,23(3):337-343,May 1977.42LZ77算法算法nLZ77 算法在某种意义上又可以称为算法在某种意义上又可以

29、称为“滑滑动窗口压缩动窗口压缩”，该算法将一个虚拟的，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。则输出其出现位置和长度。43LZ77n首先介绍算法中用到的几个术语：首先介绍算法中用到的几个术语：n输入数据流输入数据流(input stream)：要被压缩的字符序列。：要被压缩的字符序列。n字符字符(character)：输入数据流中的基本单元。：输入数据流中的基本单元。n编码位置编码位置(coding position)：输入数据流中当前要编码：输入数据

30、流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。的字符位置，指前向缓冲存储器中的开始字符。n前向缓冲存储器前向缓冲存储器(Lookahead buffer)：存放从编码位置：存放从编码位置到输入数据流结束的字符序列的存储器。到输入数据流结束的字符序列的存储器。n窗口窗口(window)：指包含：指包含W个字符的窗口，字符从编码个字符的窗口，字符从编码位置开始向后数，也就是最后处理的字符数。位置开始向后数，也就是最后处理的字符数。n指针指针(pointer)：指向窗口中的匹配串，一般含有长度。：指向窗口中的匹配串，一般含有长度。AABCBBABCAW=5已编码未编码B=444图例图例输入

31、数据流45LZ77算法核心算法核心nLZ77编码算法的核心：查找从前向缓冲存储编码算法的核心：查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执器开始的最长的匹配串。编码算法的具体执行步骤如下：行步骤如下：1.把编码位置设置到输入数据流的开始位置。2.查找窗口中最长的匹配串。3.以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。4.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。46指

32、针表示指针表示n(Pointer,Length)Characters 表示匹配的表示匹配的（字符位置，长度）下一个不匹配的字（字符位置，长度）下一个不匹配的字符符n指针可以以指针可以以“(Back_chars,Chars_length)Explicit_character”格式输格式输出。出。n其中，其中，(Back_chars,Chars_length)是指是指向匹配串的指针，告诉译码器向匹配串的指针，告诉译码器“在这个在这个窗口中向后退窗口中向后退Back_chars个字符然后拷个字符然后拷贝贝Chars_length个字符到输出个字符到输出”，Explicit_character是真实字

33、符。是真实字符。47例子例子位置位置123456789字符字符 AABCBBABCCBABBCBAA编码步骤编码步骤编码位置编码位置匹配串匹配串 前向缓冲中前向缓冲中第一个字符第一个字符 输出输出(ptr,len)ch11-A(0,0)A22AB(1,1)B34-C(0,0)C45BB(2,1)B57A BC(5,2)CW=5,B=2每次移动窗口和编码位置Len+1Len=0Len=1 Len=0Len=148LZ77的问题的问题nLZ77通过输出真实字符解决了在窗口中通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表

34、现在两案包含有冗余信息。冗余信息表现在两个方面，个方面，一是空指针 例如前一个例子中(0,0)C二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。49LZSS算法算法n1982年由年由Storer和和Szymanski改进改进LZ77nLZSS算法以比较有效的方法解决这个问算法以比较有效的方法解决这个问题，题，n它的思想是如果匹配串的长度比指针本它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需有指针和字符本身，为了区

35、分它们就需要有额外的标志位，即要有额外的标志位，即ID位。位。50LZSS编码算法步骤编码算法步骤1.把编码位置置于输入数据流的开始位置。把编码位置置于输入数据流的开始位置。2.在前向缓冲存储器中查找与窗口中最长的匹在前向缓冲存储器中查找与窗口中最长的匹配串配串 Pointer：=匹配串指针。匹配串指针。Length：=匹配串长度。匹配串长度。3.判断匹配串长度判断匹配串长度Length是否大于等于最小匹是否大于等于最小匹配串长度配串长度(LengthMIN_LENGTH)，如果如果“是是”：输出指针，然后把编码位置向：输出指针，然后把编码位置向前移动前移动Length个字符。个字符。如果如果

36、“否否”：输出前向缓冲存储器中的第：输出前向缓冲存储器中的第1个个字符，然后把编码位置向前移动一个字符。字符，然后把编码位置向前移动一个字符。4.如果前向缓冲存储器不是空的，就返回到步如果前向缓冲存储器不是空的，就返回到步骤骤251例子例子位置1234567891011字符 AABBCBBAABC步骤位置 匹配串输出11-A22AA33-B44BB55-C66B B(3,2)78A A B(7,3)811CC编码过程(MIN_LENGTH=2，W=10,B=3)Len=1252LZSS与与LZ77比较比较n在相同的在相同的计算机算机环境下，境下，LZSS算法比算法比LZ77可可获得比得比较高的

37、高的压缩比，而比，而译码同同样简单。这也也就是就是为什么什么这种算法成种算法成为开开发新算法的基新算法的基础，许多后来开多后来开发的文档的文档压缩程序都使用了程序都使用了LZSS的思想。例如，的思想。例如，PKZip,GZip,ARJ,LHArc和和ZOO等等，其差等等，其差别仅仅是指是指针的的长短和窗口的短和窗口的大小等有所不同。大小等有所不同。nLZSS同同样可以和可以和熵编码联合使用，例如合使用，例如ARJ就就与霍夫曼与霍夫曼编码联用，而用，而PKZip则与与Shannon-Fano联用，它的后用，它的后续版本也采用霍夫曼版本也采用霍夫曼编码。53LZ78原理原理nLZ78的编码思想是不

38、断地从字符流中提的编码思想是不断地从字符流中提取新的字符串取新的字符串(String)，通俗地理解为新，通俗地理解为新“词条词条”，然后用，然后用“代号代号”也就是码字也就是码字(Code word)表示这个表示这个“词条词条”。这样一。这样一来，对字符流的编码就变成了用码字来，对字符流的编码就变成了用码字(Code word)去替换字符流去替换字符流(Char stream)，生成码字流，生成码字流(Code stream)，从而达到，从而达到压缩数据的目的。压缩数据的目的。54LZ77与与LZ78比较比较nLZ77利用滑动窗口里的内容作为字典，利用滑动窗口里的内容作为字典，找最长子串找最长

39、子串nLZ78动态构建字典动态构建字典55LZ78编码编码n在在编编码码开开始始时时词词典典是是空空的的，不不包包含含任任何何字字符符串串(string)。在在这这种种情情况况下下编编码码器器就就输输出出一一个个表表示示空空字字符符串串的的特特殊殊码码字字(例例如如“0”)和和字字符符流流中中(Charstream)的的第第一一个个字字符符C，并并把把这这个个字字符符C添添加加到到词词典典中中作作为为一一个个由由一一个个字字符符组组成成的的字字符符串串(string)。在在编编码码过过程程中中，如如果果出出现现类似没有任何匹配的情况，也照此办理。类似没有任何匹配的情况，也照此办理。n在在词词典

40、典中中已已经经包包含含某某些些字字符符串串(String)之之后后，如如果果“当当前前前前缀缀P+当当前前字字符符C”已已经经在在词词典典中中，就就用用字字符符C来来扩扩展展这这个个前前缀缀，这这样样的的扩扩展展操操作作一一直直重重复复到到获获得得一一个个在在词典中没有的字符串词典中没有的字符串(String)为止。为止。n此此时时就就输输出出表表示示当当前前前前缀缀P的的码码字字(Code word)和和字字符符C，并并把把P+C添添加加到到词词典典中中，然然后后开开始始处处理理字字符符流流(Charstream)中的下一个字符。中的下一个字符。56算法算法n 在开始时，词典和当前前缀在开始

41、时，词典和当前前缀P都是空的。都是空的。n 当前字符当前字符C：=字符流中的下一个字符。字符流中的下一个字符。n 判断判断P+C是否在词典中：是否在词典中：(1)如果如果“是是”：用：用C扩展扩展P，让，让P：=P+C；(2)如果如果“否否”：输出与当前前缀P相对应的码字和当前字符C；把字符串P+C 添加到词典中。令P：=空值。(3)判断字符流中是否判断字符流中是否还有字符需要有字符需要编码 如果“是”：返回到步骤2。如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。57LZ78编码输出编码输出nLZ78编码器的输出是码字编码器的输出是码字-字符字符(W,C)对，对，

42、每次输出一对到码字流中，与码字每次输出一对到码字流中，与码字W相对相对应的字符串应的字符串(String)用字符用字符C进行扩展生成进行扩展生成新的字符串新的字符串(String)，然后添加到词典中。，然后添加到词典中。58例子例子位置位置123456789字符字符 ABBCBCABA步骤步骤位置位置 当前字符当前字符C当前前缀当前前缀P添加词典添加词典输出输出 11A，A(0,A)22B，B(0,B)33BC，BBC,B C(2,C)45BCA，BBCBCA，B C A(3,A)58BA，BBA，B A(2,A)59LZ78与与LZ77nLZ78在每个编码步骤中减少了在每个编码步骤中减少了s

43、tring比较比较数目数目LZ77需要找最长匹配子串n压缩率与压缩率与LZ77类似。类似。60LZWnTerry A.Weltch在在 1984年年 发发 表表 了了 改改 进进LZ78的的文文章章，因因此此把把这这种种编编码码方方法法称称为为LZW(Lempel-Ziv Walch)61LZW与与LZ78编码原理差别编码原理差别LZW只只输输出出代代表表词词典典中中的的字字符符串串(String)的的码码字字(code word)。这这就就意意味味在在开开始始时时词词典典不不能能是是空空的的，它它必必须须包包含含可可能能在在字字符符流流出出现现中中的的所所有有单个字符，即前缀根单个字符，即前

44、缀根(Root)。由由于于所所有有可可能能出出现现的的单单个个字字符符都都事事先先包包含含在在词词典典中中，每每个个编编码码步步骤骤开开始始时时都都使使用用一一字字符符前前缀缀(one-character prefix)，因因此此至至少少可可以以在在词词典典中找到长度为中找到长度为1的匹配串。的匹配串。62LZW的词典的词典nLZW编码是围绕称为词典的转换表来完编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分的字符序列，并且为每个表项分配一个码字配一个码字(Code word)，或者叫做序号。，或者叫做序

45、号。nWelch的论文中用了的论文中用了12位码字，位码字，12位可以位可以有有4096个不同的个不同的12位代码，这就是说，位代码，这就是说，转换表有转换表有4096个表项，其中个表项，其中256个表项用个表项用来存放已定义的字符，剩下来存放已定义的字符，剩下3840个表项个表项用来存放前缀用来存放前缀(Prefix)。63例子例子码字(Code word)前缀(Prefix)1193A194B2551305abcdefxyF0123464LZW编码编码nLZW编码器就是通过管理这个词典完成编码器就是通过管理这个词典完成输入与输出之间的转换。输入与输出之间的转换。nLZW编码器的输入是字符流

46、编码器的输入是字符流(Char stream)，字符流可以是用，字符流可以是用8位位ASCII字符字符组成的字符串，而输出是用组成的字符串，而输出是用n位位(例如例如12位位)表示的码字流表示的码字流(Code stream)，码字代，码字代表单个字符或多个字符组成的字符串表单个字符或多个字符组成的字符串(String)。LZ78输出是码字输出是码字+字符字符CBABBCBAA19365贪婪分析算法贪婪分析算法nLZW采用采用greedy parsing algorithm 每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中

47、出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串。判断新的串是否在词典中n是：继续输入Cn否：加入词典，分配码字66具体执行步骤1.开始时词典包含所有可能的根开始时词典包含所有可能的根(Root)，当前，当前前缀前缀P是空的；是空的；2.当前字符当前字符(C)：=字符流中的下一个字符；字符流中的下一个字符；3.判断缀判断缀-符串符串P+C是否在词典中是否在词典中(1)如果如果“是是”：P：=P+C/(用用C扩展扩展P)；(2)如果如果“否否”把代表当前前缀P的码字输出到

48、码字流;把缀-符串P+C添加到词典;令P：=C/(现在的P仅包含一个字符C);67n 4.判断字符流中是否还有字符需要编码判断字符流中是否还有字符需要编码(1)如果“是”，就返回到步骤2；(2)如果“否”n 把代表当前前缀P的码字输出到码字流;n 结束。注注意意：每每个个输输出出的的码码字字对对应应于于词词典典中中的的一一个个词词条条，因因为为只只有有当当出出现现新新的的字字符符串串的的时候才输出码字。时候才输出码字。68位置123456789字符 ABBABABAC步骤步骤位置位置 词典词典当前字符当前字符C当前前缀当前前缀P输出输出(1)A (2)B (3)C 11(4)A B A B A

49、 AB,B(1)22(5)B B B BB,B(2)33(6)B A A BA,A(2)44(7)A B A B A AB ABA,A(4)56(8)A B A C B A C AB ABA ABAC,C(7)6-(3)69LZW的特点的特点n1)对于一段短语，它只输出一个数字，即字典中的序号。（这个对于一段短语，它只输出一个数字，即字典中的序号。（这个数字的位数决定了字典的最大容量，当它的位数取得太大时，比数字的位数决定了字典的最大容量，当它的位数取得太大时，比如如 24 位以上，对于短匹配占多数的情况，压缩率可能很低。取得位以上，对于短匹配占多数的情况，压缩率可能很低。取得太小时，比如太小

50、时，比如 8 位，字典的容量受到限制。所以同样需要取舍。）位，字典的容量受到限制。所以同样需要取舍。）2)对于一个短语，比如对于一个短语，比如 abcd，当它在待压缩文件中第一次出现，当它在待压缩文件中第一次出现时，时，ab 被加入字典，第二次出现时，被加入字典，第二次出现时，abc 被加入字典，第三次出被加入字典，第三次出现时，现时，abcd 才会被加入字典，对于一些长匹配，它必须高频率地才会被加入字典，对于一些长匹配，它必须高频率地出现，并且字典有较大的容量，才会被最终完整地加入字典。相出现，并且字典有较大的容量，才会被最终完整地加入字典。相应地，应地，lz77 只要匹配在只要匹配在“字典