第五章字典编码

1、1第五章 字典编码n迄今为止，我们大多假设符号是独立的n但这对许多常见数据类型来说是不对的n如：文本、图像和源代码文件n基本思想n标识经常出现的符号模式保存于字典中n对这些常出现的模式采用更有效的编码方式用其在字典中的索引作为码字n而对其它部分采用缺省（不太有效）的编码方式n以期总的编码效率更高n注意n这对如文本这样的信源是合理的n显然对（接近）随机数据不会有效2例n考虑某英文文本信源n26 字母和6个标点符号n单字符，定长码n5 比特/字符n4字符模式，定长码n20比特/模式 (324 = 220 = 1,048,576)n假设为非均匀分布n字典：256个最常出现的模式，每个用8比特编码n对

2、其它模式用20比特编码n再增加1比特用于指示是上述两种情况中的哪种3例 (2)n若用p 表示使用字典的概率，则比特率为r = 9p + 21(1-p) = 21 - 12pn压缩 21 - 12p p 0.084n还不太坏n在等概率假设下，p = 0.00025n p越大，性能越好 选择最可能出现的模式存于字典中n为了达到好的性能，需要知道信源的结构信息n有足够的先验信息， 静态字典n否则，在编码过程中获得信源的知识 自适应字典4静态字典n静态字典n对信源的结构有足够的先验知识时，利用先验知识构造字典n对特定应用特别有效n只对针对其设计的特定应用和数据有效n例：电话号码的区号n例：学校的学生信

3、息表地 区长途区号北京市 010上海市021天津市022重庆市023沈阳市024南京市025乌鲁木齐市09915自适应字典n有许多场合，开始时不知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。n字典编码的思路：根据数据本身包含有重复代码的特性n例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮n如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。n实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余。6自适应字典n开始njacob ziv / abraham lempeln1977 (lz77/l

4、z1), 1978 (lz78/lz2)n1984 terry welch (lzw)nlz77 vs. lz78n两种不同的方法n有很多变种n是很多主流压缩的基础7lz77n基本方法：字典为先前已编码序列的一部分n搜索缓冲区为当前字典，通常为几千字节n机制：滑动窗口n搜索缓冲区( search buffer)、前向（look ahead）缓冲区、搜索指针(search pointer)n目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串，并对其进行编码n基本原理：如果某些模式在局部重复出现，能得到更有效的表示8lz77 (2)n(o)ffset = search ptr - mat

5、ch ptr = 7n(l)ength = 连续匹配的字符数 = 4n(c)odeword = c(r)n编码n = nif |search buff| = s, |a| = a, s + |la buff| = wn定长码：log2s + log2w + log2asearch pointer9lz77 编码举例n序列ncabracadabrarrarradnw = 13, s = 7n|cabraca|dabrar|rarradn对d，没有匹配的字符串n发送 (可以做得更好?)n |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|

6、abrarr|rarrad |abracad|abrarr|rarradn发送 10lz77 编码举例 (2)n|cadabrar|rarrad|cadabrar|rarrad|cadabrar|rarrad|n发送 n可以做得更好?n发送 !n总结：三种情况n没有匹配n匹配n匹配串超过了搜索缓冲区11lz77 解码举例 n输入n n输出ncabracan解码：n增加一个 d: c|abracad|n解码： n从第一个a开始，拷贝4个字母，解码c(r)cabrac|adabrar|n解码： n从第一个r开始，拷贝3个字母 cabracada|brarrar|n再拷贝2个字母cabracadab

7、r|arrarar|n解码c(d)：cabracadabrarrarard12lz77编码小结n使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；n随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。nlz77解码器比编码器简单得多（非对称压缩）n维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串及第3个字段的字符写入输出流，同时移进缓冲区n在如文件压缩（一次压缩，多次还原）的场合很有用13lz77的变种n迄

8、今为止n自适应模型，没有先验知识n渐近 接近知道信源统计知识的情况n但是，局部性起到了很大作用n改进n变长编码noffset: 各数值基本均匀分布，一般用定长码nlength: 可用huffman码/golomb码/exp-golomb码npkzip, zip, lharcm ong, gzip, arjn可变缓冲区大小n需设计较完善的数据结构来实现对大缓冲区的快速搜索nlzss：搜索缓冲区（字典）用对分查找树保持，前向缓冲区用循环队列表示n取消 nlzss：只需增加1一个标记位，用于指示是否为单字符14lz78nlz77假设模式满足局部性nlz78:n没有搜索缓冲区代之以显式的字典n编码器/

