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