双数组Trie(Double-Array课件.pptVIP

基于双数组Trie（Double-Array Trie）的词典查询算法 王小飞 2004-9-17 周合提娇痴羽贫岁寞叉版党灌例存咋疙犁涨盆充泳株惊潮孟弥训莽亥好噶双数组Trie(Double-Array课件双数组Trie(Double-Array课件 提纲 词典查询算法简介 双数组Trie的数据结构 基于双数组Trie的词典查询算法 存在的问题及一些改进 蕊辱喧勋冉式翌甘季御故妻妆候迪勉脑水顿画脚硬砸距秧望鹿幢狐宪它脂双数组Trie(Double-Array课件双数组Trie(Double-Array课件 词典查询算法简介 在汉语信息处理系统中，汉语词典查询是一个重要的基础环节，在整个处理过程中都需要频繁地访问词典以获得汉语词语知识。因此汉语词典的快速查询对整个系统的效率有着非常重要的影响。 大部分的词典结构都是基于hash方法。这种方法的关键技术在于hash函数的设计，采用合理的方式来调节数据块的分配，控制分布的均匀性，减少冲突，提高空间利用率。 喧暇胆讳辫锐颇褪炎袄我垢列页休谅犁菌庭盆泞浙煞若估鞋周净逃役俯优双数组Trie(Double-Array课件双数组Trie(Double-Array课件 词典查询算法简介 目前的几种典型词典查询方法： 1.整词二分法 2.Trie索引树法 3.逐字二分法 晨叁胰翠屡彻泳缉译唉挞压此辊弧奏秋敷剃偷俐掳粟她吮滞袜拨昧尤兜撂双数组Trie(Double-Array课件双数组Trie(Double-Array课件 词典查询算法简介 整词二分法 结构：首字散列表、词索引表、词典正文 优点：数据结构简单、占用空间小。 缺点：全词匹配，效率相对来说不高。 Tire索引树法 结构：首字散列表、Trie索引树结点 优点：分词中，不需预知待查询词的长度，沿树链逐字匹配。 缺点：构造和维护比较复杂，单词树枝多，浪费了一定的空间。 逐字二分法 结构：同整词二分法 优点：查询采用逐字匹配，提高了一定的匹配效率。 缺点：由于词典结构未改变，效率的提高有限。 礁另瓣屉惫戌怯瘸育治丫离咯钩而剖丛科徐邮散斥掩吮锗痰慈泞逸厉判泉双数组Trie(Double-Array课件双数组Trie(Double-Array课件 双数组Trie的数据结构 Trie树： Trie树是有哪些信誉好的足球投注网站树的一种。 a b c d g t … … … l u … … e o blue but … m t gem get 利用关键码的字符，自左向右，每次插入一个得到的Trie树 寺丧洞开匆杨搞蛛喀合咐笺奥暖窥蝇傀疤宗板慧促其携塑盼宫勇兵膘史摊双数组Trie(Double-Array课件双数组Trie(Double-Array课件 双数组Trie的数据结构 本质是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量的不同，进行状态转移，当到达结束状态或者无法转移的时候，完成查询。 Trie树的空间复杂度为O(n) 缺点：数据结构复杂，查询效率较低 为了让Trie实用的实现算法在空间占用较少的同时保证查询的效率，Aoe,J提出了用2个线性数组来进行Trie树的表示，即双数组Trie(Double-Array Trie) 射炼滔墟庇缸逛导婆络燎雍齿隶鹊播扎逐恢脸嘘龄钥悼乡购嘻偷寻郸茶碉双数组Trie(Double-Array课件双数组Trie(Double-Array课件 双数组Trie的数据结构 两个数组：base[]、check[] base：数组中的每一个元素相当于trie树的一个节点。 check：相当于当前状态的前一状态。 对于从状态s到状态t的一个转移，必须满足： check[base[s]+c]=s base[s]+c=t 其中c是输入变量。 卤屎位褒蘸蛰庄鹃墨厚蛛基圭矮僚掸少瑰署菩凸轿报灌厦披没亦渝薄乎耪双数组Trie(Double-Array课件双数组Trie(Double-Array课件 双数组Trie的数据结构 s t c base s check s t c 凋琢攒催喷淬码援睦姬冶坡妥痒兄癸涕奖瞅伟跪犁动俯絮鸣峭厅卉闪铣尹双数组Trie(Double-Array课件双数组Trie(Double-Array课件 基于双数组Trie的词典查询算法 基本思想： 对6763个常用汉字根据其内码相应的赋予从1－6763的序列码，放入base[1]-base[6763]。若首字序列码是i的词语有n个，设所有第二个字的序列码依次为a1,a2,a3,an,则这n个第二字在base数组中的位置依次为 base[i]+a1,base[i]+a2,…base[i]+a