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

Presentation on theme: "基于双数组Trie（Double-Array Trie）的词典查询算法"— Presentation transcript:

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

2 提纲 词典查询算法简介 双数组Trie的数据结构 基于双数组Trie的词典查询算法 存在的问题及一些改进

3 词典查询算法简介 在汉语信息处理系统中，汉语词典查询是一个重要的基础环节，在整个处理过程中都需要频繁地访问词典以获得汉语词语知识。因此汉语词典的快速查询对整个系统的效率有着非常重要的影响。 大部分的词典结构都是基于hash方法。这种方法的关键技术在于hash函数的设计，采用合理的方式来调节数据块的分配，控制分布的均匀性，减少冲突，提高空间利用率。

4 词典查询算法简介 目前的几种典型词典查询方法： 1.整词二分法 2.Trie索引树法 3.逐字二分法

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

6 双数组Trie的数据结构 Trie树： a b c d g t … … … … … … Trie树是搜索树的一种。
l u e 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树的一个节点。
对于从状态s到状态t的一个转移，必须满足： check[base[s]+c]=s base[s]+c=t 其中c是输入变量。

9 双数组Trie的数据结构 base check s c s t s c t

10 基于双数组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]为负值，表示该状态为一个词语。

11 基于双数组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开头的词的第二字序列码。

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 如果非空，则要重置base[i]以及之后的相关项。 i base[i]+c

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 check[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 } base[s] := b end

16 基于双数组Trie的词典查询算法 base check b S none t’ base[s] s c t’ c t base[t] d u

17 基于双数组Trie的词典查询算法 词表：啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及 啊 根 廷 2 4 5 阿 胶 3 1 6 拉 伯 人 7
8 9 埃 及 11 11 Trie树表示

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 －6 －8 －9 －11 check 状态 啊 阿 埃 阿根 阿胶 阿拉 埃及 阿根廷 阿拉伯 阿拉伯人 查询时相当于从一个状态查到另一个状态。比如查“阿根廷”，先根据“阿”的序列码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的词典查询算法 算法的时间和空间复杂度
根据之前的分析，该算法的查询避免了字符串比较、copy运算等步骤，直接进行数值计算和数组读取，因而时间上比其他查询算法都要快。 三种查询算法的比较 查询算法名称 花费时间(s) 逐字二分法 6.697 双编码 4.725 双数组Trie 1.408

21 基于双数组Trie的词典查询算法 空间上，对于一个空间大小为5,650,000字节的主词典，增加的数组结构大概需要1,440,000字节，总共占用空间7,090,000字节。

22 存在的问题 在数据结构上不可避免的存在空间浪费。
构造调整过程中，每个状态都依赖于其他状态，所以当在词典插入或删除词语的时候，往往需要对双数组结构进行全局调整，灵活性较差。

23 一些改进 只把词表中出现的首字词按序列码放入数组中，而不是把6763个常用字全都放入base[]数组的前6763位中。

24 Thanks for your attention！