9、解码器必须同步建立字典n 如没有匹配，将字典原有词条+当前没有匹配的字符 字典的新词条n编码：ni = 字典索引n同lz77，i=0 表示在字典中没有找到匹配的词条nc = 下一字符的码字15lz78举例索引条目字典：输入：wabbawabbawabbawabbawoowoowoo输出：16lz78举例 (2)索引条目字典：输入： wabbawabbawabbawabbawoowoowoo输出：17lz78举例 (3)索引条目1w字典：输入： -abbawabbawabbawabbawoowoowoo输出：18lz78举例 (4)索引条目1w2a字典：输入： -bbawabbawabbawab

10、bawoowoowoo输出：19lz78举例 (5)索引条目1w2a3b字典：输入： -bawabbawabbawabbawoowoowoo输出：20lz78举例 (6)索引条目1w2a3b4ba字典：输入： -wabbawabbawabbawoowoowoo输出：21lz78举例 (7)索引条目1w2a3b4ba5字典：输入： -wabbawabbawabbawoowoowoo输出：22lz78举例 (8)索引条目1w2a3b4ba56wa字典：输入： -bbawabbawabbawoowoowoo输出：23lz78举例 (9)索引条目1w2a3b4ba56wa7bb字典：输入： -awab

11、bawabbawoowoowoo输出：24lz78举例 (10)索引条目1w2a3b4ba56wa7bb8a字典：输入： -wabbawabbawoowoowoo输出：25lz78举例 (11)索引条目1w2a3b4ba56wa7bb8a9wab字典：输入： -bawabbawoowoowoo输出：26lz78举例 (12)索引条目1w2a3b4ba56wa7bb8a9wab10ba字典：输入： -wabbawoowoowoo输出：27lz78举例 (13)字典：输入： -awoowoowoo输出：11wabb索引条目1w2a3b4ba56wa7bb8a9wab10ba28lz78举例 (14

12、)字典：输入： -oowoowoo输出：11wabb12aw索引条目1w2a3b4ba56wa7bb8a9wab10ba29lz78举例 (15)字典：输入： -owoowoo输出：11wabb12aw13o索引条目1w2a3b4ba56wa7bb8a9wab10ba30lz78举例 (16)字典：输入： -woowoo输出：11wabb12aw13o14o索引条目1w2a3b4ba56wa7bb8a9wab10ba31lz78举例 (17)字典：输入： -owoo输出：11wabb12aw13o14o15wo索引条目1w2a3b4ba56wa7bb8a9wab10ba32lz78举例 (18

13、)字典：输入： -oo输出：11wabb12aw13o14o15wo16ow索引条目1w2a3b4ba56wa7bb8a9wab10ba33lz78n观察：如果继续编码，字典将继续增长n实用的选择n停止增长字典n相当于从此成为一个静态字典策略n删除一些较早用过的项n如基于使用统计（但还没有好的算法决定哪些项该删）n将字典全部删除，从空字典开始重建字典n如果没有信源的特定知识，任何方法可能都不会工作得很好！34lz78的变种：lzwnterry welch (1984)n基本思想：n只对i编码，而不是编码 n算法：n/初始化字典为包含所有字母 seed dictionary with all a

14、lphabet letters, p = null while( !done)a = get_next_symbolif( p a) is in dictionary /在字典中，继续用更长的字符串匹配p = p aelsesend out index of p /不在字典中，输出已匹配部分，从a 重新开始p.a is added to dictionary p = aendwhile35lzw编码索引条目12a3b4o5w678910字典：输出：输入： wabbawabbawabbawabbawoowoowoop = 36lzw编码(2)索引条目12a3b4o5w678910字典：输出：输入

15、： wabbawabbawabbawabbawoowoowoop = w 37lzw编码(3)索引条目12a3b4o5w678910字典：输出：5 (w)输入： -abbawabbawabbawabbawoowoowoop = wa38lzw编码(4)索引条目12a3b4o5w6wa78910字典：输出：5 (w)2 (a)输入： -bbawabbawabbawabbawoowoowoop = ab39lzw编码(5)索引条目12a3b4o5w6wa7ab8910字典：输出：5 (w)2 (a)3 (b)输入： -bawabbawabbawabbawoowoowoop = bb40lzw编码(

16、6)索引条目12a3b4o5w6wa7ab8bb910字典：输出：5 (w)2 (a)3 (b)3 (b)输入： -awabbawabbawabbawoowoowoop = ba41lzw编码 (7)索引条目12a3b4o5w6wa7ab8bb9ba10字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)输入： -wabbawabbawabbawoowoowoop = a42lzw编码 (8)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()输入： -wabbawabbawabbawoowoowoo索引条目1

