基于双数组TrieDoubleArray Trie的词典查询算法.pptVIP

基于双数组Trie（Double-Array Trie）的词典查询算法 王小飞 2004-9-17 提纲 词典查询算法简介 双数组Trie的数据结构 基于双数组Trie的词典查询算法 存在的问题及一些改进 词典查询算法简介 在汉语信息处理系统中，汉语词典查询是一个重要的基础环节，在整个处理过程中都需要频繁地访问词典以获得汉语词语知识。因此汉语词典的快速查询对整个系统的效率有着非常重要的影响。 大部分的词典结构都是基于hash方法。这种方法的关键技术在于hash函数的设计，采用合理的方式来调节数据块的分配，控制分布的均匀性，减少冲突，提高空间利用率。 词典查询算法简介 目前的几种典型词典查询方法： 1.整词二分法 2.Trie索引树法 3.逐字二分法 词典查询算法简介 整词二分法 结构：首字散列表、词索引表、词典正文 优点：数据结构简单、占用空间小。 缺点：全词匹配，效率相对来说不高。 Tire索引树法 结构：首字散列表、Trie索引树结点 优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。 缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。 逐字二分法 结构：同整词二分法 优点：查询采用逐字匹配，提高了一定的匹配效率。 缺点：由于词典结构未改变，效率的提高有限。 双数组Trie的数据结构 Trie树： Trie树是搜索树的一种。 双数组Trie的数据结构 本质是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。 Trie树的空间复杂度为O(n) 缺点：数据结构复杂，查询效率较低 为了让Trie实用的实现算法在空间占用较少的同时保证查询的效率，Aoe,J提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double-Array Trie) 双数组Trie的数据结构 两个数组：base[]、check[] base：数组中的每一个元素相当于trie树的一个节点。 check：相当于当前状态的前一状态。 对于从状态s到状态t的一个转移，必须满足： check[base[s]+c]=s base[s]+c=t 其中c是输入变量。 双数组Trie的数据结构 基于双数组Trie的词典查询算法 基本思想： 对6763个常用汉字根据其内码相应的赋予从1－6763的序列码，放入base[1]-base[6763]。若首字序列码是i的词语有n个，设所有第二个字的序列码依次为a1,a2,a3,an,则这n个第二字在base数组中的位置依次为 base[i]+a1,base[i]+a2,…base[i]+an。依次类推第三字、第四字……第k字的位置。 如果base[i]和check[i]同为0，表示该位置为空； 如果base[i]为负值，表示该状态为一个词语。 基于双数组Trie的词典查询算法 数组构造 对于每一个汉字，要确定其base[]值，使得对于所有以该汉字开头的词语都能在数组中放下。即要找到一个k=base[i]，使得base[k+a1],check[k+a1],base[k+a2],check[k+a2],…base[k+an],check[k+an]均为0，a1,a2…an是以i开头的词的第二字序列码。 基于双数组Trie的词典查询算法 查询 t := base[s] + c;if check[t] = s then next state := t else fail endif 基于双数组Trie的词典查询算法 双数组构造完成之后，查询实质上就是将待查词的各字分别转换为相应的序列码，然后作几次加法，即可查到相应的词语。查询效率是极高的。 基于双数组Trie的词典查询算法 添加节点 当词典添加新词的时候，Trie树中就要添加新的节点。如果新插入的变量是c，则必须保证base[base[i]+c]=0 如果非空，则要重置base[i]以及之后的相关项。 基于双数组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 }