双数组trie树的基本构造及简单优化

双数组trie树的基本构造及简单优化  2007/06/04

作者：Sunny from Hour41 (www.hour41.com )

一、 基本构造

Trie树是搜索树的一种，来自英文单词"Retrieval"的简写，可以建立有效的数据检索组织结构，是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态。在词典中这此状态包括＂词前缀＂，＂已成词＂等。

双数组Trie（Double-Array Trie）是trie树的一个简单而有效的实现，由两个整数数组构成，一个是base[]，另一个是check[]。设数组下标为i ,如果base[i],check[i]均为0,表示该位置为空。如果base[i]为负值，表示该状态为词语。Check[i]表示该状态的前一状态，t=base[i]+a, check[t]=i 。

下面举例(源自<<双数组Trie（Double-Array Trie）的数据结构与具体实现>>)来说明用双数组Trie（Double-Array Trie）构造分词算法词典的过程。假定词表中只有“啊，阿根廷，阿胶，阿拉伯，阿拉伯人，埃及”这几个词，用Trie树可以表示为： 

我们首先对词表中所有出现的10个汉字进行编码：啊-1，阿-2，唉-3，根-4，胶-5，拉-6，及-7，廷-8，伯-9，人-10。。对于每一个汉字，需要确定一个base值，使得对于所有以该汉字开头的词，在双数组中都能放下。例如，现在要确定“阿”字的base值，假设以“阿”开头的词的第二个字序列码依次为a1，a2，a3……an，我们必须找到一个值i，使得base[i+a1]，check[i+a1]，base[i+a2]，check[i+a2]……base[i+an]，check[i+an]均为0。一旦找到了这个i，“阿”的base值就确定为i。用这种方法构建双数组Trie（Double-Array Trie），经过四次遍历，将所有的词语放入双数组中，然后还要遍历一遍词表，修改base值。因为我们用负的base值表示该位置为词语。如果状态i对应某一个词，而且Base[i]=0，那么令Base[i]=（-1）*i，如果Base[i]的值不是0，那么令Base[i]=（-1）*Base[i]。得到双数组如下：

下标<o:p></o:p>

1<o:p></o:p>

2<o:p></o:p>

3<o:p></o:p>

4<o:p></o:p>

5<o:p></o:p>

6<o:p></o:p>

7<o:p></o:p>

8<o:p></o:p>

9<o:p></o:p>

10<o:p></o:p>

11<o:p></o:p>

12<o:p></o:p>

13<o:p></o:p>

14<o:p></o:p>

Base<o:p></o:p>

-1<o:p></o:p>

4<o:p></o:p>

4<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

4<o:p></o:p>

-9<o:p></o:p>

4<o:p></o:p>

-11<o:p></o:p>

-12<o:p></o:p>

-4<o:p></o:p>

-14<o:p></o:p>

Check<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

0<o:p></o:p>

2<o:p></o:p>

2<o:p></o:p>

2<o:p></o:p>

3<o:p></o:p>

8<o:p></o:p>

10<o:p></o:p>

13<o:p></o:p>

词缀<o:p></o:p>

啊<o:p></o:p>

阿<o:p></o:p>

埃<o:p></o:p>

<o:p> </o:p>

<o:p> </o:p>

<o:p> </o:p>

<o:p> </o:p>

阿根<o:p></o:p>

阿胶<o:p></o:p>

阿拉<o:p></o:p>

埃及<o:p></o:p>

阿根廷<o:p></o:p>

阿拉伯<o:p></o:p>

阿拉伯人<o:p></o:p>

 用上述方法生成的双数组，将“啊”，“阿”，“埃”，“阿根”，“阿拉”，“阿胶”，“埃及”，“阿拉伯”，“阿拉伯人”，“阿根廷”均视为状态。每个状态均对应于数组的一个下标。例如设“阿根”的下标为i=8，那么check[i]的内容是“阿”的下标，而base[i]是“阿根廷”的下标的基值。“廷”的序列码为x=8，那么“阿根廷”的下标为base[i]+x=base[8]+8=12。

二、 基本操作与存在问题