17、1121314151617181920p = w43lzw编码 (9)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()输入： -abbawabbawabbawoowoowoo索引条目11w121314151617181920p = wa44lzw编码 (10)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)输入： -bbawabbawabbawoowoowoo索引条目11w121314151617181920p = wab45l

18、zw编码 (11)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)输入： -bawabbawabbawoowoowoo索引条目11w12wab1314151617181920p = bb46lzw编码 (12)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)输入： -awabbawabbawoowoowoo索引条目11w12wab1314151617181920p = bba47lzw编码 (13)索引条

19、目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)输入： -wabbawabbawoowoowoo索引条目11w12wab13bba14151617181920p = a48lzw编码 (14)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)输入： -wabbawabbawoowoowoo索引条目11w12wab13bba14151617181920p = aw49lzw编码 (15)索引

20、条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)输入： -abbawabbawoowoowoo索引条目11w12wab13bba14aw151617181920p = wa50lzw编码 (16)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)输入： -bbawabbawoowoowoo索引条目11w12wab13bba14aw151617181920p = wab51lz

21、w编码 (17)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)输入： -bawabbawoowoowoo索引条目11w12wab13bba14aw151617181920p = wabb52lzw编码 (18)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)输入： -awabbawoowoowoo索引条目11w12wab13bba14a

22、w15wabb1617181920p = ba53lzw编码 (19)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)输入： -wabbawoowoowoo索引条目11w12wab13bba14aw15wabb1617181920p = ba54lzw编码 (20)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)输

23、入： -wabbawoowoowoo索引条目11w12wab13bba14aw15wabb16ba17181920p = w55lzw编码 (21)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)输入： -abbawoowoowoo索引条目11w12wab13bba14aw15wabb16ba17181920p = wa56lzw编码 (22)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3

24、 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)输入： -bbawoowoowoo索引条目11w12wab13bba14aw15wabb16ba17wa181920p = ab57lzw编码 (23)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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索引条目11w12wab13bba14aw15wabb16ba17wa181920p = abb58

25、lzw编码 (24)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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索引条目11w12wab13bba14aw15wabb16ba17wa18abb1920p = ba59lzw编码 (25)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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

26、)输入： -woowoowoo索引条目11w12wab13bba14aw15wabb16ba17wa18abb1920p = ba60lzw编码 (26)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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索引条目11w12wab13bba14aw15wabb16ba17wa18abb1920p = baw61lzw编码 (27)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输

27、出：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索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20p = wo5 (w)62lzw编码 (28)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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索引条目11w12

28、wab13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)索引条目2122232425262728293063lzw编码 (29)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = o5 (w)4 (o)4 (o)索引条目21oo222324

29、25262728293064lzw编码 (30)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = w5 (w)4 (o)4 (o)索引条目21oo22o232425262728293065lzw编码 (31)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a

30、)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)输入： -oowoo索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)4 (o)4 (o)11 (w)索引条目21oo22o232425262728293066lzw编码 (32)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (

31、ab)16 (ba)输入： -owoo索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)4 (o)11 (w)索引条目21oo22o23wo2425262728293067lzw编码 (33)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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)输入： -woo索引条目11w12wab13bba14aw15wabb16ba17wa18abb19

32、baw20wop = oo5 (w)4 (o)4 (o)11 (w)21 (oo)索引条目21oo22o23wo2425262728293068lzw编码 (34)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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)输入： -woo索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = w5 (w)4 (o)4 (o)11 (w)21 (oo)索引条目21oo22o23w

33、o24oo25262728293069lzw编码 (35)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：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)输入： -oo索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)4 (o)4 (o)11 (w)21 (oo)索引条目21oo22o23wo24oo25262728293070lzw编码 (36)索引条目12a3b4o5w6wa7ab8bb9b

34、a10a字典：输出：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)输入： -o索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = woo5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)索引条目21oo22o23wo24oo25 262728293071lzw编码 (eot)索引条目12a3b4o5w6wa7ab8bb9ba10a字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa

35、)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)输入： -索引条目11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = o5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)4 (o)索引条目21oo22o23wo24oo25 woo262728293072lzw解码索引条目12a3b4o5w678910字典：输入： 5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = 输出：73lzw解码 (2)索引条目12a3b4o5w678910字典

