第五章字典编码

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、息表5自适应字典n有许多场合，开始时不知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。n字典编码的思路：根据数据本身包含有重复代码的特性n例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮n如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。n实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余。6自适应字典n开始nJacob Ziv / Abraham Lempeln1977 (LZ77/LZ1), 1978 (LZ78/LZ2)n1984 Terry Welch (LZW)nLZ77 vs.

4、LZ78n两种不同的方法n有很多变种n是很多主流压缩的基础7LZ77n基本方法：字典为先前已编码序列的一部分n搜索缓冲区为当前字典，通常为几千字节n机制：滑动窗口n搜索缓冲区( Search buffer)、前向（look ahead）缓冲区、搜索指针(search pointer)n目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串，并对其进行编码n基本原理：如果某些模式在局部重复出现，能得到更有效的表示8LZ77 (2)n(o)ffset = search ptr - match ptr = 7n(l)ength = 连续匹配的字符数 = 4n(c)odeword = C(r)n

5、编码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|abrarr|rarrad |abracad|abrarr|rarradn发送 10LZ77 编码举例 (

6、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个字母cabracadabr|arrarar|n解码C(d)：cabracadabrarrarard12LZ77编码小结n使用固定大

7、小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；n随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。nLZ77解码器比编码器简单得多（非对称压缩）n维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串及第3个字段的字符写入输出流，同时移进缓冲区n在如文件压缩（一次压缩，多次还原）的场合很有用13LZ77的变种n迄今为止n自适应模型，没有先验知识n渐近 接近知道信源统计知识的情况n但是，局部性起到了很大作用n改进n变长

8、编码noffset: 各数值基本均匀分布，一般用定长码nlength: 可用Huffman码/Golomb码/Exp-Golomb码nPKZip, Zip, Lharcm ONG, gzip, ARJn可变缓冲区大小n需设计较完善的数据结构来实现对大缓冲区的快速搜索nLZSS：搜索缓冲区（字典）用对分查找树保持，前向缓冲区用循环队列表示n取消 nLZSS：只需增加1一个标记位，用于指示是否为单字符14LZ78nLZ77假设模式满足局部性nLZ78:n没有搜索缓冲区代之以显式的字典n编码器/解码器必须同步建立字典n 如没有匹配，将字典原有词条+当前没有匹配的字符 字典的新词条n编码：ni = 字

9、典索引n同LZ77，i=0 表示在字典中没有找到匹配的词条nc = 下一字符的码字15LZ78举例字典：输入：wabbawabbawabbawabbawoowoowoo输出：16LZ78举例 (2)字典：输入： wabbawabbawabbawabbawoowoowoo输出：17LZ78举例 (3)字典：输入： -abbawabbawabbawabbawoowoowoo输出：18LZ78举例 (4)字典：输入： -bbawabbawabbawabbawoowoowoo输出：19LZ78举例 (5)字典：输入： -bawabbawabbawabbawoowoowoo输出：20LZ78举例 (6)

10、字典：输入： -wabbawabbawabbawoowoowoo输出：21LZ78举例 (7)字典：输入： -wabbawabbawabbawoowoowoo输出：22LZ78举例 (8)字典：输入： -bbawabbawabbawoowoowoo输出：23LZ78举例 (9)字典：输入： -awabbawabbawoowoowoo输出：24LZ78举例 (10)字典：输入： -wabbawabbawoowoowoo输出：25LZ78举例 (11)字典：输入： -bawabbawoowoowoo输出：26LZ78举例 (12)字典：输入： -wabbawoowoowoo输出：27LZ78举例

11、(13)字典：输入： -awoowoowoo输出：28LZ78举例 (14)字典：输入： -oowoowoo输出：29LZ78举例 (15)字典：输入： -owoowoo输出：30LZ78举例 (16)字典：输入： -woowoo输出：31LZ78举例 (17)字典：输入： -owoo输出：32LZ78举例 (18)字典：输入： -oo输出：33LZ78n观察：如果继续编码，字典将继续增长n实用的选择n停止增长字典n相当于从此成为一个静态字典策略n删除一些较早用过的项n如基于使用统计（但还没有好的算法决定哪些项该删）n将字典全部删除，从空字典开始重建字典n如果没有信源的特定知识，任何方法可能都

12、不会工作得很好！34LZ78的变种：LZWnTerry Welch (1984)n基本思想：n只对i编码，而不是编码 n算法：n/初始化字典为包含所有字母 Seed dictionary with all alphabet 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 = aendwhile35

13、LZW编码字典：输出：输入： wabbawabbawabbawabbawoowoowoop = 36LZW编码(2)字典：输出：输入： wabbawabbawabbawabbawoowoowoop = w 37LZW编码(3)字典：输出：5 (w)输入： -abbawabbawabbawabbawoowoowoop = wa38LZW编码(4)字典：输出：5 (w)2 (a)输入： -bbawabbawabbawabbawoowoowoop = ab39LZW编码(5)字典：输出：5 (w)2 (a)3 (b)输入： -bawabbawabbawabbawoowoowoop = bb40LZW

14、编码(6)字典：输出：5 (w)2 (a)3 (b)3 (b)输入： -awabbawabbawabbawoowoowoop = ba41LZW编码 (7)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)输入： -wabbawabbawabbawoowoowoop = a42LZW编码 (8)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()输入： -wabbawabbawabbawoowoowoop = w43LZW编码 (9)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()输入： -abbawabbawabbawoowoowoop =

