【教学课件】第五章字典编码.ppt

《【教学课件】第五章字典编码.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第五章字典编码.ppt（128页珍藏版）》请在三一办公上搜索。

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

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

3、它们的统计特性。字典编码的思路：根据数据本身包含有重复代码的特性例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余。,6,自适应字典,开始Jacob Ziv/Abraham Lempel1977(LZ77/LZ1),1978(LZ78/LZ2)1984 Terry Welch(LZW)LZ77 vs.LZ78两种不同的方法有很多变种是很多主流压缩的基础,7,LZ77,基本方法：字典为先前已编码序列的一部分搜索

4、缓冲区为当前字典，通常为几千字节机制：滑动窗口搜索缓冲区(Search buffer)、前向（look ahead）缓冲区、搜索指针(search pointer)目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串，并对其进行编码基本原理：如果某些模式在局部重复出现，能得到更有效的表示,8,LZ77(2),(o)ffset=search ptr-match ptr=7(l)ength=连续匹配的字符数=4(c)odeword=C(r)编码=If|search buff|=S,|A|=A,S+|LA buff|=W定长码：log2S+log2W+log2A,Search pointer

5、,9,LZ77 编码举例,序列cabracadabrarrarradW=13,S=7|cabraca|dabrar|rarrad对d，没有匹配的字符串发送(可以做得更好?)|abracad|abrarr|rarrad|abracad|abrarr|rarrad|abracad|abrarr|rarrad|abracad|abrarr|rarrad发送,10,LZ77 编码举例(2),|cadabrar|rarrad|cadabrar|rarrad|cadabrar|rarrad|发送 可以做得更好?发送!总结：三种情况没有匹配匹配匹配串超过了搜索缓冲区,11,LZ77 解码举例,输入 输出ca

6、braca解码：增加一个 d:c|abracad|解码：从第一个a开始，拷贝4个字母，解码C(r)cabrac|adabrar|解码：从第一个r开始，拷贝3个字母 cabracada|brarrar|再拷贝2个字母cabracadabr|arrarar|解码C(d)：cabracadabrarrarard,12,LZ77编码小结,使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串

7、。LZ77解码器比编码器简单得多（非对称压缩）维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串及第3个字段的字符写入输出流，同时移进缓冲区在如文件压缩（一次压缩，多次还原）的场合很有用,13,LZ77的变种,迄今为止自适应模型，没有先验知识渐近 接近知道信源统计知识的情况但是，局部性起到了很大作用改进变长编码offset:各数值基本均匀分布，一般用定长码length:可用Huffman码/Golomb码/Exp-Golomb码PKZip,Zip,Lharcm ONG,gzip,ARJ可变缓冲区大小需设计较完善的数据结构来实现对大缓冲区的快速搜索LZSS：搜索缓冲区（字典）

8、用对分查找树保持，前向缓冲区用循环队列表示取消 LZSS：只需增加1一个标记位，用于指示是否为单字符,14,LZ78,LZ77假设模式满足局部性LZ78:没有搜索缓冲区代之以显式的字典编码器/解码器必须同步建立字典 如没有匹配，将字典原有词条+当前没有匹配的字符 字典的新词条编码：i=字典索引同LZ77，i=0 表示在字典中没有找到匹配的词条c=下一字符的码字,15,LZ78举例,字典：,输入：wabbawabbawabbawabbawoowoowoo,输出：,16,LZ78举例(2),字典：,输入：wabbawabbawabbawabbawoowoowoo,输出：,17,LZ78举例(3),

9、字典：,输入：-abbawabbawabbawabbawoowoowoo,输出：,18,LZ78举例(4),字典：,输入：-bbawabbawabbawabbawoowoowoo,输出：,19,LZ78举例(5),字典：,输入：-bawabbawabbawabbawoowoowoo,输出：,20,LZ78举例(6),字典：,输入：-wabbawabbawabbawoowoowoo,输出：,21,LZ78举例(7),字典：,输入：-wabbawabbawabbawoowoowoo,输出：,22,LZ78举例(8),字典：,输入：-bbawabbawabbawoowoowoo,输出：,23,LZ7

