基于双数组Trie（Double-Array Trie）的词典查询算法

2020-02-23 219浏览

1. 基于双数组 Trie （ Double-Array Tri e ）的词典查询算法的词典查询算法王小飞 2004-9-17
2. 提纲 词典查询算法简介 双数组 Trie 的数据结构 基于双数组 Trie 的词典查询算法 存在的问题及一些改进
3. 词典查询算法简介在汉语信息处理系统中，汉语词典查询是一个重要的基础环节，在整个处理过程中都需要频繁地访问词典以获得汉语词语知识。因此汉语词典的快速查询对整个系统的效率有着非常重要的影响。大部分的词典结构都是基于 hash 方法。这种方法的关键技术在于 hash 函数的设计，采用合理的方式来调节数据块的分配，控制分布的均匀性，减少冲突，提高空间利用率。
4. 词典查询算法简介目前的几种典型词典查询方法： 1. 整词二分法 2.Trie 索引树法 3. 逐字二分法
5. 词典查询算法简介  整词二分法结构：首字散列表、词索引表、词典正文优点：数据结构简单、占用空间小。缺点：全词匹配，效率相对来说不高。  Tire 索引树法结构：首字散列表、 Trie 索引树结点优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。  逐字二分法结构：同整词二分法优点：查询采用逐字匹配，提高了一定的匹配效率。缺点：由于词典结构未改变，效率的提高有限。
6. 双数组 Trie 的数据结构  Trie 树： Trie 树是搜索树的一种。 ab cd l … g t … e u … o … … m t … blue but gem get 利用关键码的字符，自左向右，每次插入一个得到的 Trie 树
7. 双数组 Trie 的数据结构  本质是一个确定的有限状态自动机（ DFA ）的词典查询算法，每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。  Trie 树的空间复杂度为 O(n)  缺点：数据结构复杂，查询效率较低  为了让 Trie 实用的实现算法在空间占用较少的同时保证查询的效率， Aoe,J 提出了用 2 个线性数组来进行 Trie 树的表示，即双数组 Trie(Double-Array Trie)
8. 双数组 Trie 的数据结构 两个数组： base[] 、 check[] base ：数组中的每一个元素相当于 trie 树的一个节点。 check ：相当于当前状态的前一状态。 对于从状态 s 到状态 t 的一个转移，必须满足： check[base[s]+c]=s base[s]+c=t 其中 c 是输入变量。
9. 双数组 Trie 的数据结构 check base s c t s c t s
10. 基于双数组 Trie 的词典查询算法  基本思想：对 6763 个常用汉字根据其内码相应的赋予从 1 － 6 763 的序列码，放入 base[1]-base[6763] 。若首字序列码是 i 的词语有 n 个，设所有第二个字的序列码依次为 a 1,a2,a3,an, 则这 n 个第二字在 base 数组中的位置依次为 base[i]+a1,base[i]+a2,…base[i]+an 。依次类推第三字、第四字……第 k 字的位置。如果 base[i] 和 check[i] 同为 0 ，表示该位置为空；如果 base[i] 为负值，表示该状态为一个词语。
11. 基于双数组 Trie 的词典查询算法 数组构造对于每一个汉字，要确定其 base[] 值，使得对于所有以该汉字开头的词语都能在数组中放下。即要找到一个 k=base[i] ，使得 base[k+a1],che ck[k+a1],base[k+a2],check[k+a2],…base[k+an] ,check[k+an] 均为 0 ， a1,a2…an 是以 i 开头的
12. 基于双数组 Trie 的词典查询算法 查询 t := base[s] + c; if check[t] = s then next state := t else fail endif
13. 基于双数组 Trie 的词典查询算法 双数组构造完成之后，查询实质上就是将待查词的各字分别转换为相应的序列码，然后作几次加法，即可查到相应的词语。查询效率是极高的。
14. 基于双数组 Trie 的词典查询算法 添加节点当词典添加新词的时候， Trie 树中就要添加新的节点。如果新插入的变量是 c ，则必须保证 base[base[i]+ c]=0 i base[i]+c 如果非空，则要重置 base[i] 以及之后的相关项。
15. 基于双数组 Trie 的词典查询算法  Procedure Relocate(s : state; b : base_index) {Move base for state s to a new place beginning at b } begin for each input character c for the state s { i.e. for each c such that check[base[s] + c]] = s } begin check[b + c] := s; { mark owner } base[b + c] := base[base[s] + c]; { copy data } { the node base[s] + c is to be moved to b + c; Hence, for any i for which ch eck[i] = base[s] + c, update check[i] to b + c } for each input character d for the node base[s] + c begin check[base[base[s] + c] + d] := b + c end; check[base[s] + c] := none { free the cell } end; base[s] := b end
16. 基于双数组 Trie 的词典查询算法 base check b base[s] s c t’ S c t none base[t] u d t’
17. 基于双数组 Trie 的词典查询算法词表：啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及啊根 2 胶 3 6 拉埃伯 7 及 11 5 4 阿 1 廷 11 Trie 树表示人 8 9
18. 基于双数组 Trie 的词典查询算法  编码：啊 -1 ，阿 -2 ，埃 -3 ，根 -4 ，胶 -5 ，拉 -6 ，及 -7 ，廷 -8 ，伯 -9 ，人 -10  经过四次遍历，将所有词语放入双数组中，再遍历一遍词表，修改 base 值 if 状态 i 为一个词 if base[i]=0 then base[i]= -I else base[i]=(-1)*base[i]
19. 基于双数组 Trie 的词典查询算法得到双数组如下：下标 1 2 3 4 5 6 7 8 9 10 11 base －1 1 1 0 1 －6 1 －8 －9 －1 － 11 check 0 0 0 0 2 2 2 3 5 7 10 状态啊阿埃阿根阿胶阿拉埃及阿根廷阿拉伯阿拉伯人查询时相当于从一个状态查到另一个状态。比如查“阿根廷”，先根据“阿”的序列码 2 ，得到 base[2]=1 ，再根据“根”的序列码 4 ，得到“阿根”这个状态的数组下标为 base[2]+4=5,check [5]=2 ，继续，因为 base[5]=1 ，根据“廷”的序列码 8 ，得到“阿根廷”这个状态的数组下标 base[5]+8=9 ， check[9]=5 ，同时 base [9] 为负值，表明“阿根廷”是词表中的一个词，查询完毕。
20. 基于双数组 Trie 的词典查询算法  算法的时间和空间复杂度根据之前的分析，该算法的查询避免了字符串比较、 co py 运算等步骤，直接进行数值计算和数组读取，因而时间上比其他查询算法都要快。三种查询算法的比较查询算法名称花费时间 (s) 逐字二分法 6.697 双编码 4.725 双数组 Trie 1.408
21. 基于双数组 Trie 的词典查询算法空间上，对于一个空间大小为 5,650,000 字节的主词典，增加的数组结构大概需要 1,440,000 字节，总共占用空间 7,090,000 字节。
22. 存在的问题 在数据结构上不可避免的存在空间浪费。 构造调整过程中，每个状态都依赖于其他状态，所以当在词典插入或删除词语的时候，往往需要对双数组结构进行全局调整，灵活性较差。
23. 一些改进 只把词表中出现的首字词按序列码放入数组中，而不是把 6763 个常用字全都放入 base[] 数组的前 6763 位中。 在初始构造确定 base[] 值的时候，优先处理词数多的首字。为了避免调整范围太大，预先留一定空间备以后添加新词。
24. Thanks for your attention ！