双数组TRIE树原理

 

原文名称&＃xff1a;

An Efficient Digital Search Algorithm by Using a Double-Array Structure

作者&＃xff1a;

JUN-ICHI AOE

译文&＃xff1a;

使用双数组结构的一个高效的Digital Search算法



摘要&＃xff1a;

本文介绍了一种新的内部&＃xff08;内部排序的内部&＃xff0c;也就是在内存里&＃xff09;数组结构的digital search算法&＃xff0c;叫做双数组&＃xff0c;结合了数组存取的快速和链式存储的压缩。Digital search树的每一条弧在双数组中都可以以O(1)的时间复杂度计算得到&＃xff1b;也就是说&＃xff0c;查找一个key值最坏的时间复杂度是O(k)&＃xff0c;k是这个key值的长度。本文给出了同时具有速度和空间双重性能的双数组的查找&＃xff0c;插入&＃xff0c;删除算法。假设双数组的长度是n&＃43;cm&＃xff0c;n是ds树中节点的数量&＃xff0c;m是输入符号的数量&＃xff0c;c是一个依赖于实现的常数&＃xff1b;那么理论上可以证明插入和删除的最坏时间复杂度分别是cm2&＃xff08;插入要解决冲突&＃xff0c;所以慢&＃xff09;和cm&＃xff0c;与n没有关系。从实验的结果来看&＃xff0c;建立双数组的时间随n增长&＃xff0c;并且c是一个相当小的常数&＃xff0c;从0.17到1.13。



关键词&＃xff1a;数据库系统&＃xff0c;数据结构&＃xff0c;词典&＃xff0c;digital search&＃xff0c;动态内部存储&＃xff0c;关键词查询算法。 ---





1.       导论

在很多信息检索算法中&＃xff0c;很需要采用一种快速的digital search算法&＃xff0c;或者叫做trie搜索&＃xff0c;因为它一个字符(digital)一 个字符地查看输入。使用这种数据结构的例子有一种词法分析器&＃xff0c;和一种编译器的本地代码优化器&＃xff0c;一种图书搜索&＃xff0c;拼写检查&＃xff0c;常用单词过滤器&＃xff0c;一种自然语言处理 中的形态学分析器等等。词典能够动态增长在自然语言处理中尤为重要&＃xff0c;因为经常需要对词汇表添加新词&＃xff08;这其实是双数组的弱项- -&＃xff09;。本文展示的这一算法适合插入远远多于删除的情况&＃xff0c;这样删除带来的空间浪费就可以由插入来填补。



       关键词查询策略可以被大致分为两类&＃xff0c;按照关键词集合是否可变可以将这些算法分为“动态方法”&＃xff08;允许查询表被修改&＃xff09;和“静态方法”&＃xff08;显然相反&＃xff09;两种。广为人知的“动态方法”有&＃xff1a;hashing&＃xff0c;二叉树&＃xff0c;B&＃43;树&＃xff0c;扩展hashing&＃xff0c;和trie hashing。而“静态方法”有&＃xff1a;完美hashing&＃xff0c;稀疏表&＃xff0c;以及压缩trie。 当使用静态方法的时候我们能专注于提高查询速度和压缩数据结构&＃xff0c;而当使用动态方法的时候我们会使用额外的空间以达到更快的更新速度。本文提出的查询方法正 好介于这两者之间&＃xff0c;所以我称之为“弱静态方法”。将静态方法扩展到弱静态方法&＃xff0c;同时保持前者有用的特性是十分困难的。完美hashing的扩展已经有了&＃xff0c;但不能确定插入的时间复杂度上限。本文的目标是建立一种digital search算法&＃xff0c;它同时具有静态方法的速度和压缩特性&＃xff0c;以及动态方法的快速更新的能力。



       不同于基于key值的搜索方法&＃xff0c;digital search采用一连串的字符(digit)来表示一个key。每个h层的DS树的节点表示所有以一定的h个字符开始的关键词&＃xff1b;这个节点根据第(h&＃43;1)个字符定义它的分支。本文的基本观念是压缩trie树&＃xff0c;使用两个一维数组base和check来表示trie树&＃xff0c;成为双数组&＃xff0c;并且给出更新&＃xff08;插入、删除&＃xff09;算法。Trie的每个节点使用指针指向下一个元素&＃xff0c;每个索引元素是一个结束标志加上一个指向新节点的指针&＃xff08;或者null&＃xff09;。查询&＃xff0c;插入&＃xff0c;删除都非常快&＃xff0c;但是它会占用很多空间&＃xff0c;因为很多trie树节点是空的&＃xff1b;也就是说&＃xff0c;trie树是稀疏的。所以我们必须尝试映射节点r到check数组&＃xff0c;这种映射关系由base[r]指定。



       在接下来的章节&＃xff0c;我们会详细描述我们的想法。在第二节&＃xff0c;我们把DS树形式化为模式匹配机器并定义双数组使用O(1)时间计算一条弧。为了将双数组应用于大的关键词集合&＃xff0c;双数组做出了一些修改。最主要的创新是仅将足以分辨不通关键词的前缀存储到双数组&＃xff0c;将其他部分存储在单独的string里面。插入删除算法在第三章讨论。当插入一个新的非空位置r的时候遇到另一个节点k已经占用这个位置&＃xff0c;插入算法通过重新调整base[r]或者base[k]来解决冲突。在本文中&＃xff0c;为减少占用的时间和空间占用组少非空未知的k或r有优先权&＃xff08;就是移动占用少的&＃xff0c;占用多的不变&＃xff09;。第四节讨论了每个算法的最坏时间复杂度的理论值&＃xff0c;并且通过实验验证了。双数组的部分匹配和key-order查询也做出了讨论。最后第五节做出了结论总结。



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



