《五章字典编码.ppt》由会员分享，可在线阅读，更多相关《五章字典编码.ppt（128页珍藏版）》请在三一文库上搜索。
1、1,第五章 字典编码,迄今为止，我们大多假设符号是独立的 但这对许多常见数据类型来说是不对的 如：文本、图像和源代码文件 基本思想 标识经常出现的符号模式保存于字典中 对这些常出现的模式采用更有效的编码方式用其在字典中的索引作为码字 而对其它部分采用缺省（不太有效）的编码方式 以期总的编码效率更高 注意 这对如文本这样的信源是合理的 显然对（接近）随机数据不会有效,2,例,考虑某英文文本信源 26 字母和6个标点符号 单字符，定长码 5 比特/字符 4字符模式，定长码 20比特/模式 (324 = 220 = 1,048,576) 假设为非均匀分布 字典：256个最常出现的模式，每个用8比特编
2、码 对其它模式用20比特编码 再增加1比特用于指示是上述两种情况中的哪种,3,例 (2),若用p 表示使用字典的概率，则比特率为 R = 9p + 21(1-p) = 21 - 12p 压缩 21 - 12p p 0.084 还不太坏 在等概率假设下，p = 0.00025 p越大，性能越好 选择最可能出现的模式存于字典中 为了达到好的性能，需要知道信源的结构信息 有足够的先验信息， 静态字典 否则，在编码过程中获得信源的知识 自适应字典,4,静态字典,静态字典 对信源的结构有足够的先验知识时，利用先验知识构造字典 对特定应用特别有效 只对针对其设计的特定应用和数据有效 例：电话号码的区号 例
3、：学校的学生信息表,5,自适应字典,有许多场合，开始时不知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。 字典编码的思路：根据数据本身包含有重复代码的特性 例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮 如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。 实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余。,6,自适应字典,开始 Jacob Ziv / Abraham Lempel 1977 (LZ77/LZ1), 1978 (LZ78/LZ2) 1984 Terry Welch (LZW
4、) LZ77 vs. LZ78 两种不同的方法 有很多变种 是很多主流压缩的基础,7,LZ77,基本方法：字典为先前已编码序列的一部分 搜索缓冲区为当前字典，通常为几千字节 机制：滑动窗口 搜索缓冲区( Search buffer)、前向（look ahead）缓冲区、搜索指针(search pointer) 目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串，并对其进行编码 基本原理：如果某些模式在局部重复出现，能得到更有效的表示,8,LZ77 (2),(o)ffset = search ptr - match ptr = 7 (l)ength = 连续匹配的字符数 = 4 (c)
5、odeword = C(r) 编码 = If |search buff| = S, |A| = A, S + |LA buff| = W 定长码：log2S + log2W + log2A,Search pointer,9,LZ77 编码举例,序列 cabracadabrarrarrad W = 13, S = 7 |cabraca|dabrar|rarrad 对d，没有匹配的字符串 发送 (可以做得更好?) |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad 发
6、送 ,10,LZ77 编码举例 (2),|cadabrar|rarrad| |cadabrar|rarrad| |cadabrar|rarrad| 发送 可以做得更好? 发送 ! 总结：三种情况 没有匹配 匹配 匹配串超过了搜索缓冲区,11,LZ77 解码举例,输入 输出 cabraca 解码： 增加一个 d: c|abracad| 解码： 从第一个a开始，拷贝4个字母，解码C(r) cabrac|adabrar| 解码： 从第一个r开始，拷贝3个字母 cabracada|brarrar| 再拷贝2个字母 cabracadabr|arrarar| 解码C(d)：cabracadabrarrar
7、ard,12,LZ77编码小结,使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率； 随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。 LZ77解码器比编码器简单得多（非对称压缩） 维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串及第3个字段的字符写入输出流，同时移进缓冲区 在如文件压缩（一次压缩，多次还原）的场合很有用,13,LZ77的变种,迄今为止 自适应模型，没有先验知识 渐近 接近知道信源统计知识
8、的情况 但是，局部性起到了很大作用 改进 变长编码 offset: 各数值基本均匀分布，一般用定长码 length: 可用Huffman码/Golomb码/Exp-Golomb码 PKZip, Zip, Lharcm ONG, gzip, ARJ 可变缓冲区大小 需设计较完善的数据结构来实现对大缓冲区的快速搜索 LZSS：搜索缓冲区（字典）用对分查找树保持，前向缓冲区用循环队列表示 取消 LZSS：只需增加1一个标记位，用于指示是否为单字符,14,LZ78,LZ77假设模式满足局部性 LZ78: 没有搜索缓冲区代之以显式的字典 编码器/解码器必须同步建立字典 如没有匹配，将字典原有词条+当前没
9、有匹配的字符 字典的新词条 编码： i = 字典索引 同LZ77，i=0 表示在字典中没有找到匹配的词条 c = 下一字符的码字,15,LZ78举例,字典：,输入：wabbawabbawabbawabbawoowoowoo,输出：,16,LZ78举例 (2),字典：,输入： wabbawabbawabbawabbawoowoowoo,输出： ,17,LZ78举例 (3),字典：,输入： -abbawabbawabbawabbawoowoowoo,输出： ,18,LZ78举例 (4),字典：,输入： -bbawabbawabbawabbawoowoowoo,输出： ,19,LZ78举例 (5),
10、字典：,输入： -bawabbawabbawabbawoowoowoo,输出： ,20,LZ78举例 (6),字典：,输入： -wabbawabbawabbawoowoowoo,输出： ,21,LZ78举例 (7),字典：,输入： -wabbawabbawabbawoowoowoo,输出： ,22,LZ78举例 (8),字典：,输入： -bbawabbawabbawoowoowoo,输出： ,23,LZ78举例 (9),字典：,输入： -awabbawabbawoowoowoo,输出： ,24,LZ78举例 (10),字典：,输入： -wabbawabbawoowoowoo,输出： ,25,L
11、Z78举例 (11),字典：,输入： -bawabbawoowoowoo,输出： ,26,LZ78举例 (12),字典：,输入： -wabbawoowoowoo,输出： ,27,LZ78举例 (13),字典：,输入： -awoowoowoo,输出： ,28,LZ78举例 (14),字典：,输入： -oowoowoo,输出： ,29,LZ78举例 (15),字典：,输入： -owoowoo,输出： ,30,LZ78举例 (16),字典：,输入： -woowoo,输出： ,31,LZ78举例 (17),字典：,输入： -owoo,输出： ,32,LZ78举例 (18),字典：,输入： -oo,输出
12、： ,33,LZ78,观察：如果继续编码，字典将继续增长 实用的选择 停止增长字典 相当于从此成为一个静态字典策略 删除一些较早用过的项 如基于使用统计（但还没有好的算法决定哪些项该删） 将字典全部删除，从空字典开始重建字典 如果没有信源的特定知识，任何方法可能都不会工作得很好！,34,LZ78的变种：LZW,Terry Welch (1984) 基本思想： 只对i编码，而不是编码 算法： /初始化字典为包含所有字母 Seed dictionary with all alphabet letters, p = null while( !done) a = get_next_symbol if(
13、 p a) is in dictionary /在字典中，继续用更长的字符串匹配 p = p a else send out index of p /不在字典中，输出已匹配部分，从a 重新开始 p.a is added to dictionary p = a endwhile,35,LZW编码,字典：,输出：,输入： wabbawabbawabbawabbawoowoowoo,p =,36,LZW编码(2),字典：,输出：,输入： wabbawabbawabbawabbawoowoowoo,p = w,37,LZW编码(3),字典：,输出： 5 (w),输入： -abbawabbawabbaw
14、abbawoowoowoo,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 (
15、a),输入： -wabbawabbawabbawoowoowoo,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),输入： -bbawabba
16、wabbawoowoowoo,p = wab,45,LZW编码 (11),字典：,输出： 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (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),输入：
17、 -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编码 (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
18、 () 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 () 6 (wa) 8 (bb) 10 (a) 12 (wab),输入： -awabbawoowoowoo,p = ba,53,LZW编码 (1
19、9),字典：,输出： 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)
20、 10 (a) 12 (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),输入： -bawo
21、owoowoo,p = abb,58,LZW编码 (24),字典：,输出： 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,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
22、 (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) 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
23、 (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),字典：,输出： 5 (w) 2 (a) 3 (b) 3
24、 (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
25、(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,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编
26、码 (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),字典：,输出： 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)
27、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 (wab) 9 (ba) 11 (w) 7 (ab
28、) 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 = w
29、a,输出： wa,75,LZW解码 (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
30、10 12 9 11 7 16 5 4 4 11 21 23 4,p = a,输出： wabba,字典：,79,LZW解码 (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
31、= wabb,输出： wabbawabb,字典：,82,LZW解码 (11),输入： - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4,p = bb,输出： wabbawabb,字典：,83,LZW解码 (12),输入： - - - - - - - - 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,
32、字典：,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 16 5 4 4 11 21 23 4,p = wab,输出： wabbawabbawab,字典：,88,LZW解码 (16)
33、,输入： - - - - - - - - - - 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),输入： - - -
34、- - - - - - - - 11 7 16 5 4 4 11 21 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特殊情况,上述解码
35、器 简单、有效，但是，有时会出错 不过可以修复 例： A = a, b 输入序列：abababab 开始字典,95,LZW特殊情况：编码,字典：,输出：,输入：abababababab ,p =,96,LZW特殊情况：编码(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),输入
36、： -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 = 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,字
37、典：,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特殊情况：解码 (4),输入： - - 3 5 ,p = bab,输出： abab,字典：,108,LZW特殊情况：解码 (5),输入： - - - 5 ,p = ab,输出： abab,字典：,109,LZW特殊情况：解
38、码 (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),输入： - - - - ,p = aba,输出： abababa,解码器必须用一个额外的句
39、柄用于处理该情况 索引不在字典中： 前缀+前缀的的第一个字符 字典的新词条 输出索引对应的词条,字典：,114,LZW解码算法,LZW译码算法可用伪码表示如下： Dictionaryj all n single-character, j =1，2，n j n + 1 cW first code from Codestream Charstream DictionarycW pW cW While (cW next Code word) != NULL) If cW is in Dictionary Charstream DictionarycW Prefix DictionarypW cW f
40、irst 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,字典结构,在编码时，编码器逐个输入字符并累积成字符串I（相当于伪
41、代码中的Prefix ） 只要在字典中能找到变量I的字符串，编码器就不断地输入字符并将其串接到I中，直到某个输入字符x与I连接后使搜索失败（字符串Ix不在字典中），然后将Ix加到字典中。 添加到字典中去的每个字符串仅有效增加了一个新字符x，即对每个不止一个字符的字符串，字典中有一个比它只少一个字符的“母串”。,117,字典结构,用树trie表示时，树是动态建立的，且树中每个节点可能存在多个子节点。因此数据结构应该设计成一个节点可拥有任意个子节点，但无需为其预留空间：将树驻留在一个节点数组中，每个数据结构有两个字段：一个字符和指向母节点的指针 数据结构中没有指向子节点的指针，沿着树从一个节点到其
42、子节点的操作可用一个散列过程实现，该过程把指向节点的指针和子节点的字符散列以生成一个新指针，因此需添加一个新字段：散列索引,118,字典结构,实用中，每个节点有3个字段： 树用数组dict表示，数组下标用pointer表示，所以dictpointer表示一个节点 dictpointer.parent dictpointer.index dictpointer.symbol,119,字典结构,例：字符串“ababab” (a: 1 b: 2) Step 0：将从3个位置开始的所有字典位置标记为“未使用” Step 1：将第一个字符a输入到变量I。 “a”的码字为1，因此I = 1。因为是第一个字符，编码器假定它已在字典中，故无需搜索 Step 2：将第二个字符b输入到J，所以J = 2。编码器在字典中搜索字符串ab，执行 pointer:=hash(I,J)，假设结果为5。因为位置5仍然是空的，字段dictpointer.index标记为“未使用”，因此串ab不在字典中，将其添加到字典中： dictpointer.parent:=I; dict