36、：输入： 5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = w 输出： w74lzw解码 (3)索引条目12a3b4o5w678910字典：输入： - 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 输出： wa75lzw解码 (4)索引条目12a3b4o5w6wa78910输入： - - 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ab 输出： wab字典：76lzw解码 (5)索引条目12a3b4o5w6wa7ab8910输入：

37、 - - - 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb 输出： wabb字典：77lzw解码 (6)索引条目12a3b4o5w6wa7ab8bb910输入： - - - - 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ba 输出： wabba字典：78lzw解码 (7)索引条目12a3b4o5w6wa7ab8bb9ba10 输入： - - - - - 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = a 输出： wabba字典：79lzw解码 (8)索引条目12

38、a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 输出： wabbawa索引条目11121314151617181920字典：80lzw解码 (9)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 输出： wabbawa索引条目11121314151617181920字典：81lzw解码 (10)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入

39、： - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wabb 输出： wabbawabb索引条目11121314151617181920字典：82lzw解码 (11)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb 输出： wabbawabb索引条目11121314151617181920字典：83lzw解码 (12)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - -

40、10 12 9 11 7 16 5 4 4 11 21 23 4p = bba 输出： wabbawabba索引条目1112wab1314151617181920字典：84lzw解码 (13)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = bba 输出： wabbawabba索引条目1112wab1314151617181920字典：85lzw解码 (14)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - 12 9 11 7

41、 16 5 4 4 11 21 23 4p = a 输出： wabbawabba索引条目1112wab13bba14151617181920字典：86lzw解码 (15)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = awab 输出： wabbawabbawab索引条目1112wab13bba14151617181920字典：87lzw解码 (16)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - - 9 11 7 16 5

42、 4 4 11 21 23 4p = wab 输出： wabbawabbawab索引条目1112wab13bba14aw151617181920字典：88lzw解码 (16)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wab 输出： wabbawabbawab索引条目1112wab13bba14aw151617181920字典：89lzw解码 (17)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - - 9 11 7 16

43、 5 4 4 11 21 23 4p = wab 输出： wabbawabbawab索引条目1112wab13bba14aw151617181920字典：90lzw解码 (18)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wabba 输出： wabbawabbawabba索引条目1112wab13bba14aw151617181920字典：91lzw解码 (19)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - - - 1

44、1 7 16 5 4 4 11 21 23 4p = ba 输出： wabbawabbawabba索引条目1112wab13bba14aw15wabb1617181920字典：92lzw解码 (20)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - - - - - - - - 11 7 16 5 4 4 11 21 23 4p = baw 输出： wabbawabbawabbaw索引条目1112wab13bba14aw15wabb1617181920字典：93lzw解码 (21)索引条目12a3b4o5w6wa7ab8bb9ba10a 输入： - - - - -

45、 - - - - - - - 7 16 5 4 4 11 21 23 4p = w 输出： wabbawabbawabbaw索引条目1112wab13bba14aw15wabb16ba17181920 字典：最后得到与编码器输入一致的字符串94lzw特殊情况n上述解码器n简单、有效，但是，有时会出错n不过可以修复n例：na = a, bn输入序列：abababab n开始字典索引条目1a2b95lzw特殊情况：编码索引条目1a2b字典：输出： 输入：abababababab p =96lzw特殊情况：编码(2)索引条目1a2b输出：输入： abababababab p = a字典：97lzw特

46、殊情况：编码(3)索引条目1a2b3输出：1 (a)输入： -bababababab p = ab字典：98lzw特殊情况：编码(4)索引条目1a2b3ab4输出：1 (a)2 (b)输入： -ababababab p = ba字典：99lzw特殊情况：编码 (5)索引条目1a2b3ab4ba输出：1 (a)2 (b)输入： -babababab p = ab字典：100lzw特殊情况：编码 (6)索引条目1a2b3ab4ba5输出：1 (a)2 (b)3 (ab)输入： -abababab p = aba字典：101lzw特殊情况：编码 (7)索引条目1a2b3ab4ba5aba输出：1 (

47、a)2 (b)3 (ab)输入： -bababab p = ab字典：102lzw特殊情况：编码 (8)索引条目1a2b3ab4ba5aba输出：1 (a)2 (b)3 (ab)输入： -ababab p = aba字典：103lzw特殊情况：编码 (9)索引条目1a2b3ab4ba5aba6abab输出：1 (a)2 (b)3 (ab)5 (aba)输入： -babab p = abab字典：104lzw特殊情况：解码索引条目1a2b输入： 1 2 3 5 p = 输出：字典：105lzw特殊情况：解码 (2)索引条目1a2b输入： 1 2 3 5 p = a 输出： a字典：索引在字典中存

