多媒体技术基础第版数据无损压缩课件

多媒体技术基础(第3版)

第2章数据无损压缩张奇复旦大学计算机科学技术学院2015年4月多媒体技术基础(第3版)

第2章数据无损压缩张奇2023年8月23日第2章数据无损压缩2of72第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.3RLE编码2.4词典编码2.4.1词典编码的思想2.4.2LZ77算法2.4.3LZSS算法2.4.4LZ78算法2.4.5LZW算法参考文献和站点2023年8月2日第2章数据无损压缩2of72第2章2023年8月23日第2章数据无损压缩3of722.0数据无损压缩概述数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限三种多媒体数据类型文字(text)数据——无损压缩根据数据本身的冗余(Basedondataredundancy)声音(audio)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的听觉系统特性(Basedonhumanhearingsystem)图像(image)/视像(video)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的视觉系统特性(Basedonhumanvisualsystem)

2023年8月2日第2章数据无损压缩3of722.02023年8月23日第2章数据无损压缩4of722.0数据无损压缩概述(续1)数据无损压缩的理论——信息论(informationtheory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储该术语源于ClaudeShannon(香农)发表的“AMathematicalTheoryofCommunication”论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。数据无损压缩的方法霍夫曼编码(Huffmancoding)算术编码(arithmeticcoding)行程长度编码(run-lengthcoding)词典编码(dictionarycoding)……2023年8月2日第2章数据无损压缩4of722.02023年8月23日第2章数据无损压缩5of722.0数据无损压缩概述(续2)TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html信息论之父介绍2023年8月2日第2章数据无损压缩5of722.02023年8月23日第2章数据无损压缩6of722.0数据无损压缩概述(续3)ClaudeShannon

——Thefoundingfatherofelectroniccommunicationsage；AmericanmathematicalengineerIn1936~1940,MIT:Master'sthesis,AsymbolicanalysisofrelayandswitchingcircuitsDoctoralthesis:ontheoreticalgeneticsIn1948:Amathematicaltheoryofcommunication,landmark,climax(AnimportantfeatureofShannon'stheory:conceptofentropy)2023年8月2日第2章数据无损压缩6of722.02023年8月23日第2章数据无损压缩7of722.1数据的冗余冗余概念人为冗余在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达2023年8月2日第2章数据无损压缩7of722.12023年8月23日第2章数据无损压缩8of722.1数据的冗余(续1)决策量(decisioncontent)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为

H0=log(n)其中，n是事件数决策量的单位由对数的底数决定Sh(Shannon):用于以2为底的对数Nat(naturalunit):用于以e为底的对数Hart(hartley)：用于以10为底的对数2023年8月2日第2章数据无损压缩8of722.12023年8月23日第2章数据无损压缩9of722.1数据的冗余(续2)信息量(informationcontent)具有确定概率事件的信息的定量度量在数学上定义为

其中，是事件出现的概率举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a,b和c出现的概率，这些事件的信息量分别为，

I(a)=log2(1/0.50)=1shI(b)=log2(1/0.25)=2shI(c)=log2(1/0.25)=2sh一个等概率事件的集合，每个事件的信息量等于该集合的决策量2023年8月2日第2章数据无损压缩9of722.12023年8月23日第2章数据无损压缩10of722.1数据的冗余(续3)熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(meaninformationcontent)用数学表示为2023年8月2日第2章数据无损压缩10of722.12023年8月23日第2章数据无损压缩11of722.1数据的冗余(续4)数据的冗余量2023年8月2日第2章数据无损压缩11of722.12023年8月23日第2章数据无损压缩12of722.2统计编码 统计编码给已知统计信息的符号分配代码的数据无损压缩方法编码方法香农-范诺编码霍夫曼编码算术编码编码特性香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵2023年8月2日第2章数据无损压缩12of722.22023年8月23日第2章数据无损压缩13of722.2.1统计编码——香农-范诺编码 香农-范诺编码(Shannon–Fanocoding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”。“位”是1948年Shannon首次使用的术语。例如最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon-Fano)编码法2023年8月2日第2章数据无损压缩13of722.22023年8月23日第2章数据无损压缩14of722.2.1香农-范诺编码香农-范诺编码举例有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1(1)计算该图像可能获得的压缩比的理论值(2)对5个符号进行编码(3)计算该图像可能获得的压缩比的实际值表2-1符号在图像中出现的数目符号ABCDE出现的次数157765出现的概率15/407/407/406/405/402023年8月2日第2章数据无损压缩14of722.22023年8月23日第2章数据无损压缩15of722.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.84≈1.37:1，实际上就是3:2.196≈1.372023年8月2日第2章数据无损压缩15of722.22023年8月23日第2章数据无损压缩16of722.2.1香农-范诺编码(续2)(2)符号编码对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图2-1所示2023年8月2日第2章数据无损压缩16of722.22023年8月23日第2章数据无损压缩17of722.2.1香农-范诺编码(续3)（3）压缩比的实际值按照这种方法进行编码需要的总位数为30+14+14+18+15＝91，实际的压缩比为120:91≈1.32:1图2-1香农-范诺算法编码举例