10、8举例(9),字典：,输入：-awabbawabbawoowoowoo,输出：,24,LZ78举例(10),字典：,输入：-wabbawabbawoowoowoo,输出：,25,LZ78举例(11),字典：,输入：-bawabbawoowoowoo,输出：,26,LZ78举例(12),字典：,输入：-wabbawoowoowoo,输出：,27,LZ78举例(13),字典：,输入：-awoowoowoo,输出：,28,LZ78举例(14),字典：,输入：-oowoowoo,输出：,29,LZ78举例(15),字典：,输入：-owoowoo,输出：,30,LZ78举例(16),字典：,输入：-wo

11、owoo,输出：,31,LZ78举例(17),字典：,输入：-owoo,输出：,32,LZ78举例(18),字典：,输入：-oo,输出：,33,LZ78,观察：如果继续编码，字典将继续增长实用的选择停止增长字典相当于从此成为一个静态字典策略删除一些较早用过的项如基于使用统计（但还没有好的算法决定哪些项该删）将字典全部删除，从空字典开始重建字典如果没有信源的特定知识，任何方法可能都不会工作得很好！,34,LZ78的变种：LZW,Terry Welch(1984)基本思想：只对i编码，而不是编码 算法：/初始化字典为包含所有字母 Seed dictionary with all alphabet

12、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=aendwhile,35,LZW编码,字典：,输出：,输入：wabbawabbawabbawabbawoowoowoo,p=,36,LZW编码(2),字典：,输出：,输入：wabbawabbawabbawabbawoowoowoo,p=w,37,LZW编码(3),字典：,输

13、出：5(w),输入：-abbawabbawabbawabbawoowoowoo,p=wa,38,LZW编码(4),字典：,输出：5(w)2(a),输入：-bbawabbawabbawabbawoowoowoo,p=ab,39,LZW编码(5),字典：,输出：5(w)2(a)3(b),输入：-bawabbawabbawabbawoowoowoo,p=bb,40,LZW编码(6),字典：,输出：5(w)2(a)3(b)3(b),输入：-awabbawabbawabbawoowoowoo,p=ba,41,LZW编码(7),字典：,输出：5(w)2(a)3(b)3(b)2(a),输入：-wabbawa

14、bbawabbawoowoowoo,p=a,42,LZW编码(8),字典：,输出：5(w)2(a)3(b)3(b)2(a)1(),输入：-wabbawabbawabbawoowoowoo,p=w,43,LZW编码(9),字典：,输出：5(w)2(a)3(b)3(b)2(a)1(),输入：-abbawabbawabbawoowoowoo,p=wa,44,LZW编码(10),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa),输入：-bbawabbawabbawoowoowoo,p=wab,45,LZW编码(11),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6

15、(wa),输入：-bawabbawabbawoowoowoo,p=bb,46,LZW编码(12),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb),输入：-awabbawabbawoowoowoo,p=bba,47,LZW编码(13),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb),输入：-wabbawabbawoowoowoo,p=a,48,LZW编码(14),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a),输入：-wabbawabbawoowoowoo,p=aw,49,LZW编码(

16、15),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a),输入：-abbawabbawoowoowoo,p=wa,50,LZW编码(16),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a),输入：-bbawabbawoowoowoo,p=wab,51,LZW编码(17),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab),输入：-bawabbawoowoowoo,p=wabb,52,LZW编码(18),字典：,输出：5(w)2(a)3(b)3(b)2(a)1

17、()6(wa)8(bb)10(a)12(wab),输入：-awabbawoowoowoo,p=ba,53,LZW编码(19),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba),输入：-wabbawoowoowoo,p=ba,54,LZW编码(20),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba),输入：-wabbawoowoowoo,p=w,55,LZW编码(21),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(

18、wab)9(ba)11(w),输入：-abbawoowoowoo,p=wa,56,LZW编码(22),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w),输入：-bbawoowoowoo,p=ab,57,LZW编码(23),字典：,输出：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,p=abb,58,LZW编码(24),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(

19、wab)9(ba)11(w)7(ab),输入：-awoowoowoo,p=ba,59,LZW编码(25),字典：,输出：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,p=ba,60,LZW编码(26),字典：,输出：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,p=baw,61,LZW编码(27),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)

