基于双数组Trie树的词典查询算法

《基于双数组Trie树的词典查询算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于双数组Trie（Double-ArrayTrie）的词典查询算法王小飞2004-9-17提纲词典查询算法简介双数组Trie的数据结构基于双数组Trie的词典查询算法存在的问题及一些改进词典查询算法简介在汉语信息处理系统中，汉语词典查询是一个重要的基础环节，在整个处理过程中都需要频繁地访问词典以获得汉语词语知识。因此汉语词典的快速查询对整个系统的效率有着非常重要的影响。大部分的词典结构都是基于hash方法。这种方法的关键技术在于hash函数的设计，采用合理的方式来调节数据块的分配，控制分布的均匀性，减少冲突，提高空间利用率。词典查询算法简介目前的几种典型词典查询方法：1.整

2、词二分法2.Trie索引树法3.逐字二分法词典查询算法简介整词二分法结构：首字散列表、词索引表、词典正文优点：数据结构简单、占用空间小。缺点：全词匹配，效率相对来说不高。Tire索引树法结构：首字散列表、Trie索引树结点优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。逐字二分法结构：同整词二分法优点：查询采用逐字匹配，提高了一定的匹配效率。缺点：由于词典结构未改变，效率的提高有限。双数组Trie的数据结构Trie树：Trie树是搜索树的一种。abcdgt………lu……eobluebut…mtgemget利用关键码

3、的字符，自左向右，每次插入一个得到的Trie树双数组Trie的数据结构本质是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。Trie树的空间复杂度为O(n)缺点：数据结构复杂，查询效率较低为了让Trie实用的实现算法在空间占用较少的同时保证查询的效率，Aoe,J提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double-ArrayTrie)双数组Trie的数据结构两个数组：base[]、check[]base：数组中的每一个元素相当于trie树的一个节点。check：相

4、当于当前状态的前一状态。对于从状态s到状态t的一个转移，必须满足：check[base[s]+c]=sbase[s]+c=t其中c是输入变量。双数组Trie的数据结构stcbasescheckstc基于双数组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字的位置。如果

5、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;ifcheck[t]=sthennextstate:=tel

6、sefailendif基于双数组Trie的词典查询算法双数组构造完成之后，查询实质上就是将待查词的各字分别转换为相应的序列码，然后作几次加法，即可查到相应的词语。查询效率是极高的。基于双数组Trie的词典查询算法添加节点当词典添加新词的时候，Trie树中就要添加新的节点。如果新插入的变量是c，则必须保证base[base[i]+c]=0如果非空，则要重置base[i]以及之后的相关项。ibase[i]+c基于双数组Trie的词典查询算法ProcedureRelocate(s:state;b:base_index){Movebaseforstatestoanewplacebeg

7、inningatb}beginforeachinputcharactercforthestates{i.e.foreachcsuchthatcheck[base[s]+c]]=s}begincheck[b+c]:=s;{markowner}base[b+c]:=base[base[s]+c];{copydata}{thenodebase[s]+cistobemovedtob+c;Hence,foranyiforwhichcheck[i]=base[s]+c,updatecheck[i]tob+c}for