一、 基本构造



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

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



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

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



下标 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Base -1 4 4 0 0 0 0 4 -9 4 -11 -12 -4 -14

Check 0 0 0 0 0 0 0 2 2 2 3 8 10 13

词缀 啊 阿 埃 阿根 阿胶 阿拉 埃及 阿根廷 阿拉伯 阿拉伯人

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



二、 基本操作与存在问题



1&＃xff0c; 查询

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



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



2&＃xff0c; 插入与删除

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



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



例如说&＃xff0c;如果&＃xff02;阿拉根&＃xff02;某一天也成为了一个词&＃xff0c;我们要在trie树中插入这一状态。按计算它的位置应在&＃xff18;&＃xff0c;但8是一个已成状态&＃xff0e;所以我们得重新确定&＃xff02;阿拉&＃xff02;这一最大已成前缀状态的BASE值&＃xff0e;重新扫描得出BASE[10]&＃61;11。这样状态&＃xff11;&＃xff15;为&＃xff02;阿拉根&＃xff02;&＃xff0c;且BASE[15]为负&＃xff08;成词&＃xff09;&＃xff0c;CHECK[15]&＃61;10&＃xff1b;状态&＃xff12;&＃xff10;为&＃xff02;阿拉佰&＃xff02;&＃xff0c;且BASE[20]&＃61;-4&＃xff0c;CHECK&＃61;10。



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



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



三、 简单优化



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



1&＃xff0c; 插入优化

在插入需要确定新的BASE值时&＃xff0c;我们是只需要遍历空状态的。非空状态的出现意味着某个BASE值尝试的打败&＃xff0c;我们可以完全不必理会。所以&＃xff0c;我们可以对所有的空状态构建一个序列&＃xff0c;在确定BASE值时只需要扫描该序列即可。

对双数组中的空状态的递增结点r1,r2, …, rm&＃xff0c;我们可以这样构建这一空序列&＃xff1a;

CHECK[ri]&＃61;−ri&＃43;1 (1 i m−1),

CHECK[rm]&＃61;−(DA_SIZE&＃43;1)

其中r1&＃61; E_HEAD&＃xff0c;为第一个空值状态对应的索引点。这样我们在确定BASE值时只需扫描这一序列即可。这样就省去了对非空状态的访问时间。



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



2&＃xff0c; 删除优化

1) 无用结点

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



2) 数组长度的压缩

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