20、10(a)12(wab)9(ba)11(w)7(ab)16(ba),输入：-oowoowoo,p=wo,5(w),62,LZW编码(28),字典：,输出：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,p=oo,5(w)4(o),63,LZW编码(29),字典：,输出：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,p=o,5(w)4(o)4(o),64,LZW编码(30),字典

21、：,输出：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,p=w,5(w)4(o)4(o),65,LZW编码(31),字典：,输出：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,p=wo,5(w)4(o)4(o)11(w),66,LZW编码(32),字典：,输出：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)

22、16(ba),输入：-owoo,p=oo,5(w)4(o)4(o)11(w),67,LZW编码(33),字典：,输出：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,p=oo,5(w)4(o)4(o)11(w)21(oo),68,LZW编码(34),字典：,输出：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,p=w,5(w)4(o)4(o)11(w)21(oo),69,LZW编码(35),字

23、典：,输出：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,p=wo,5(w)4(o)4(o)11(w)21(oo),70,LZW编码(36),字典：,输出：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,p=woo,5(w)4(o)4(o)11(w)21(oo)23(wo),71,LZW编码(EOT),字典：,输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(

24、wab)9(ba)11(w)7(ab)16(ba),输入：-,p=o,5(w)4(o)4(o)11(w)21(oo)23(wo)4(o),72,LZW解码,字典：,输入：5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=,输出：,73,LZW解码(2),字典：,输入：5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=w,输出：w,74,LZW解码(3),字典：,输入：-2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=wa,输出：wa,75,L

25、ZW解码(4),输入：-3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=ab,输出：wab,字典：,76,LZW解码(5),输入：-3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=bb,输出：wabb,字典：,77,LZW解码(6),输入：-2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=ba,输出：wabba,字典：,78,LZW解码(7),输入：-1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=a,输出：wabba,字典：,79,L

26、ZW解码(8),输入：-6 8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=wa,输出：wabbawa,字典：,80,LZW解码(9),输入：-8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=wa,输出：wabbawa,字典：,81,LZW解码(10),输入：-8 10 12 9 11 7 16 5 4 4 11 21 23 4,p=wabb,输出：wabbawabb,字典：,82,LZW解码(11),输入：-10 12 9 11 7 16 5 4 4 11 21 23 4,p=bb,输出：wabbawabb,字典：,83,LZW解码(12)

27、,输入：-10 12 9 11 7 16 5 4 4 11 21 23 4,p=bba,输出：wabbawabba,字典：,84,LZW解码(13),输入：-12 9 11 7 16 5 4 4 11 21 23 4,p=bba,输出：wabbawabba,字典：,85,LZW解码(14),输入：-12 9 11 7 16 5 4 4 11 21 23 4,p=a,输出：wabbawabba,字典：,86,LZW解码(15),输入：-12 9 11 7 16 5 4 4 11 21 23 4,p=awab,输出：wabbawabbawab,字典：,87,LZW解码(16),输入：-9 11 7

28、 16 5 4 4 11 21 23 4,p=wab,输出：wabbawabbawab,字典：,88,LZW解码(16),输入：-9 11 7 16 5 4 4 11 21 23 4,p=wab,输出：wabbawabbawab,字典：,89,LZW解码(17),输入：-9 11 7 16 5 4 4 11 21 23 4,p=wab,输出：wabbawabbawab,字典：,90,LZW解码(18),输入：-9 11 7 16 5 4 4 11 21 23 4,p=wabba,输出：wabbawabbawabba,字典：,91,LZW解码(19),输入：-11 7 16 5 4 4 11 2