15、 wa44LZW编码 (10)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)输入： -bbawabbawabbawoowoowoop = wab45LZW编码 (11)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)输入： -bawabbawabbawoowoowoop = bb46LZW编码 (12)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)输入： -awabbawabbawoowoowoop = bba47LZW编码 (13)字典：输出：5 (w)2 (a)3 (b)3

16、 (b)2 (a)1 ()6 (wa)8 (bb)输入： -wabbawabbawoowoowoop = a48LZW编码 (14)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)输入： -wabbawabbawoowoowoop = aw49LZW编码 (15)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)输入： -abbawabbawoowoowoop = wa50LZW编码 (16)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (b

17、b)10 (a)输入： -bbawabbawoowoowoop = wab51LZW编码 (17)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)输入： -bawabbawoowoowoop = wabb52LZW编码 (18)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)输入： -awabbawoowoowoop = ba53LZW编码 (19)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10

18、(a)12 (wab)9 (ba)输入： -wabbawoowoowoop = ba54LZW编码 (20)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)输入： -wabbawoowoowoop = w55LZW编码 (21)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)输入： -abbawoowoowoop = wa56LZW编码 (22)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 (

19、)6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)输入： -bbawoowoowoop = ab57LZW编码 (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)输入： -bawoowoowoop = abb58LZW编码 (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)输入： -awoowoowoop = ba59LZW编码 (25)

20、字典：输出：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)输入： -woowoowoop = ba60LZW编码 (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)输入： -woowoowoop = baw61LZW编码 (27)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11

21、(w)7 (ab)16 (ba)输入： -oowoowoop = wo5 (w)62LZW编码 (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)输入： -owoowoop = oo5 (w)4 (o)63LZW编码 (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)输入： -woowoop = o5 (w)4 (o)4 (o)64LZW

22、编码 (30)字典：输出：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)输入： -woowoop = w5 (w)4 (o)4 (o)65LZW编码 (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)输入： -oowoop = wo5 (w)4 (o)4 (o)11 (w)66LZW编码 (32)字典：输出：5 (w)2 (a)3 (b)3 (b)2 (

23、a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)输入： -owoop = oo5 (w)4 (o)4 (o)11 (w)67LZW编码 (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)输入： -woop = oo5 (w)4 (o)4 (o)11 (w)21 (oo)68LZW编码 (34)字典：输出：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)输入： -woop = w5 (w)4 (o)4 (o)11 (w)21 (oo)69LZW编码 (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)输入： -oop = wo5 (w)4 (o)4 (o)11 (w)21 (oo)70LZW编码 (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 (a

25、b)16 (ba)输入： -op = woo5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)71LZW编码 (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)16 (ba)输入： -p = o5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)4 (o)72LZW解码字典：输入： 5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = 输出：73LZW解码 (2)字典：输入： 5 2 3 3

26、 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = w 输出： w74LZW解码 (3)字典：输入： - 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 输出： wa75LZW解码 (4)输入： - - 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ab 输出： wab字典：76LZW解码 (5)输入： - - - 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb 输出： wabb字典：77LZW解码

27、(6)输入： - - - - 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ba 输出： wabba字典：78LZW解码 (7)输入： - - - - - 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = a 输出： wabba字典：79LZW解码 (8)输入： - - - - - - 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa 输出： wabbawa字典：80LZW解码 (9)输入： - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23

28、 4p = wa 输出： wabbawa字典：81LZW解码 (10)输入： - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wabb 输出： wabbawabb字典：82LZW解码 (11)输入： - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb 输出： wabbawabb字典：83LZW解码 (12)输入： - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4p = bba 输出： wabbawabba字典：84LZW解码 (13)

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

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

