《【教学课件】第五章字典编码.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第五章字典编码.ppt（128页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 字典编码n n迄今为止，我们大多假设符号是独立的迄今为止，我们大多假设符号是独立的n n但这对许多常见数据类型来说是不对的但这对许多常见数据类型来说是不对的n n如：文本、图像和源代码文件如：文本、图像和源代码文件n n基本思想基本思想n n标识经常出现的符号模式标识经常出现的符号模式保存于字典中保存于字典中n n对这些常出现的模式采用更有效的编码方式对这些常出现的模式采用更有效的编码方式用其在字典中的索用其在字典中的索引作为码字引作为码字n n而对其它部分采用缺省（不太有效）的编码方式而对其它部分采用缺省（不太有效）的编码方式n n以期总的编码效率更高以期总的编码效率更高n n注意注
2、意n n这对如文本这样的信源是合理的这对如文本这样的信源是合理的n n显然对（接近）随机数据不会有效显然对（接近）随机数据不会有效1例n n考虑某英文文本信源考虑某英文文本信源n n26 26 字母和字母和6 6个标点符号个标点符号n n单字符，定长码单字符，定长码n n5 5 比特比特/字符字符n n4 4字符模式，定长码字符模式，定长码n n2020比特比特/模式模式(32(324 4=2=22020=1,048,576)=1,048,576)n n假设为非均匀分布假设为非均匀分布n n字典字典：256256个最常出现的模式，每个用个最常出现的模式，每个用8 8比特编码比特编码n n对其它
3、模式用对其它模式用2020比特编码比特编码n n再增加再增加1 1比特用于指示是上述两种情况中的哪种比特用于指示是上述两种情况中的哪种2例(2)n n若用若用p p 表示使用字典的概率，则比特率为表示使用字典的概率，则比特率为R R=9=9p p+21(1-+21(1-p p)=21-12)=21-12p pn n压缩压缩 21-12p 20 21-12p =p p 0.084 0.084n n还不太坏还不太坏n n在等概率假设下，在等概率假设下，p=0.00025p=0.00025n n p p越大，性能越好越大，性能越好 选择最可能出现的模式存于字典中选择最可能出现的模式存于字典中n n为
4、了达到好的性能，需要知道信源的结构信息为了达到好的性能，需要知道信源的结构信息n n有足够的先验信息，有足够的先验信息，静态字典静态字典n n否则，在编码过程中获得信源的知识否则，在编码过程中获得信源的知识 自适应字典自适应字典3静态字典n n静态字典静态字典n n对信源的结构有足够的先验知识时，对信源的结构有足够的先验知识时，利用先验知识构利用先验知识构造造字典字典n n对特定应用特别有效对特定应用特别有效n n只对针对其设计的特定应用和数据有效只对针对其设计的特定应用和数据有效n n例：电话号码的区号例：电话号码的区号n n例：学校的学生信息表例：学校的学生信息表地地 区区长途区号长途区号
5、北京市北京市 010010上海市上海市021021天津市天津市022022重庆市重庆市023023沈阳市沈阳市024024南京市南京市025025乌鲁木齐市乌鲁木齐市09910991喀什市喀什市 0998 0998 4自适应字典n n有许多场合，开始时不知道要编码数据的统计特性，也不一有许多场合，开始时不知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。定允许事先知道它们的统计特性。n n字典编码的思路：根据数据本身包含有重复代码的特性字典编码的思路：根据数据本身包含有重复代码的特性n n例：例：吃吃葡萄葡萄不吐不吐葡萄皮葡萄皮，不吃，不吃葡萄葡萄倒吐倒吐葡萄皮葡萄皮n n如果用一
6、些简单的代号代替这些字符串，就可以实现压缩，实际上如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。典。n n实用的字典编码算法的核心就是如何动态地形成字典，以及如何选实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余择输出格式以减小冗余。5自适应字典n n开始n nJacob Ziv/Abraham LempelJacob Ziv/Abraham Lempeln n1977(LZ77/LZ1),1978(LZ78/LZ2)1977(LZ7
7、7/LZ1),1978(LZ78/LZ2)n n1984 Terry Welch(LZW)1984 Terry Welch(LZW)n nLZ77 vs.LZ78n n两种不同的方法两种不同的方法n n有很多变种有很多变种n n是很多主流压缩的基础是很多主流压缩的基础6LZ77n n基本方法：字典为先前已编码序列的一部分基本方法：字典为先前已编码序列的一部分n n搜索缓冲区为当前字典，通常为几千字节搜索缓冲区为当前字典，通常为几千字节n n机制：滑动窗口机制：滑动窗口n n搜索缓冲区搜索缓冲区(Search buffer)Search buffer)、前向（、前向（look aheadlook
8、 ahead）缓冲区、）缓冲区、搜索指针搜索指针(search pointer)(search pointer)n n目标：在搜索缓冲区中，寻找与搜索指针指向的字符目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串，并对其进行编码串匹配的最长串，并对其进行编码n n基本原理：如果某些模式在局部重复出现，能得基本原理：如果某些模式在局部重复出现，能得到更有效的表示到更有效的表示7LZ77(2)n n(o)ffset=search ptr-match ptr=(o)ffset=search ptr-match ptr=7 7n n(l)ength=(l)ength=连续匹配的字符数连续匹
9、配的字符数=4 4n n(c)odeword=C(r)(c)odeword=C(r)n n编码编码n n=n nIf|search buff|=S,|A|=A,If|search buff|=S,|A|=A,S+|LA buff|=WS+|LA buff|=Wn n定长码：定长码：loglog2 2S S +loglog2 2WW +loglog2 2A A Search pointer8LZ77 编码举例n n序列序列n ncabracadabrarrarradcabracadabrarrarradn nW=13,S=7W=13,S=7n n|cabraca|cabraca|d dabrar
10、|rarradabrar|rarradn n对对d d，没有匹配的字符串，没有匹配的字符串n n发送发送 (可以做得更好可以做得更好?)?)n n|abracad|abracad|a abrarr|rarradbrarr|rarrad|abrac|abraca ad|d|a abrarr|rarradbrarr|rarrad|abr|abra acad|cad|a abrarr|rarradbrarr|rarrad|abraabracad|cad|abraabrarr|rarradrr|rarradn n发送发送 9LZ77 编码举例(2)n n|cadabrar|cadabrar|r rar
11、rad|arrad|cadabra|cadabrar r|r rarrad|arrad|cadab|cadabrarrar|rarrarrad|rad|n n发送发送 n n可以做得更好可以做得更好?n n发送发送!n n总结：三种情况总结：三种情况n n没有匹配没有匹配n n匹配匹配n n匹配串超过了搜索缓冲区匹配串超过了搜索缓冲区10LZ77 解码举例 n n输入输入n n n n输出输出n ncabracacabracan n解码：解码：n n增加一个增加一个 d:c|abraca d:c|abracad d|n n解码：解码：n n从第一个从第一个aa开始，拷贝开始，拷贝4 4个字母，
12、解码个字母，解码C(r)C(r)cabrac|adcabrac|adabrarabrar|n n解码：解码：n n从第一个从第一个rr开始，拷贝开始，拷贝3 3个字母个字母 cabracada|brarcabracada|brarrarrar|n n再拷贝再拷贝2 2个字母个字母cabracadabr|arrarcabracadabr|arrararar|n n解码解码C(d)C(d)：cabracadabrarrararcabracadabrarrarard d11LZ77编码小结n n使用固定大小窗口进行词语匹配，而不是在所有已经编码使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息
13、中匹配，是因为匹配算法的时间消耗往往很多，必的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；须限制词典的大小才能保证算法的效率；n n随着压缩的进程滑动词典窗口，使其中总包含最近编码过随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。在最近的上下文中更容易找到匹配串。n nLZ77LZ77解码器比编码器简单得多（非对称压缩）解码器比编码器简单得多（非对称压缩）n n维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹维持
14、一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串及第配串，将匹配串及第3 3个字段的字符写入输出流，同时移进缓冲区个字段的字符写入输出流，同时移进缓冲区n n在如文件压缩（一次压缩，多次还原）的场合很有用在如文件压缩（一次压缩，多次还原）的场合很有用12LZ77的变种n n迄今为止迄今为止n n自适应模型，没有先验知识自适应模型，没有先验知识n n渐近渐近 接近知道信源统计知识的情况接近知道信源统计知识的情况n n但是，局部性起到了很大作用但是，局部性起到了很大作用n n改进改进n n变长编码变长编码n noffset:offset:各数值基本均匀分布，一般用定长码各数值基本
15、均匀分布，一般用定长码n nlength:length:可用可用HuffmanHuffman码码/Golomb/Golomb码码/Exp-Golomb/Exp-Golomb码码n nPKZip,Zip,Lharcm ONG,gzip,ARJPKZip,Zip,Lharcm ONG,gzip,ARJn n可变缓冲区大小可变缓冲区大小n n需设计较完善的数据结构来实现对大缓冲区的快速搜索需设计较完善的数据结构来实现对大缓冲区的快速搜索n nLZSSLZSS：搜索缓冲区（字典）用对分查找树保持，前向缓冲区用循环：搜索缓冲区（字典）用对分查找树保持，前向缓冲区用循环队列表示队列表示n n取消取消 n
16、nLZSSLZSS：只需增加：只需增加1 1一个标记位，用于指示是否为单字符一个标记位，用于指示是否为单字符13LZ78n nLZ77假设模式满足局部性n nLZ78:n n没有搜索缓冲区没有搜索缓冲区代之以显式的字典代之以显式的字典n n编码器编码器/解码器必须同步建立字典解码器必须同步建立字典n n 如没有匹配，将字典原有词条如没有匹配，将字典原有词条+当前没有匹配的字当前没有匹配的字符符 字典的新词条字典的新词条n n编码：编码：n ni=i=字典索引字典索引n n同同LZ77LZ77，i=0 i=0 表示在字典中没有找到匹配的词条表示在字典中没有找到匹配的词条n nc=c=下一字符的码
17、字下一字符的码字14LZ78举例索引索引条目条目字典：输入：wabbawabbawabbawabbawoowoowoo输出：15LZ78举例(2)索引索引条目条目1 1w w字典：输入：wabbawabbawabbawabbawoowoowoo输出：16LZ78举例(3)索引索引条目条目1 1w w2 2a a字典：输入：-abbawabbawabbawabbawoowoowoo输出：17LZ78举例(4)索引索引条目条目1 1w w2 2a a3 3b b字典：输入：-bbawabbawabbawabbawoowoowoo输出：18LZ78举例(5)索引索引条目条目1 1w w2 2a a3
18、 3b b4 4baba字典：输入：-bawabbawabbawabbawoowoowoo输出：19LZ78举例(6)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 字典：输入：-wabbawabbawabbawoowoowoo输出：20LZ78举例(7)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa字典：输入：-wabbawabbawabbawoowoowoo输出：21LZ78举例(8)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb字典：输入：-bbawabbawabb
19、awoowoowoo输出：22LZ78举例(9)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 字典：输入：-a wabbawabbawoowoowoo输出：23LZ78举例(10)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab字典：输入：-wabbawabbawoowoowoo输出：24LZ78举例(11)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab
20、1010baba 字典：输入：-ba wabbawoowoowoo输出：25LZ78举例(12)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 字典：输入：-wabbawoowoowoo输出：1111wabbwabb26LZ78举例(13)字典：输入：-a woowoowoo输出：1111wabbwabb1212a a w w索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 27LZ78举例
21、(14)字典：输入：-oowoowoo输出：1111wabbwabb1212a a w w1313o o索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 28LZ78举例(15)字典：输入：-o woowoo输出：1111wabbwabb1212a a w w1313o o1414o o 索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 29LZ78举例(16)字典：输入：-woowoo输出：
22、1111wabbwabb1212a a w w1313o o1414o o 1515wowo索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 30LZ78举例(17)字典：输入：-o woo输出：1111wabbwabb1212a a w w1313o o1414o o 1515wowo1616o o w w索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 31LZ78举例(18)字典：输入：
23、-oo输出：1111wabbwabb1212a a w w1313o o1414o o 1515wowo1616o o w w1717oooo索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 32LZ78n n观察：如果继续编码，字典将继续增长观察：如果继续编码，字典将继续增长n n实用的选择实用的选择n n停止增长字典停止增长字典n n相当于从此成为一个静态字典策略相当于从此成为一个静态字典策略n n删除一些较早用过的项删除一些较早用过的项n n如基于使用统计（但还没有好的算法决定哪些项该删
24、）如基于使用统计（但还没有好的算法决定哪些项该删）n n将字典全部删除，从空字典开始重建字典将字典全部删除，从空字典开始重建字典n n如果没有信源的特定知识，任何方法可能都不会工作如果没有信源的特定知识，任何方法可能都不会工作得很好！得很好！33LZ78的变种：LZWn nTerry Welch(1984)Terry Welch(1984)n n基本思想：基本思想：n n只对只对i i编码，而不是编码编码，而不是编码 n n算法：算法：n n/初始化字典为包含所有字母初始化字典为包含所有字母 Seed dictionary with all alphabet letters,Seed dict
25、ionary with all alphabet letters,p p=null =null while(!done)while(!done)a a=get_next_symbol=get_next_symbolif(if(p p a a)is in dictionary )is in dictionary /在字典中，继续用更长的字符串匹配在字典中，继续用更长的字符串匹配p p=p p a aelseelsesend out index of send out index of p p /不在字典中，输出已匹配部分，从不在字典中，输出已匹配部分，从a a 重新开始重新开始p.a p.a i
26、s added to dictionaryis added to dictionary p p=a aendwhileendwhile34LZW编码索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 67 78 89 91010字典：输出：输入：wabbawabbawabbawabbawoowoowoop=35LZW编码(2)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 67 78 89 91010字典：输出：输入：wabbawabbawabbawabbawoowoowoop=w 36LZW编码(3)索引索引条目条目1 1 2 2a a3
27、3b b4 4o o5 5w w6 6wawa7 78 89 91010字典：输出：5(w)输入：-abbawabbawabbawabbawoowoowoop=wa37LZW编码(4)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 89 91010字典：输出：5(w)2(a)输入：-bbawabbawabbawabbawoowoowoop=ab38LZW编码(5)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 91010字典：输出：5(w)2(a)3(b)输入：-baw
28、abbawabbawabbawoowoowoop=bb39LZW编码(6)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010字典：输出：5(w)2(a)3(b)3(b)输入：-awabbawabbawabbawoowoowoop=ba40LZW编码(7)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)输入：-wabbawabbawabbawoowoowoop=a4
29、1LZW编码(8)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()输入：-wabbawabbawabbawoowoowoo索引索引条目条目1111 w w121213131414151516161717181819192020p=w42LZW编码(9)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a
30、)1()输入：-abbawabbawabbawoowoowoo索引索引条目条目1111 w w121213131414151516161717181819192020p=wa43LZW编码(10)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)输入：-bbawabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab13131414151516161717181819192020p=wab44LZW编码
31、(11)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)输入：-bawabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab13131414151516161717181819192020p=bb45LZW编码(12)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(
32、b)2(a)1()6(wa)8(bb)输入：-a wabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414151516161717181819192020p=bba46LZW编码(13)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)输入：-wabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba141415
33、1516161717181819192020p=a47LZW编码(14)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入：-wabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w151516161717181819192020p=aw48LZW编码(15)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6
34、wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入：-abbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w151516161717181819192020p=wa49LZW编码(16)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a
35、)输入：-bbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w151516161717181819192020p=wab50LZW编码(17)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)输入：-bawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1
36、515wabbwabb16161717181819192020p=wabb51LZW编码(18)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)输入：-awabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb16161717181819192020p=ba52LZW编码(19)索引索引条目条目1 1 2 2a
37、 a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)输入：-wabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717181819192020p=ba53LZW编码(20)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a
38、 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)输入：-wabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717181819192020p=w54LZW编码(21)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba
39、)11(w)输入：-abbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa181819192020p=wa55LZW编码(22)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)输入：-bbawoowoowoo索引索引条目条目1111 w w1212wabw
40、ab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa181819192020p=ab56LZW编码(23)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)输入：-bawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba
41、 1717 wawa1818abbabb19192020p=abb57LZW编码(24)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)输入：-awoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb19192020p=ba58LZW
42、编码(25)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)输入：-woowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb19192020p=ba59LZW编码(26)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5
43、w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w2020p=baw60LZW编码(27)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb
44、9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-oowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w2020wowop=wo5(w)61LZW编码(28)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：
45、输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-owoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w2020wowop=oo5(w)4(o)索引索引条目条目2121oooo22222323242425252626272728282929303062LZW编码(29)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6
46、6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w2020wowop=o5(w)4(o)4(o)索引索引条目条目2121oooo2222o o 2323242425252626272728282929303063LZW编
47、码(30)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w2020wowop=w5(w)4(o)4(o)索引索引条目条目2121oooo222
48、2o o 2323242425252626272728282929303064LZW编码(31)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-oowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w
49、2020wowop=wo5(w)4(o)4(o)11(w)索引索引条目条目2121oooo2222o o 2323 wowo242425252626272728282929303065LZW编码(32)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-owoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w
50、1515wabbwabb1616baba 1717 wawa1818abbabb1919baba w w2020wowop=oo5(w)4(o)4(o)11(w)索引索引条目条目2121oooo2222o o 2323 wowo242425252626272728282929303066LZW编码(33)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：