29、1 23 4,p=ba,输出：wabbawabbawabba,字典：,92,LZW解码(20),输入：-11 7 16 5 4 4 11 21 23 4,p=baw,输出：wabbawabbawabbaw,字典：,93,LZW解码(21),输入：-7 16 5 4 4 11 21 23 4,p=w,输出：wabbawabbawabbaw,字典：,最后得到与编码器输入一致的字符串,94,LZW特殊情况,上述解码器简单、有效，但是，有时会出错不过可以修复例：A=a,b输入序列：abababab 开始字典,95,LZW特殊情况：编码,字典：,输出：,输入：abababababab,p=,96,LZW

30、特殊情况：编码(2),输出：,输入：abababababab,p=a,字典：,97,LZW特殊情况：编码(3),输出：1(a),输入：-bababababab,p=ab,字典：,98,LZW特殊情况：编码(4),输出：1(a)2(b),输入：-ababababab,p=ba,字典：,99,LZW特殊情况：编码(5),输出：1(a)2(b),输入：-babababab,p=ab,字典：,100,LZW特殊情况：编码(6),输出：1(a)2(b)3(ab),输入：-abababab,p=aba,字典：,101,LZW特殊情况：编码(7),输出：1(a)2(b)3(ab),输入：-bababab,p

31、=ab,字典：,102,LZW特殊情况：编码(8),输出：1(a)2(b)3(ab),输入：-ababab,p=aba,字典：,103,LZW特殊情况：编码(9),输出：1(a)2(b)3(ab)5(aba),输入：-babab,p=abab,字典：,104,LZW特殊情况：解码,输入：1 2 3 5,p=,输出：,字典：,105,LZW特殊情况：解码(2),输入：1 2 3 5,p=a,输出：a,字典：,索引在字典中存在：输出索引对应的词条前缀+当前词条的第一个字符 字典的新词条,106,LZW特殊情况：解码(3),输入：-2 3 5,p=ab,输出：ab,字典：,107,LZW特殊情况：解

32、码(4),输入：-3 5,p=bab,输出：abab,字典：,108,LZW特殊情况：解码(5),输入：-5,p=ab,输出：abab,字典：,109,LZW特殊情况：解码(6),输入：-5,p=ab?,输出：abab?,字典：,110,LZW特殊情况：解码(7),第5个词条应该以 ab开始 需将其加到 p 并继续解码,输入：-5,p=ab?,输出：abab?,字典：,111,LZW特殊情况：解码(8),输入：-5,p=abab?,输出：abab?,字典：,112,LZW特殊情况：解码(9),输入：-5,p=ababa,输出：abab?,字典：,113,LZW特殊情况：解码(10),输入：-,

33、p=aba,输出：abababa,解码器必须用一个额外的句柄用于处理该情况索引不在字典中：前缀+前缀的的第一个字符 字典的新词条输出索引对应的词条,字典：,114,LZW解码算法,LZW译码算法可用伪码表示如下：Dictionaryj all n single-character,j=1，2，n j n+1cW first code from CodestreamCharstream DictionarycWpW cWWhile(cW next Code word)!=NULL)If cW is in Dictionary Charstream DictionarycW Prefix Dict

34、ionarypW cW first Character of DictionarycW Dictionaryj Prefix.cW j n+1 pW cW else Prefix DictionarypW cW first Character of Prefix Charstream Prefix.cW Dictionaryj Prefix.cW pW cW j n+1,115,字典结构,字典越大，能存储更多的字符串，也就能匹配更长的字符串，但其代价是指针更长（标识需要的位数越多），搜索起来也更慢对字典而言，最好的数据结构是树：trie,116,字典结构,在编码时，编码器逐个输入字符并累积成字

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

36、节点到其子节点的操作可用一个散列过程实现，该过程把指向节点的指针和子节点的字符散列以生成一个新指针，因此需添加一个新字段：散列索引,118,字典结构,实用中，每个节点有3个字段：树用数组dict表示，数组下标用pointer表示，所以dictpointer表示一个节点dictpointer.parentdictpointer.indexdictpointer.symbol,119,字典结构,例：字符串“ababab”(a:1 b:2)Step 0：将从3个位置开始的所有字典位置标记为“未使用”Step 1：将第一个字符a输入到变量I。“a”的码字为1，因此I=1。因为是第一个字符，编码器假定它