31、wabbawabbawabba字典：91LZW解码 (19)输入： - - - - - - - - - - - 11 7 16 5 4 4 11 21 23 4p = ba 输出： wabbawabbawabba字典：92LZW解码 (20)输入： - - - - - - - - - - - 11 7 16 5 4 4 11 21 23 4p = baw 输出： wabbawabbawabbaw字典：93LZW解码 (21)输入： - - - - - - - - - - - - 7 16 5 4 4 11 21 23 4p = w 输出： wabbawabbawabbaw 字典：最后得到与编码

32、器输入一致的字符串94LZW特殊情况n上述解码器n简单、有效，但是，有时会出错n不过可以修复n例：nA = a, bn输入序列：abababab n开始字典95LZW特殊情况：编码字典：输出： 输入：abababababab p =96LZW特殊情况：编码(2)输出：输入： abababababab p = a字典：97LZW特殊情况：编码(3)输出：1 (a)输入： -bababababab p = ab字典：98LZW特殊情况：编码(4)输出：1 (a)2 (b)输入： -ababababab p = ba字典：99LZW特殊情况：编码 (5)输出：1 (a)2 (b)输入： -babab

33、abab p = ab字典：100LZW特殊情况：编码 (6)输出：1 (a)2 (b)3 (ab)输入： -abababab p = aba字典：101LZW特殊情况：编码 (7)输出：1 (a)2 (b)3 (ab)输入： -bababab p = ab字典：102LZW特殊情况：编码 (8)输出：1 (a)2 (b)3 (ab)输入： -ababab p = aba字典：103LZW特殊情况：编码 (9)输出：1 (a)2 (b)3 (ab)5 (aba)输入： -babab p = abab字典：104LZW特殊情况：解码输入： 1 2 3 5 p = 输出：字典：105LZW特殊情况

34、：解码 (2)输入： 1 2 3 5 p = a 输出： a字典：索引在字典中存在：输出索引对应的词条前缀+当前词条的第一个字符 字典的新词条106LZW特殊情况：解码 (3)输入： - 2 3 5 p = ab 输出： ab字典：107LZW特殊情况：解码 (4)输入： - - 3 5 p = bab 输出： abab字典：108LZW特殊情况：解码 (5)输入： - - - 5 p = ab 输出： abab字典：109LZW特殊情况：解码 (6)输入： - - - 5 p = ab? 输出： abab?字典：110LZW特殊情况：解码 (7)n第5个词条应该以 ab开始 需将其加到 p

35、并继续解码输入： - - - 5 p = ab? 输出： abab?字典：111LZW特殊情况：解码 (8)输入： - - - 5 p = abab? 输出： abab?字典：112LZW特殊情况：解码 (9)输入： - - - 5 p = ababa 输出： abab?字典：113LZW特殊情况：解码 (10)输入： - - - - p = aba 输出： abababan索引不在字典中：n前缀+前缀的的第一个字符 字典的新词条n输出索引对应的词条字典：114LZW解码算法LZW译码算法可用伪码表示如下：nDictionaryj all n single-character, j =1，2，

36、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 DictionarycWn Dictionaryj Prefix.cWn j n + 1n pW cWn elsen Prefix DictionarypWn cW first Character of

37、 Prefixn Charstream Prefix.cWn Dictionaryj Prefix.cWn pW cWn j n + 1115字典结构n字典越大，能存储更多的字符串，也就能匹配更长的字符串，但其代价是指针更长（标识需要的位数越多），搜索起来也更慢n对字典而言，最好的数据结构是树：trien 116字典结构n在编码时，编码器逐个输入字符并累积成字符串I（相当于伪代码中的Prefix ）n只要在字典中能找到变量I的字符串，编码器就不断地输入字符并将其串接到I中，直到某个输入字符x与I连接后使搜索失败（字符串Ix不在字典中），然后将Ix加到字典中。n添加到字典中去的每个字符串仅有效增

38、加了一个新字符x，即对每个不止一个字符的字符串，字典中有一个比它只少一个字符的“母串”。117字典结构n用树trie表示时，树是动态建立的，且树中每个节点可能存在多个子节点。因此数据结构应该设计成一个节点可拥有任意个子节点，但无需为其预留空间：将树驻留在一个节点数组中，每个数据结构有两个字段：一个字符和指向母节点的指针n数据结构中没有指向子节点的指针，沿着树从一个节点到其子节点的操作可用一个散列过程实现，该过程把指向节点的指针和子节点的字符散列以生成一个新指针，因此需添加一个新字段：散列索引118字典结构n实用中，每个节点有3个字段：n树用数组dict表示，数组下标用pointer表示，所以d

39、ictpointer表示一个节点ndictpointer.parentndictpointer.indexndictpointer.symbol119字典结构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.

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