1， 查询
trie树的查询过程其实就是一个DFA的状态转移过程，在双数组中实现起来比较简单：只需按照状态标志进行状态转移即可．例如查询“阿根廷”，先根据“阿”的序列码b=2，找到状态“阿”的下标2，再根据“根”的序列码d=4找到“阿根”的下标base[b]+d=8，同时根据check[base[b]+d]=b，表明“阿根”是某个词的一部分，可以继续查询。然后再找到状态“阿根廷”。它的下标为y=12，此时base[y]<0，check[y]=base[b]+d=8，表明“阿根廷”在词表中，查询完毕。

查询过程中我们可以看到，对于一个词语的查询时间是只与它的长度相关的，也就是说它的时间复杂度为Ｏ(1)．在汉语中，词语以单字词，双字词居多，超过三字的词语少之又少．因此，用双数组构建的trie树词典查询是理论上中文机械分词中的最快实现。

2， 插入与删除
双数组的缺点在于：构造调整过程中，每个状态都依赖于其他状态，所以当在词典中插入或删除词语的时候，往往需要对双数组结构进行全局调整,灵活性能较差。

将一个词语插入原有的双数组trie树中，相当于对DFA增加一个状态。首先我们应根据查询方法找出该状态本应所处的位置，如果该位置为空，那好办，直接插入即可。如果该位置不为空。那么我们只好按照构造时一样的方法重新扫描得出该状态已存在的最大前缀状态的BASE值，并由此依次得出该状态后继结点的BASE值。在这其中还要注意CHECK值的相应变化。

例如说，如果＂阿拉根＂某一天也成为了一个词，我们要在trie树中插入这一状态。按计算它的位置应在８，但8是一个已成状态．所以我们得重新确定＂阿拉＂这一最大已成前缀状态的BASE值．重新扫描得出BASE[10]=11。这样状态１５为＂阿拉根＂，且BASE[15]为负（成词），CHECK[15]=10；状态２０为＂阿拉佰＂，且BASE[20]=-4，CHECK=10。

这样的处理其实是非常耗时间的，因为得依次对每一个可能BASE值进行扫描来进行确定最大已成前缀状态的BASE值。这个确定过程在构造时还是基本可以忍受的，毕竟你就算用上一，两天来构造也没有问题（只要你构造完后可以在效运行即可）。但在插入比较频繁时，如果每次都需要那么长的运行时间，那确实是无法忍受的。

双数组删除实现比较简单，只需要将删除词语的对应状态设为空即可――即BASE值，CHECK均为设0。但它存在存在一个空间效率的问题．例如，当我们在上面删除＂埃及＂这一词语时，状态11被设为空。而状态10则成了一个无用结点――它不成词，而且在插入新词时也不可重用。所以，随着删除的进行，空状态点和无用状态点不断增多，空间的利用率会不断的降低。

三、 简单优化

优化的基本思路是将双数组trie树构建为一种动态检索方法，从而解决插入和删除所存在的问题。

1， 插入优化
在插入需要确定新的BASE值时，我们是只需要遍历空状态的。非空状态的出现意味着某个BASE值尝试的打败，我们可以完全不必理会。所以，我们可以对所有的空状态构建一个序列，在确定BASE值时只需要扫描该序列即可。
对双数组中的空状态的递增结点r1,r2, …, rm，我们可以这样构建这一空序列：
CHECK[ri]=−ri+1 (1 i m−1),
CHECK[rm]=−(DA_SIZE+1)
其中r1= E_HEAD，为第一个空值状态对应的索引点。这样我们在确定BASE值时只需扫描这一序列即可。这样就省去了对非空状态的访问时间。

这种方法在空状态并不太多的情况下可以很大程度的提高插入速度。

2， 删除优化
1) 无用结点
对于删除叶结点时产生的无用结点，可以通过依次判断将它们置为空，使得可在插入新词时得以重用。例如，如果我们删除了上例中的＂阿根廷＂，可以看到＂阿根＂这一状态没有子状态，因此也可将它置为空。而＂阿＂这一状态不能置空，因为它还有两个子状态。

2) 数组长度的压缩
在删除了一个状态后，数组末尾可能出现的连续空状态我们是可以直接删除的。另外我们还可以重新为最大非空索引点的状态重新确定BASE值，因为它有可能已经由于删除的进行而变小。这们我们可能又得以删除一些空值状态。

评论

1 楼 kevinye 2008-01-17  

有没有具体的实现?