48、在：输出索引对应的词条前缀+当前词条的第一个字符 字典的新词条106lzw特殊情况：解码 (3)索引条目1a2b3输入： - 2 3 5 p = ab 输出： ab字典：107lzw特殊情况：解码 (4)索引条目1a2b3ab4ba输入： - - 3 5 p = bab 输出： abab字典：108lzw特殊情况：解码 (5)索引条目1a2b3ab4ba输入： - - - 5 p = ab 输出： abab字典：109lzw特殊情况：解码 (6)索引条目1a2b3ab4ba输入： - - - 5 p = ab? 输出： abab?字典：110lzw特殊情况：解码 (7)n第5个词条应该以 ab

49、开始 需将其加到 p 并继续解码索引条目1a2b3ab4ba5ab输入： - - - 5 p = ab? 输出： abab?字典：111lzw特殊情况：解码 (8)索引条目1a2b3ab4ba5输入： - - - 5 p = abab? 输出： abab?字典：112lzw特殊情况：解码 (9)索引条目1a2b3ab4ba5输入： - - - 5 p = ababa 输出： abab?字典：113lzw特殊情况：解码 (10)索引条目1a2b3ab4ba5aba输入： - - - - p = aba 输出： abababa解码器必须用一个额外的句柄用于处理该情况n索引不在字典中：n前缀+前缀的

50、的第一个字符 字典的新词条n输出索引对应的词条字典：114lzw解码算法lzw译码算法可用伪码表示如下：ndictionaryj all n single-character, j =1，2，nn j n + 1ncw first code from codestreamncharstream dictionarycwnpw cwnwhile (cw next code word) != null)n if cw is in dictionaryn charstream dictionarycwn prefix dictionarypwn cw first character of dicti

51、onarycwn dictionaryj prefix.cwn j n + 1n pw cwn elsen prefix dictionarypwn cw first character of prefixn charstream prefix.cwn dictionaryj prefix.cwn pw cwn j n + 1115字典结构n字典越大，能存储更多的字符串，也就能匹配更长的字符串，但其代价是指针更长（标识需要的位数越多），搜索起来也更慢n对字典而言，最好的数据结构是树：trien 116字典结构n在编码时，编码器逐个输入字符并累积成字符串i（相当于伪代码中的prefix ）n只要

52、在字典中能找到变量i的字符串，编码器就不断地输入字符并将其串接到i中，直到某个输入字符x与i连接后使搜索失败（字符串ix不在字典中），然后将ix加到字典中。n添加到字典中去的每个字符串仅有效增加了一个新字符x，即对每个不止一个字符的字符串，字典中有一个比它只少一个字符的“母串”。117字典结构n用树trie表示时，树是动态建立的，且树中每个节点可能存在多个子节点。因此数据结构应该设计成一个节点可拥有任意个子节点，但无需为其预留空间：将树驻留在一个节点数组中，每个数据结构有两个字段：一个字符和指向母节点的指针n数据结构中没有指向子节点的指针，沿着树从一个节点到其子节点的操作可用一个散列过程实现，

53、该过程把指向节点的指针和子节点的字符散列以生成一个新指针，因此需添加一个新字段：散列索引118字典结构n实用中，每个节点有3个字段：n树用数组dict表示，数组下标用pointer表示，所以dictpointer表示一个节点ndictpointer.parentndictpointer.indexndictpointer.symbol母节点（parent）索引（index）字符（symbol）119字典结构n例：字符串“ababab” (a: 1 b: 2)nstep 0：将从3个位置开始的所有字典位置标记为“未使用”n step 1：将第一个字符a输入到变量i。 “a”的码字为1，因此i = 1。因为是第一个字符，编码器假定它已在字典中，故无需搜索nstep 2：将第二个字符b输入到j，所以j = 2。编码器在字典中搜索字符串ab，执行 pointer:=hash(i,j)，假设结果为5。因为位置5仍然是空的，字段dictpointer.index标记为“未使用”，因此串ab不在字典中，将其添加到字典中： ndictpointer.parent:=i;ndictpointer.index:=pointer;ndictpo