多媒体技术基础第3版第2部分数据无损压缩教学.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 数据无损压缩,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,多媒体技术基础,(,第,3,版,),第,2,章数据无损压缩,张奇,复旦大学 计算机科学技术学院,2015,年,4,月,2026年10月22日,第,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.4.3 LZSS,算法,2.4.4 LZ78,算法,2.4.5 LZW,算法,参考文献和站点,2026年10月22日,第,2,章 数据无损压缩,3,of 72,2.0,数据无损压缩概述,数据可被压缩的依据,数据本身存在冗余,听觉系统的敏感度有限,视觉系统的敏感度有限,三种多媒体数据类型,文字,(text),数据,无损压缩,根据数据本身的冗余,(Based on data redundancy),声音,(audio),数据,有损压缩,根据数据本身的冗余,(Based on data redundancy),根据人的听觉系统特性,(Based on human hearing system),图像,(image)/,视像,(video),数据,有损压缩,根据数据本身的冗余,(Based on data redundancy),根据人的视觉系统特性,(Based on human visual system),2026年10月22日,第,2,章 数据无损压缩,4,of 72,2.0,数据无损压缩概述,(,续,1),数据无损压缩的理论,信息论,(information theory),1948,年创建的数学理论的一个分支学科，研究信息的编码、传输和存储,该术语源于,Claude Shannon(,香农,),发表的“,A Mathematical Theory of Communication”,论文题目，提议用二进制数据对信息进行编码,最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。,数据无损压缩的方法,霍夫曼编码,(,Huffman coding),算术编码,(arithmetic coding),行程长度编码,(r,un-length coding),词典编码,(dictionary coding),2026年10月22日,第,2,章 数据无损压缩,5,of 72,2.0,数据无损压缩概述,(,续,2),The Father of Information TheoryClaude Elwood Shannon,Born:30 April 1916 in Gaylord,Michigan,USA,Died:24 Feb 2001 in Medford,Massachusetts,USA,www.bell-数据无损压缩,8,of 72,2.1,数据的冗余,(,续,1),决策量,(decision content),在有限数目的互斥事件集合中，决策量是事件数的对数值,在数学上表示为,H,0,=log(,n,),其中，,n,是事件数,决策量的单位由对数的底数决定,Sh(Shannon):,用于以,2,为底的对数,Nat(natural unit):,用于以,e,为底的对数,Hart(hartley),：用于以,10,为底的对数,2026年10月22日,第,2,章 数据无损压缩,9,of 72,2.1,数据的冗余,(,续,2),信息量,(information content),具有确定概率事件的信息的定量度量,在数学上定义为,其中，是事件出现的概率,举例：假设,X=a,b,c,是由,3,个事件构成的集合，,p(a)=0.5,，,p(b)=0.25,，,p(b)=0.25,分别是事件,a,b,和,c,出现的概率，这些事件的信息量分别为，,I(a)=log,2,(1/0.50)=1 sh,I(b)=log,2,(1/0.25)=2 sh,I(c)=log,2,(1/0.25)=2 sh,一个等概率事件的集合，每个事件的信息量等于该集合的决策量,2026年10月22日,第,2,章 数据无损压缩,10,of 72,2.1,数据的冗余,(,续,3),熵,(entropy),按照香农,(Shannon),的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量,(,mean information content,),用数学表示为,2026年10月22日,第,2,章 数据无损压缩,11,of 72,2.1,数据的冗余,(,续,4),数据的冗余量,2026年10月22日,第,2,章 数据无损压缩,12,of 72,2.2,统计编码,统计编码,给已知统计信息的符号分配代码的数据无损压缩方法,编码方法,香农,-,范诺编码,霍夫曼编码,算术编码,编码特性,香农,-,范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少,算术编码使用,0,和,1,之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵,2026年10月22日,第,2,章 数据无损压缩,13,of 72,2.2.1,统计编码,香农,-,范诺编码,香农,-,范诺编码,(ShannonFano coding),在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量,在计算熵时，如果对数的底数用,2,，熵的单位就用“香农,(Sh)”,，也称“位,(bit)”,。“位”是,1948,年,Shannon,首次使用的术语。例如,最早阐述和实现“从上到下”的熵编码方法的人是,Shannon(1948,年,),和,Fano(1949,年,),，因此称为香农,-,范诺,(Shannon-Fano),编码法,2026年10月22日,第,2,章 数据无损压缩,14,of 72,2.2.1,香农,-,范诺编码,香农,-,范诺编码举例,有一幅,40,个像素组成的灰度图像，灰度共有,5,级，分别用符号,A,，,B,，,C,，,D,和,E,表示。,40,个像素中出现灰度,A,的像素数有,15,个，出现灰度,B,的像素数有,7,个，出现灰度,C,的像素数有,7,个，其余情况见表,2-1,(1),计算该图像可能获得的压缩比的理论值,(2),对,5,个符号进行编码,(3),计算该图像可能获得的压缩比的实际值,表,2-1,符号在图像中出现的数目,符号,A,B,C,D,E,出现的次数,15,7,7,6,5,出现的概率,15/40,7/40,7/40,6/40,5/40,2026年10月22日,第,2,章 数据无损压缩,15,of 72,2.2.1,香农,-,范诺编码,(,续,1),(1),压缩比的理论值,按照常规的编码方法，表示,5,个符号最少需要,3,位，如用,000,表示,A,，,001,表示,B,，,，,100,表示,E,，其余,3,个代码,(101,，,110,，,111),不用。这就意味每个像素用,3,位，编码这幅图像总共需要,120,位。按照香农理论，这幅图像的熵为,这个数值表明，每个符号不需要用,3,位构成的代码表示，而用,2.196,位就可以，因此,40,个像素只需用,87.84,位就可以，因此在理论上，这幅图像的的压缩比为,120:87.841.37:1,，实际上就是,3:2.1961.37,2026年10月22日,第,2,章 数据无损压缩,16,of 72,2.2.1,香农,-,范诺编码,(,续,2),(2),符号编码,对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如,A,，,B,，,C,，,D,和,E,，见表,2-2,。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图,2-1,所示,2026年10月22日,第,2,章 数据无损压缩,17,of 72,2.2.1,香农,-,范诺编码,(,续,3),（,3,）压缩比的实际值,按照这种方法进行编码需要的总位数为,30+14+14+18+15,91,，实际的压缩比为,120:911.32:1,图,2-1,香农,-,范诺算法编码举例,2026年10月22日,第,2,章 数据无损压缩,18,of 72,2.2.2,统计编码,霍夫曼编码,霍夫曼编码,(Huffman coding),霍夫曼,(D.A.Huffman),在,1952,年提出和描述的“从下到上”的熵编码方法,根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素,(,如字母,),出现的次数越多，其编码的位数就越少,广泛用在,JPEG,MPEG,H.26X,等各种信息编码标准中,2026年10月22日,第,2,章 数据无损压缩,19,of 72,2.2.2,霍夫曼编码,Case Study 1,霍夫曼编码举例,1,现有一个由,5,个不同符号组成的,30,个符号的字符串：,BABACACADADABBCBABEBEDDABEEEBB,计算,(1),该字符串的霍夫曼码,(2),该字符串的熵,(3),该字符串的平均码长,(4),编码前后的压缩比,2026年10月22日,第,2,章 数据无损压缩,20,of 72,2.2.2,霍夫曼编码,Case Study 1,(,续,1),符号,出现的次数,log,2,(1/,p,i,）,分配的代码,需要的位数,B,10,1.585,?,A,8,1.907,?,C,3,3.322,?,D,4,2.907,?,E,5,2.585,?,合计,30,符号出现的概率,2026年10月22日,第,2,章 数据无损压缩,21,of 72,2.2.2,霍夫曼编码,Case Study 1(,续,2),(1),计算该字符串的霍夫曼码,步骤：按照符号出现概率大小的顺序对符号进行排序,步骤：把概率最小的两个符号组成一个节点,P1,步骤：重复步骤，得到节点,P2,，,P3,，,P4,，,，,PN,，形成一棵树，其中的,PN,称为根节点,步骤：从根节点,PN,开始到每个符号的树叶，从上到下 标上,0(,上枝,),和,1(,下枝,),，至于哪个为,1,哪个为,0,则 无关紧要，但通常把概率大的标成,1,，概率小的 标成,0,步骤：从根节点,PN,开始顺着树枝到每个叶子分别写出 每个符号的代码,2026年10月22日,第,2,章 数据无损压缩,22,of 72,2.2.2,霍夫曼编码,Case Study 1(,续,3),符号,B(10),A(8),E(5),D(4),C(3),P1(7),P2(12),P3(18),P4(30),0,1,1,0,1,0,1,0,代码,B(11),A(10),E(00),D(011),C(010),2026年10月22日,第,2,章 数据无损压缩,23,of 72,2.2.2,霍夫曼编码,Case Study 1(,续,4),符号,出现的次数,log,2,(1/,p,i,）,分配的代码,需要的位数,B,10,1.585,11,20,A,8,1.907,10,16,C,3,3.322,010,9,D,4,2.907,011,12,E,5,2.585,00,10,合计,30,1.0,67,30,个字符组成的字符串需要,67,位,5,个符号的代码,2026年10月22日,第,2,章 数据无损压缩,24,of 72,2.2.2,霍夫曼编码,Case Study 1(,续,5),(2),计算该字符串的熵,其中，是事件 的集合，,并满足,H(S),=(8/30)log,2,(30/8)+(10/30)log,2,(30/10)+(3/30)log,2,(30/3)+(4/30)log,2,(30/4)+(5/30)log,2,(30/5)=30lg30 (8,lg8,10,lg10,3,lg3,4,lg4,5 lg5)/(30,log,2,2)=(44.3136,24.5592)/9.0308,2.1874 (Sh),2026年10月22日,第,2,章 数据无损压缩,25,of 72,2.2.2,霍夫曼编码,Case Study 1(,续,6),(3),计算该字符串的平均码长,平均码长：,(2,8,2,10,3,3,3,4,2,5)/30,2.233,位,/,符号,压缩比,:90/67=1.34:1,平均码长：,67/30=2.233,位,(4),计算编码前后的压缩比,编码前：,5,个符号需,3,位，,30,个字符，需要,90,位,编码后：共,67,位,2026年10月22日,第,2,章 数据无损压缩,26,of 72,2.2.2,霍夫曼编码,Case Study 2,霍夫曼编码举例,2,编码前,N,=8 symbols:a,b,c,d,e,f,g,h,3 bits per symbol(,N,=2,3,=8),P(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),编码效率,2026年10月22日,第,2,章 数据无损压缩,27,of 72,2.2.2,霍夫曼编码,Case Study 2(,续,1),2026年10月22日,第,2,章 数据无损压缩,28,of 72,2.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:,2026年10月22日,第,2,章 数据无损压缩,29,of 72,2.2.3,统计编码,算术编码,算术编码,(arithmetic coding),给已知统计信息的符号分配代码的数据无损压缩技术,基本思想是用,0,和,1,之间的一个数值范围表示输入流中的一个字符，而不是给输入流中的每个字符分别指定一个码字,实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵,2026年10月22日,第,2,章 数据无损压缩,30,of 72,2.2.3,算术编码举例,例,2.3,（取自教材）,假设信源符号为,00,01,10,11,，它们的概率分别为,0.1,0.4,0.2,0.3,对二进制消息序列,10 00 11 00 10 11 01,进行算术编码,2026年10月22日,第,2,章 数据无损压缩,31,of 72,2.2.3,算术编码举例,(,续,1),符号,00,01,10,11,概率,0.1,0.4,0.2,0.3,初始编码间隔,0,0.1),0.1,0.5),0.5,0.7),0.7,1,表,2-4,例,2.3,的信源符号概率和初始编码间隔,初始化,根据信源符号的概率把间隔,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,称为高边界或右边界,2026年10月22日,第,2,章 数据无损压缩,32,of 72,2.2.3,算术编码举例,(,续,2),确定符号的编码范围,编码时输入第,1,个符号是,10,，找到它的编码范围是,0.5,0.7,消息中第,2,个符号,00,的编码范围是,0,0.1),，它的间隔就取,0.5,0.7),的第一个十分之一作为新间隔,0.5,0.52),编码第,3,个符号,11,时，取新间隔为,0.514,0.52),编码第,4,个符号,00,时，取新间隔为,0.514,0.5146),依此类推,消息的编码输出可以是最后一个间隔中的任意数,整个编码过程如图,2-3,所示,编码和译码的全过程分别见表,2-5,和表,2-6,2026年10月22日,第,2,章 数据无损压缩,33,of 72,2.2.3,算术编码举例,(,续,3),图,2-3,例,2.3,的算术编码过程,2026年10月22日,第,2,章 数据无损压缩,34,of 72,2.2.3,算术编码举例,(,续,4),2026年10月22日,第,2,章 数据无损压缩,35,of 72,2.2.3,算术编码举例,(,续,5),2026年10月22日,第,2,章 数据无损压缩,36,of 72,2.3 RLE,编码,行程长度编码,(,Run-Length Coding,),一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数。在,JPEG，MPEG，H.261,和,H.263,等压缩方法中，,RLE,用来对图像数据变换和量化后的系数进行编码,例,:,假设有一幅灰度图像第,n,行的像素值如图,2-5,所示。用,RLE,编码方法得到的代码为：,8,0,3,1,50,8,4,1,8,0,图,2-5 RLE,编码概念,2026年10月22日,第,2,章 数据无损压缩,37,of 72,2.3 RLE,编码,(,续,),Assumption:,Long sequences of identical symbols.,Example,2026年10月22日,第,2,章 数据无损压缩,38,of 72,2.4,词典编码,词典编码,(dictionary coding),文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时,编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典,两种类型的编码算法,具体算法,LZ77,算法,LZSS,算法,LZ78,算法,LZW,算法,2026年10月22日,第,2,章 数据无损压缩,39,of 72,2.4,词典编码,(,续,1),第一类编码算法,用已经出现过的字符串替代重复的部分,编码器的输出仅仅是指向早期出现过的字符串的“指针”,图,2-6,第一类词典编码概念,2026年10月22日,第,2,章 数据无损压缩,40,of 72,2.4,词典编码,(,续,2),第二类编码算法,从输入的数据中创建一个“短语词典,(dictionary of the phrases)”,编码器输出词典中的短语“索引号”，而不是短语,图,2-7,第二类词典编码概念,41,LZ77,算法,第一类词典编码里：所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。,这类编码中的所有算法都是以,Abraham Lempel,和,Jakob Ziv,在,1977,年开发和发表的称为,LZ77,算法为基础的,Jacob Ziv,Abraham Lempel,A Universal Algorithm for Sequential Data Compression,IEEE Transactions on Information Theory,23(3):337-343,May 1977.,42,LZ77,算法,LZ77,算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。,43,LZ77,首先介绍算法中用到的几个术语：,输入数据流,(input stream),：要被压缩的字符序列。,字符,(character),：输入数据流中的基本单元。,编码位置,(coding position),：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。,前向缓冲存储器,(Lookahead buffer),：存放从编码位置到输入数据流结束的字符序列的存储器。,窗口,(window),：指包含,W,个字符的窗口，字符从编码位置开始向后数，也就是最后处理的字符数。,指针,(pointer),：指向窗口中的匹配串，一般含有长度。,A,A,B,C,B,B,A,B,C,A,W=5,已编码,未编码,B=4,44,图例,输入数据流,45,LZ77,算法核心,LZ77,编码算法的核心：查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：,把编码位置设置到输入数据流的开始位置。,查找窗口中最长的匹配串。,以“,(Pointer,Length)Characters”,的格式输出，其中,Pointer,是指向窗口中匹配串的指针，,Length,表示匹配字符的长度，,Characters,是前向缓冲存储器中的不匹配的第,1,个字符。,如果前向缓冲存储器不是空的，则把编码位置和窗口向前移,(Length+1),个字符，然后返回到步骤,2,。,46,指针表示,(Pointer,Length)Characters,表示匹配的（字符位置，长度）下一个不匹配的字符,指针可以以“,(Back_chars,Chars_length)Explicit_character”,格式输出。,其中，,(Back_chars,Chars_length),是指向匹配串的指针，告诉译码器“在这个窗口中向后退,Back_chars,个字符然后拷贝,Chars_length,个字符到输出”，,Explicit_character,是真实字符。,47,例子,位置,1,2,3,4,5,6,7,8,9,字符,A,A,B,C,B,B,A,B,C,C,B,A,B,B,C,B,A,A,编码步骤,编码位置,匹配串,前向缓冲中第一个字符,输出,(ptr,len)ch,1,1,-,A,(0,0)A,2,2,A,B,(1,1)B,3,4,-,C,(0,0)C,4,5,B,B,(2,1)B,5,7,A B,C,(5,2)C,W=5,B=2,每次移动窗口和编码位置,Len+1,Len=0,Len=1,Len=0,Len=1,48,LZ77,的问题,LZ77,通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，,一是空指针 例如前一个例子中,(0,0)C,二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。,49,LZSS,算法,1982,年由,Storer,和,Szymanski,改进,LZ77,LZSS,算法以比较有效的方法解决这个问题，,它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即,ID,位。,50,LZSS,编码算法步骤,把编码位置置于输入数据流的开始位置。,在前向缓冲存储器中查找与窗口中最长的匹配串,Pointer,：,=,匹配串指针。,Length,：,=,匹配串长度。,判断匹配串长度,Length,是否大于等于最小匹配串长度,(LengthMIN_LENGTH),，如果“是”：输出指针，然后把编码位置向前移动,Length,个字符。如果“否”：输出前向缓冲存储器中的第,1,个字符，然后把编码位置向前移动一个字符。,如果前向缓冲存储器不是空的，就返回到步骤,2,51,例子,位置,1,2,3,4,5,6,7,8,9,10,11,字符,A,A,B,B,C,B,B,A,A,B,C,步骤,位置,匹配串,输出,1,1,-,A,2,2,A,A,3,3,-,B,4,4,B,B,5,5,-,C,6,6,B B,(3,2),7,8,A A B,(7,3),8,11,C,C,编码过程,(MIN_LENGTH=2,，,W=10,B=3),Len=12,52,LZSS,与,LZ77,比较,在相同的计算机环境下，,LZSS,算法比,LZ77,可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了,LZSS,的思想。例如，,PKZip,GZip,ARJ,LHArc,和,ZOO,等等，其差别仅仅是指针的长短和窗口的大小等有所不同。,LZSS,同样可以和熵编码联合使用，例如,ARJ,就与霍夫曼编码联用，而,PKZip,则与,Shannon-Fano,联用，它的后续版本也采用霍夫曼编码。,53,LZ78,原理,LZ78,的编码思想是不断地从字符流中提取新的字符串,(String),，通俗地理解为新“词条”，然后用“代号”也就是码字,(Code word),表示这个“词条”。这样一来，对字符流的编码就变成了用码字,(Code word),去替换字符流,(Char stream),，生成码字流,(Code stream),，从而达到压缩数据的目的。,54,LZ77,与,LZ78,比较,LZ77,利用滑动窗口里的内容作为字典，找最长子串,LZ78,动态构建字典,55,LZ78,编码,在编码开始时词典是空的，不包含任何字符串,(string),。在这种情况下编码器就输出一个表示空字符串的特殊码字,(,例如“,0”),和字符流中,(Charstream),的第一个字符,C,，并把这个字符,C,添加到词典中作为一个由一个字符组成的字符串,(string),。在编码过程中，如果出现类似没有任何匹配的情况，也照此办理。,在词典中已经包含某些字符串,(String),之后，如果“当前前缀,P+,当前字符,C”,已经在词典中，就用字符,C,来扩展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的字符串,(String),为止。,此时就输出表示当前前缀,P,的码字,(Code word),和字符,C,，并把,P+C,添加到词典中，然后开始处理字符流,(Charstream),中的下一个字符。,56,算法,在开始时，词典和当前前缀,P,都是空的。,当前字符,C,：,=,字符流中的下一个字符。,判断,P+C,是否在词典中：,(1),如果“是”：用,C,扩展,P,，让,P,：,=P+C,；,(2),如果“否”：,输出与当前前缀,P,相对应的码字和当前字符,C,；,把字符串,P+C,添加到词典中。,令,P,：,=,空值。,(3),判断字符流中是否还有字符需要编码,如果“是”：返回到步骤,2,。,如果“否”：若当前前缀,P,不是空的，输出相应于当前前缀,P,的码字，然后结束编码。,57,LZ78,编码输出,LZ78,编码器的输出是码字,-,字符,(W,C),对，每次输出一对到码字流中，与码字,W,相对应的字符串,(String),用字符,C,进行扩展生成新的字符串,(String),，然后添加到词典中。,58,例子,位置,1,2,3,4,5,6,7,8,9,字符,A,B,B,C,B,C,A,B,A,步骤,位置,当前字符,C,当前前缀,P,添加词典,输出,1,1,A,，,A,(0,A),2,2,B,，,B,(0,B),3,3,B,C,，,B,BC,B C,(2,C),4,5,B,C,A,，,B,BC,BCA,，,B C A,(3,A),5,8,B,A,，,B,BA,，,B A,(2,A),59,LZ78,与,LZ77,LZ78,在每个编码步骤中减少了,string,比较数目,LZ77,需要找最长匹配子串,压缩率与,LZ77,类似。,60,LZW,Terry A.Weltch,在,1984,年发表了改进,LZ78,的文章，因此把这种编码方法称为,LZW(Lempel-Ziv Walch),61,LZW,与,LZ78,编码原理差别,LZW,只输出代表词典中的字符串,(String),的码字,(code word),。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根,(Root),。,由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀,(one-character prefix),，因此至少可以在词典中找到长度为,1,的匹配串。,62,LZW,的词典,LZW,编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀,(Prefix),的字符序列，并且为每个表项分配一个码字,(Code word),，或者叫做序号。,Welch,的论文中用了,12,位码字，,12,位可以有,4096,个不同的,12,位代码，这就是说，转换表有,4096,个表项，其中,256,个表项用来存放已定义的字符，剩下,3840,个表项用来存放前缀,(Prefix),。,63,例子,码字,(,Code word),前缀,(,Prefix),1,193,A,194,B,255,1305,abcdefxyF01234,64,LZW,编码,LZW,编码器就是通过管理这个词典完成输入与输出之间的转换。,LZW,编码器的输入是字符流,(Char stream),，字符流可以是用,8,位,ASCII,字符组成的字符串，而输出是用,n,位,(,例如,12,位,),表示的码字流,(Code stream),，码字代表单个字符或多个字符组成的字符串,(String),。,LZ78,输出是码字,+,字符,C,B,A,B,B,C,B,A,A,193,65,贪婪分析算法,LZW,采用,greedy parsing algorithm,每一次分析都要串行地检查来自字符流,(Charstream),的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀,(Prefix),。,用已知的前缀,(Prefix),加上下一个输入字符,C,也就是当前字符,(Current character),作为该前缀的扩展字符，形成新的扩展字符串。,判断新的串是否在词典中,是：继续输入,C,否：加入词典，分配码字,66,具体执行步骤,开始时词典包含所有可能的根,(Root),，当前前缀,P,是空的；,当前字符,(C),：,=,字符流中的下一个字符；,判断缀,-,符串,P+C,是否在词典中,如果“是”：,P,：,=P+C/(,用,C,扩展,P),；,如果“否”,把代表当前前缀,P,的码字输出到码字流,;,把缀,-,符串,P+C,添加到词典,;,令,P,：,=C/(,现在的,P,仅包含一个字符,C);,67,4.,判断字符流中是否还有字符需要编码,(1),如果“是”，就返回到步骤,2,；,(2),如果“否”,把代表当前前缀,P,的码字输出到码字流,;,结束。,注意：每个输出的码字对应于词典中的一个词条，因为只有当出现新的字符串的时候才输出码字。,68,位置,1,2,3,4,5,6,7,8,9,字符,A,B,B,A,B,A,B,A,C,步骤,位置,词典,当前字符,C,当前前缀,P,输出,(1),A,(2),B,(3),C,1,1,(4),A B,A,B,A,AB,B,(1),2,2,(5),B B,B,BB,B,(2),3,3,(6),B A,A,BA,A,(2),4,4,(7),A B A,B,A,AB,ABA,A,(4),5,6,(8),A B A C,B,A,C,AB,ABA,ABAC,C,(7),6,-,-,-,(3),69,LZW,的特点,1),对于一段短语，它只输出一个数字，即字典中的序号。（这个数字的位数决定了字典的最大容量，当它的位数取得太大时，比如,24,位以上，对于短匹配占多数的情况，压缩率可能很低。取得太小时，比如,8,位，字典的容量受到限制。所以同样需要取舍。）,2),对于一个短语，比如,abcd,，当它在待压缩文件中第一次出现时，,ab,被加入字典，第二次出现时，,abc,被加入字典，第三次出现时，,abcd,才会被加入字典，对于一些长匹配，它必须高频率地出现，并且字典有较大的容量，才会被最终完整地加入字典。相应地，,lz77,只要匹配在“字典区域”中存在，马上就可以直接使用。,3),一个长匹配被加入字典的过程，是从两个字节开始，逐次增长一个字节，确定了字典的最大容量，也就间接确定了匹配的可能的最大长度。,70,LZW,与,LZ77,相对于,lz77,用两个数字来表示一个短语，,lzw,只用一个数字来表示一个短语，因此，“字典序号”的位数可以取得多一点（二进制数多一位，意味着数值大一倍），也就是说最长匹配可以比,lz77,更长，当某些超长匹配高频率地出现，直到被完整地加入字典后，,lzw,将开始弥补初期的低效，逐渐显出自己的优势。,在多数情况下，,lz77,拥有更高的压缩率，而在待压缩文件中占绝大多数的是些超长匹配，并且相同的超长匹配高频率地反复出现时，,lzw,更具优势，,GIF,就是采用了,lzw,算法来压缩背景单一、图形简单的图片。,zip,是用来压缩通用文件的，这就是它采用对大多数文件有更高压缩率的,lz77,算法的原因。,第,2,章 数据无损压缩,参考文献和站点,David Salomon,Data Compression,ISBN 0-387-40697-2,Third Edition,Springer-Verlag,2004,Data Compression Reference Center,，,compress.rasip.fer.hr/index_menu.htm,Timothy C.Bell,John G.Cleary,Ian H.Witten.,Text Compression,.Prentice-Hall,Inc.,1990,Ziv,J.and Lempel,A.A,Universal Algorithm for Sequential Data Compression,.IEEE Transactions on Information Theory,May 1977,Terry A.Welch,A Technique for High-Performance Data Compression.,Computer,June 1984,Nelson,M.R.,LZW Data Compression,.Dr.Dobbs Journal,October 1989,，,marknelson.us/1989/10/01/lzw-data-compression/,R.Hunter and A.H.Robison.,International Digital Facsimile Coding Standards,.Proceedings of the IEEE,Vol.68,No.7,，,July,1980,，,pp854,867,2026年10月22日,第,2,章 数据无损压缩,71,of 72,END,第,2,章 数据无损压缩,