37、已在字典中，故无需搜索Step 2：将第二个字符b输入到J，所以J=2。编码器在字典中搜索字符串ab，执行 pointer:=hash(I,J)，假设结果为5。因为位置5仍然是空的，字段dictpointer.index标记为“未使用”，因此串ab不在字典中，将其添加到字典中：dictpointer.parent:=I;dictpointer.index:=pointer;dictpointer.symbol:=J;由于pointer=5，将J送入I，因此I=2。,120,字典结构,Step 3：将第3个字符a输入到J，所以J=1。编码器在字典中搜索字符串ba，执行 pointer:=hash

38、(I,J)，假设结果为8。因为位置8仍然是空的，字段dictpointer.index标记为“未使用”，因此串ba不在字典中，将其添加到字典中：dictpointer.parent:=I;dictpointer.index:=pointer;dictpointer.symbol:=J;由于pointer=8，将J送入I，因此I=1。Step 4：将第4个字符b输入到J，这时J=2。编码器在字典中搜索字符串ab，执行 pointer:=hash(I,J)，由步骤2可知该结果为5。字段dictpointer.index中含有5，因此字符串ab在字典中，将指针的值送入I，因此I=5。,121,字典结

39、构,Step 5：将第5个字符a输入到J，这时J=1。编码器在字典中搜索字符串aba，执行 pointer:=hash(I,J)，假定该值为8。在字段dictpointer.index中含有8，但dictpointer.parent为2，而非预期的5，因此散列函数知道这是一个冲突且字符串aba不在字典第8项中。将指针+1，直到找到一个index=8且parent=5的词条或找到一个未使用的词条为止。前一种情况字符串aba在字典中，可以将其指针送入I；而后一种情况，aba不在字典中，编码器将其保存在所指的词条中，并将J送入I。,122,字典结构,LZW解码器所用的字典数组简单且无需散列解码器首先

40、将数组的前n个位置初始化为单个字符（如n=256），然后从输入流中读入一个码字，用每个指针来定位字典中的一个字符第一步：读入第一个指针，用它检索字典的第I项，并把找到的字符I写入解码器输出流中。需要将Ix存入字典，但字符x此时仍未知，它将是下一个从字典中取出的串的首字符此后的每一步中，解码器输入下一个指针，用它从字典中取出下一个字符串J并记录到解码器输出流中。假设指针为8，则解码器检查dict8.index字段，如果它也是8，那么节点就是所要找的，否则解码器检查相继的数组位置，直到找到正确的节点,123,字典结构,一旦找到了所要的树节点，就利用parent字段返回到树的上层，并按相反顺序取出字

41、符串中的单个字符，再将江这些字符按正常顺序置于J中。解码器把第一个字符x从字符串J中分离出来，并将字符串Ix存入下一个可用的数组单元中（字符串I是前面找到的，所以只需添加一个带有字符x的节点），然后解码器将J送入I，继续下一步解码通过parent字段追踪，实现对树的上行，无需散列函数,124,应用：compress,LZW的早期实现自适应字典开始字典有512词条（9比特码字）当字典填满时，字典大小翻倍（码字长度增加1比特）最大码字长度bmax=16当字典达到2bmax 个词条变成静态字典编码器如果压缩率低于一个阈值，则重新初始化字典,125,应用：GIF,采用LZW机制，类似于 compres

42、s:GIF文件定义了一个编码大小(Clear Code)，b 比特/像素 2b 个clear codes字典填满时，字典大小翻倍（码字长度增加1比特）字典最大大小=4096 个词条（12比特）对计算机合成图像和颜色小于256色的自然图像编码比较有效，而对照片类的自然图像编码效率不高,126,GIF 的性能,127,总结,字典编码技术对文本、通讯协议等信源效率高静态字典技术适合已知数据领域自适应技术LZ77：假设模式在局部重复出现LZ78/LZW：不限于局部模式，从已观测到的信源动态构造字典实际应用GIF,zip，png,pdf,v.42,128,作业,作业：Sayood 3rd,pp.139-140 7,8下节课内容：第8章：有损压缩的数学基础,