2023年8月2日第2章数据无损压缩17of722.22023年8月23日第2章数据无损压缩18of722.2.2统计编码——霍夫曼编码 霍夫曼编码(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中2023年8月2日第2章数据无损压缩18of722.22023年8月23日第2章数据无损压缩19of722.2.2霍夫曼编码—CaseStudy1霍夫曼编码举例1现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比2023年8月2日第2章数据无损压缩19of722.22023年8月23日第2章数据无损压缩20of722.2.2霍夫曼编码—CaseStudy1(续1)符号出现的次数log2(1/pi）分配的代码需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率2023年8月2日第2章数据无损压缩20of722.22023年8月23日第2章数据无损压缩21of722.2.2霍夫曼编码—CaseStudy1(续2)(1)计算该字符串的霍夫曼码步骤①：按照符号出现概率大小的顺序对符号进行排序步骤②：把概率最小的两个符号组成一个节点P1步骤③：重复步骤②，得到节点P2，P3，P4，……，

PN，形成一棵树，其中的PN称为根节点步骤④：从根节点PN开始到每个符号的树叶，从上到下

标上0(上枝)和1(下枝)，至于哪个为1哪个为0则

无关紧要，但通常把概率大的标成1，概率小的

标成0步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出

每个符号的代码2023年8月2日第2章数据无损压缩21of722.22023年8月23日第2章数据无损压缩22of722.2.2霍夫曼编码—CaseStudy1(续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)2023年8月2日第2章数据无损压缩22of722.22023年8月23日第2章数据无损压缩23of722.2.2霍夫曼编码—CaseStudy1(续4)符号出现的次数log2(1/pi）分配的代码需要的位数B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合计301.06730个字符组成的字符串需要67位5个符号的代码2023年8月2日第2章数据无损压缩23of722.22023年8月23日第2章数据无损压缩24of722.2.2霍夫曼编码—CaseStudy1(续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–(8×lg8＋

10×lg10＋

3×lg3＋

4

×lg4＋5lg5)]/(30×log22)

=(44.3136－24.5592)/9.0308＝

2.1874(Sh)2023年8月2日第2章数据无损压缩24of722.22023年8月23日第2章数据无损压缩25of722.2.2霍夫曼编码—CaseStudy1(续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位2023年8月2日第2章数据无损压缩25of722.22023年8月23日第2章数据无损压缩26of722.2.2霍夫曼编码—CaseStudy2霍夫曼编码举例2编码前N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(N=23=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)编码效率2023年8月2日第2章数据无损压缩26of722.22023年8月23日第2章数据无损压缩27of722.2.2霍夫曼编码—CaseStudy2(续1)2023年8月2日第2章数据无损压缩27of722.22023年8月23日第2章数据无损压缩28of722.2.2霍夫曼编码—CaseStudy2(续2)Averagelengthpersymbol

(beforecoding):(2)Entropy:(3)Averagelengthpersymbol

(withHuffmancoding):(4)Efficiencyofthecode:2023年8月2日第2章数据无损压缩28of722.22023年8月23日第2章数据无损压缩29of722.2.3统计编码——算术编码 算术编码(arithmeticcoding)给已知统计信息的符号分配代码的数据无损压缩技术基本思想是用0和1之间的一个数值范围表示输入流中的一个字符，而不是给输入流中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵2023年8月2日第2章数据无损压缩29of722.22023年8月23日第2章数据无损压缩30of722.2.3算术编码举例[例2.3]（取自教材）假设信源符号为{00,01,10,11}，它们的概率分别为{0.1,0.4,0.2,0.3}对二进制消息序列10001100101101…进行算术编码2023年8月2日第2章数据无损压缩30of722.22023年8月23日第2章数据无损压缩31of722.2.3算术编码举例(续1)符号00011011概率0.10.40.20.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称为高边界或右边界2023年8月2日第2章数据无损压缩31of722.22023年8月23日第2章数据无损压缩32of722.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-62023年8月2日第2章数据无损压缩32of722.22023年8月23日第2章数据无损压缩33of722.2.3算术编码举例(续3)图2-3例2.3的算术编码过程2023年8月2日第2章数据无损压缩33of722.22023年8月23日第2章数据无损压缩34of722.2.3算术编码举例(续4)2023年8月2日第2章数据无损压缩34of722.22023年8月23日第2章数据无损压缩35of722.2.3算术编码举例(续5)2023年8月2日第2章数据无损压缩35of722.22023年8月23日第2章数据无损压缩36of722.3RLE编码行程长度编码(Run-LengthCoding)一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数。在JPEG，MPEG，H.261和H.263等压缩方法中，RLE用来对图像数据变换和量化后的系数进行编码例:假设有一幅灰度图像第n行的像素值如图2-5所示。用RLE编码方法得到的代码为：80315084180图2-5RLE编码概念2023年8月2日第2章数据无损压缩36of722.32023年8月23日第2章数据无损压缩37of722.3RLE编码(续)Assumption:Longsequencesofidenticalsymbols.Example,2023年8月2日第2章数据无损压缩37of722.32023年8月23日第2章数据无损压缩38of722.4词典编码词典编码(dictionarycoding)文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时,编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典两种类型的编码算法具体算法LZ77算法LZSS算法LZ78算法LZW算法2023年8月2日第2章数据无损压缩38of722.42023年8月23日第2章数据无损压缩39of722.4词典编码(续1)第一类编码算法用已经出现过的字符串替代重复的部分编码器的输出仅仅是指向早期出现过的字符串的“指针”图2-6第一类词典编码概念2023年8月2日第2章数据无损压缩39of722.42023年8月23日第2章数据无损压缩40of722.4词典编码(续2)第二类编码算法从输入的数据中创建一个“短语词典(dictionaryofthephrases)”编码器输出词典中的短语“索引号”，而不是短语图2-7第二类词典编码概念2023年8月2日第2章数据无损压缩40of722.441LZ77算法第一类词典编码里：所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以AbrahamLempel和JakobZiv在1977年开发和发表的称为LZ77算法为基础的JacobZiv,AbrahamLempel,AUniversalAlgorithmforSequentialDataCompression,IEEETransactionsonInformationTheory,23(3):337-343,May1977.41LZ77算法第一类词典编码里：所指的“词典”是指用以前处42LZ77算法LZ77算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。42LZ77算法LZ77算法在某种意义上又可以称为“滑动窗43LZ77首先介绍算法中用到的几个术语：输入数据流(inputstream)：要被压缩的字符序列。字符(character)：输入数据流中的基本单元。编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。窗口(window)：指包含W个字符的窗口，字符从编码位置开始向后数，也就是最后处理的字符数。指针(pointer)：指向窗口中的匹配串，一般含有长度。AABCBBABCAW=5已编码未编码B=443LZ77首先介绍算法中用到的几个术语：AABCBBABC44图例输入数据流44图例输入数据流45LZ77算法核心LZ77编码算法的核心：查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下：把编码位置设置到输入数据流的开始位置。查找窗口中最长的匹配串。以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。45LZ77算法核心LZ77编码算法的核心：查找从前向缓冲存46指针表示(Pointer,Length)Characters表示匹配的（字符位置，长度）下一个不匹配的字符指针可以以“(Back_chars,Chars_length)Explicit_character”格式输出。其中，(Back_chars,Chars_length)是指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。46指针表示(Pointer,Length)Charac47例子位置123456789字符AABCBBABCCBABBCBAA编码步骤编码位置匹配串前向缓冲中第一个字符输出(ptr,len)ch11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)CW=5,B=2每次移动窗口和编码位置Len+1Len=0Len=1Len=0Len=147例子位置123456789字符AABCBBABCCBA48LZ77的问题LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针例如前一个例子中(0,0)C二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。48LZ77的问题LZ77通过输出真实字符解决了在窗口中出现49LZSS算法1982年由Storer和Szymanski改进LZ77LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。49LZSS算法1982年由Storer和Szymanski50LZSS编码算法步骤

把编码位置置于输入数据流的开始位置。在前向缓冲存储器中查找与窗口中最长的匹配串

①Pointer：=匹配串指针。

②Length：=匹配串长度。判断匹配串长度Length是否大于等于最小匹配串长度(Length≥MIN_LENGTH)，

如果“是”：输出指针，然后把编码位置向前移动Length个字符。

如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。如果前向缓冲存储器不是空的，就返回到步骤250LZSS编码算法步骤把编码位置置于输入数据流的开始位置51例子位置1234567891011字符AABBCBBAABC步骤位置匹配串输出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC编码过程(MIN_LENGTH=2，W=10,B=3)Len=1<251例子位置1234567891011字符AABBCBBA52LZSS与LZ77比较在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。52LZSS与LZ77比较在相同的计算机环境下，LZSS算法53LZ78原理LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Codeword)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Codeword)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。53LZ78原理LZ78的编码思想是不断地从字符流中提取新的54LZ77与LZ78比较LZ77利用滑动窗口里的内容作为字典，找最长子串LZ78动态构建字典54LZ77与LZ78比较LZ77利用滑动窗口里的内容作为字55LZ78编码在编码开始时词典是空的，不包含任何字符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C，并把这个字符C添加到词典中作为一个由一个字符组成的字符串(string)。在编码过程中，如果出现类似没有任何匹配的情况，也照此办理。在词典中已经包含某些字符串(String)之后，如果“当前前缀P+当前字符C”已经在词典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的字符串(String)为止。此时就输出表示当前前缀P的码字(Codeword)和字符C，并把P+C添加到词典中，然后开始处理字符流(Charstream)中的下一个字符。55LZ78编码在编码开始时词典是空的，不包含任何字符串(s56算法

在开始时，词典和当前前缀P都是空的。当前字符C：=字符流中的下一个字符。判断P+C是否在词典中：(1)如果“是”：用C扩展P，让P：=P+C；(2)如果“否”：①输出与当前前缀P相对应的码字和当前字符C；②把字符串P+C添加到词典中。③令P：=空值。(3)判断字符流中是否还有字符需要编码①如果“是”：返回到步骤2。②如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。56算法在开始时，词典和当前前缀P都是空的。57LZ78编码输出LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。57LZ78编码输出LZ78编码器的输出是码字-字符(W,C58例子位置123456789字符ABBCBCABA步骤位置当前字符C当前前缀P添加词典输出11A－，－A(0,A)22B－，－B(0,B)33BC－，BBC,－BC(2,C)45BCA－，BBCBCA，－BCA(3,A)58BA－，BBA，－BA(2,A)58例子位置123456789字符ABBCBCABA步骤位59LZ78与LZ77LZ78在每个编码步骤中减少了string比较数目LZ77需要找最长匹配子串压缩率与LZ77类似。59LZ78与LZ77LZ78在每个编码步骤中减少了stri60LZWTerryA.Weltch在1984年发表了改进LZ78的文章，因此把这种编码方法称为LZW(Lempel-ZivWalch)60LZWTerryA.Weltch在1984年发表了改进61LZW与LZ78编码原理差别①LZW只输出代表词典中的字符串(String)的码字(codeword)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。②由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-characterprefix)，因此至少可以在词典中找到长度为1的匹配串。61LZW与LZ78编码原理差别62LZW的词典LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Codeword)，或者叫做序号。Welch的论文中用了12位码字，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。62LZW的词典LZW编码是围绕称为词典的转换表来完成的。这63例子码字(Codeword)前缀(Prefix)1

……193A194B……255

……1305abcdefxyF01234……63例子码字(Codeword)前缀(Prefix)1…64LZW编码LZW编码器就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串(String)。LZ78输出是码字+字符CBABBCBAA193…64LZW编码LZW编码器就是通过管理这个词典完成输入与输出65贪婪分析算法LZW采用greedyparsingalgorithm每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Currentcharacter)作为该前缀的扩展字符，形成新的扩展字符串。判断新的串是否在词典中是：继续输入C否：加入词典，分配码字65贪婪分析算法LZW采用greedyparsingal66具体执行步骤开始时词典包含所有可能的根(Root)，当前前缀P是空的；当前字符(C)：=字符流中的下一个字符；判断缀-符串P+C是否在词典中如果“是”：P：=P+C//(用C扩展P)；如果“否”①把代表当前前缀P的码字输出到码字流;②把缀-符串P+C添加到词典;③令P：=C//(现在的P仅包含一个字符C);66具体执行步骤开始时词典包含所有可能的根(Root)，当前674.判断字符流中是否还有字符需要编码(1)如果“是”，就返回到步骤2；(2)如果“否”①把代表当前前缀P的码字输出到码字流;②结束。注意：每个输出的码字对应于词典中的一个词条，因为只有当出现新的字符串的时候才输出码字。674.判断字符流中是否还有字符需要编码68位置123456789字符ABBABABAC步骤位置词典当前字符C当前前缀P输出

(1)A

－

－

(2)B

－

－

(3)C

－

－

11(4)ABABAAB,B(1)22(5)BBBBB,B(2)