DoubleArrayTrie(一)

1 双数组Tire树简介

双数组Tire树是Tire树的升级版&＃xff0c;Tire取自英文Retrieval中的一部分&＃xff0c;即检索树&＃xff0c;又称作字典树或者键树。下面简单介绍一下Tire树。

1.1 Tire树

Trie是一种高效的索引方法&＃xff0c;它实际上是一种确定有限自动机(DFA)&＃xff0c;在树的结构中&＃xff0c;每一个结点对应一个DFA状态&＃xff0c;每一个从父结点指向子结点(有向)标记的边对应一个DFA转换。遍历从根结点开始&＃xff0c;然后从head到tail&＃xff0c;由关键词(本想译成键字符串&＃xff0c;感太别扭)的每个字符来决定下一个状态&＃xff0c;标记有相同字符的边被选中做移动。注意每次这种移动会从关键词中消耗一个字符并走向树的下一层&＃xff0c;如果这个关键字符串空了&＃xff0c;并且走到了叶子结点&＃xff0c;那么我们达到了这个关键词的出口。如果我们被困在了一点结点&＃xff0c;比如因为没有分枝被标记为当前我们有的字符&＃xff0c;或是因为关键字符串在中间结点就空了&＃xff0c;这表示关键字符串没有被trie认出来。图1.1.1即是一颗Tire树&＃xff0c;其由字典{AC,ACE,ACFF,AD,CD,CF,ZQ}构成。

图1.1.1

图中R表示根节点&＃xff0c;并不代表字符&＃xff0c;除根节点外每一个节点都只包含一个字符。从根节点到图中绿色节点&＃xff0c;路径上经过的字符连接起来&＃xff0c;为该节点对应的字符串。绿色叶节点的数字代表其在字典中的位置

1.2 Tire树的用途

Tire树核心思想是空间换取时间&＃xff0c;利用字符串的公共前缀来节省查询时间&＃xff0c;常用于统计与排序大量字符串。其查询的时间复杂度是O&＃xff08;L&＃xff09;&＃xff0c;只与待查询串的长度相关。所以其有广泛的应用&＃xff0c;下边简单介绍下Tire树的用途

 Tire用于统计&＃xff1a;

 题目&＃xff1a;给你100000个长度不超过10的单词。对于每一个单词&＃xff0c;我们要判断他出没出现过&＃xff0c;如果出现了&＃xff0c;求第一次出现在第几个位置。

 解法 &＃xff1a;从第一个单词开始构造Tire树&＃xff0c;Tire树包含两字段&＃xff0c;字符与位置&＃xff0c;对于非结尾字符&＃xff0c;其位置标0&＃xff0c;结尾字符&＃xff0c;标注在100000个单词词表中的位置。对词表建造Tire树&＃xff0c;对每个词检索到词尾&＃xff0c;若词尾的数字字段>0,表示单词已经在之前出现过&＃xff0c;否则建立结尾字符标志&＃xff0c;下次出现即可得知其首次出现位置&＃xff0c;便利词表即可依次计算出每个单词首次出现位置复杂度为O&＃xff08;N×L&＃xff09;L为最长单词长度&＃xff0c;N为词表大小

 Tire用于排序

 题目&＃xff1a;对10000个英文名按字典顺序排序

 解法&＃xff1a;建造Tire树&＃xff0c;先序便利即可得到结果。

1.3 针对Tire树的改进

Tire树虽然很完美&＃xff0c;但缺点是空间的利用率很低&＃xff0c;比如建立一颗ASCII的Tire树&＃xff0c;每个节点的指针域为256&＃xff0c;这样每个节点既有256个指针域&＃xff0c;即使子节点置空&＃xff0c;仍会有空间占用问题&＃xff0c;解决办法是动态数组Tire树&＃xff0c;即对子节点分配动态数组&＃xff0c;生成子节点则动态扩大数组容量&＃xff0c;这样便能有效的利用空间。

出于对Tire树占用空间的更有效利用&＃xff0c;便引入了今天的主题&＃xff1a;双数组Tire树&＃xff0c;顾名思义&＃xff0c;即把Tire树压缩到两个数组中。

双数组Tire树拥有Tire树的所有优点&＃xff0c;而且刻服了Tire树浪费空间的不足&＃xff0c;使其应用范围更加广泛&＃xff0c;例如词法分析器&＃xff0c;图书搜索&＃xff0c;拼写检查&＃xff0c;常用单词过滤器&＃xff0c;自然语言处理 中的字典构建等等。在基于字典的分词方法中&＃xff0c;许多开源

的实现都采用了双数组Tire树。

2 构造双数组Tire树

下面不如本文的主题双数组Tire树&＃xff0c;其基本观念是压缩trie树&＃xff0c;使用两个一维数组BASE和CHECK来表示整个树。双数组缺点在于&＃xff1a;构造调整过程中&＃xff0c;每个状态都依赖于其他状态&＃xff0c;所以当在词典中插入或删除词语的时候&＃xff0c;往往需要对双数组结构进行全局调整,灵活性能较差。 但对与&＃xff0c;这个缺点是可以忽略的&＃xff0c;因为核心词典已经预先建立好并且有序的&＃xff0c;并且不会添加或删除新词&＃xff0c;所以插入时不会产生冲突。所以常用双数组Tire树来载入整个核心分词词典。

　2.1 双数组的构造

Tire树终究是一颗树形结构&＃xff0c;树形结构的两个重要要素便是前驱和后继&＃xff0c;把Tire树压缩到双数组中&＃xff0c;只需要保持能查询到每个节点的前驱和后继即可。Tire树中几个重要的概念

STATE&＃xff1a;状态&＃xff0c;实际为在数组中的下标 

CODE &＃xff1a; 状态转移值&＃xff0c;实际为转移字符的 ASCII码

BASE  &＃xff1a;表示后继节点的基地址的数组&＃xff0c;叶子节点没有后继&＃xff0c;标识为字符序列的结尾标志

CHECK&＃xff1a;标识前驱节点的地址

在DAT的构造过程当中&＃xff0c;一般有两种构造方法&＃xff1a;

1 动态输入词语&＃xff0c;动态构造双数组。

定义2. 对于一个接收字符c从状态s移动到t的转移&＃xff0c;在双数组中保存的条件是&＃xff1a;

check[base[s] &＃43; c] &＃61; s

base[s] &＃43; c &＃61; t

以上为双数组中的核心转移公式&＃xff0c;公式中s 和 t 均为状态state  

对于新插入字符串c1c2...cn

树的构造过程如下&＃xff0c;由根节点开始&＃xff0c;加入到树中&＃xff0c;加入方法即如上所述的状态转移方法。

base[root] &＃43; c1 .code&＃61; t1 &＃xff0c;check[t1] &＃61; root 

base[t1] &＃43; c2.code &＃61; t2 , check[t2] &＃61; t1

 ....

base[tn-1] &＃43; cn .code &＃61; tn , check[tn] &＃61; tn-1

公式中的root ti 即为 状态state&＃xff0c;也就是在数组中的下标&＃xff0c;如图2.1.2所示

图2.1.1

root的base值一般是给定的&＃xff0c;假定root在在位置0&＃xff0c;base[root] &＃61; base[0] &＃61; 1

假设插入字符串AB&＃xff0c; base[root]&＃43; &＃39;A&＃39;.code &＃61; 1&＃43;65 &＃61; 66,check[66] &＃61; 1,即 t1 &＃61; 66&＃xff0c;然后base[t1] &＃43;&＃39;B&＃39;.code &＃61; t2 ,因为t2  可能被占用&＃xff0c;所以要确保t2 的check值为空&＃xff0c;即没有父节点&＃xff0c;即插入 &＃39;B&＃39; 的就要在CHECK数组中找到一个空位置&＃xff0c;即找到使check[base[t1]&＃43;&＃39;B&＃39;.code] &＃61; 0的值begin&＃xff0c;另base[t1]&＃61;begin , base[t1]&＃43;&＃39;B&＃39;.code即为状态t2&＃xff0c;另check[t2] &＃61; t1即可。

接下来依次插入其他字符序列&＃xff0c;不同于静态构造&＃xff0c;动态构造的插入过程中注意产生冲突的问题&＃xff0c;比如现在Tire树由{AB&＃xff0c;AC}构成&＃xff0c;当插入AD时

首先要要找一个状态t为B C的基地址&＃xff0c;若check[base[t]&＃43;&＃39;D&＃39;.code]  !&＃61; 0,即base[t]可以作为BC基地址&＃xff0c;而作为BCD的基地址却产生了冲突&＃xff0c;因为base[t]&＃43;&＃39;D&＃39;.code已经被占用&＃xff0c;解决办法是重新选择base[A]&＃xff0c;重新寻找base[t],使得check[base[t]&＃43;&＃39;B&＃39;.code] &＃61; check[base[t]&＃43;&＃39;C&＃39;.code] &＃61; check[base[t]&＃43;&＃39;D&＃39;.code] &＃61; 0 即找到三个空位置重新放置三个子节点&＃xff0c;可完成动态构造Tire树。 

2 已知所有词语&＃xff0c;静态构造双数组&＃xff1b;

这就是本文的重点了&＃xff0c;静态构造Tire树&＃xff0c;一般双数组的实现都会对算法做一个改进&＃xff0c;下面的算法讲解主要参考开源实现dart-clone&＃xff0c;dart-clone 也对双数组算法做了一个改进&＃xff0c;即

base[s] &＃43;c &＃61; t

check[t] &＃61; base[s]

不是原来的check[t] &＃61; s , 构造过程是 对于一组待插入的序列c1...cn,找到一个begin值&＃xff0c;使得 begin&＃43;c1.code...begin&＃43;cn.code &＃61; t1 ... tn ,check[t1] ... check[tn] &＃61; base[s] &＃61; begin 即为c1...cn的基地址&＃xff0c;而不是原来的 check[t &＃61;]s &＃xff0c;所以指向父节点的指针不是指向上一个状态&＃xff0c;而是上一个状态s的base值  base[s],那么问题来了一个base[s]值只能作为一组children的基地址&＃xff0c;若现在有第二组children也可以用base[s]作为基地址&＃xff0c;如何防止这种冲突呢&＃xff0c;解决方法就是做一个boolean数组 used[],一旦base[s]作为某组children的基地址&＃xff0c;used[base[s]] &＃61; true&＃xff0c;若产生冲突发现used[base[s]] &＃61; true&＃xff0c;则说明已经作为父节点&＃xff0c;则第二组children再重新寻找新的begin值。

dart-clone的另一个改进是另字符的code &＃61; ASCII&＃43;1&＃xff0c;下面就是静态构造过程了&＃xff0c;构造中首先要有一个字典&＃xff0c;包含所有字符序列&＃xff0c;并且一般情况下不会对构造完成的Tire树插入新字符序列

对于由Dic &＃61; { AC,ACE,ACFF,AD,CD,CF,ZQ }构成的Tire树&＃xff0c;其双数组如图2.1.1所示&＃xff1a;由 dart-clone 生成的结果&＃xff1a;

图2.1.1

其中i是下标&＃xff0c;即为state&＃xff0c;这里根据下标i可以看出BASE与CHECK数组的长度均达到了144&＃xff0c;本图中只显示了BASE与CHECK中不为0的信息。

构造过程

1 建立根节点root,令base[root] &＃61;1

2 找出root的子节点 集{root.childreni }(i &＃61; 1...n) , 使得 check[root.childreni ] &＃61; base[root] &＃61; 1

3 对 each element in  root.children : 

　　1&＃xff09;找到{elemenet.childreni }(i &＃61; 1...n) &＃xff0c;注意若一个字符位于字符序列的结尾&＃xff0c;则其孩子节点包括一个空节点&＃xff0c;其code值设置为0找到一个值begin使得每一个check[ begini &＃43; element.childreni.code] &＃61; 0

　　2&＃xff09;设置base[element.childreni] &＃61; begini

　　3&＃xff09;对element.childreni 递归执行步骤3&＃xff0c;若遍历到某个element&＃xff0c;其没有children&＃xff0c;即叶节点&＃xff0c;则设置base[element]为负值&＃xff08;一般为在字典中的index取负&＃xff09;

下面举一个实例&＃xff0c;对字典Dic &＃61; { AC,ACE,ACFF,AD,CD,CF,ZQ }建立Tire树&＃xff0c;图1.1.1展示了其树形结构

1 遍历字典&＃xff0c;找到root的所有children&＃xff0c;在Dic中为{A C Z}&＃xff0c;因为首次插入&＃xff0c;直接设置其三个子节点的check值&＃61;1 root经过A  C  Z 的作用分别到达三个状态 t1  t2  t3

状态t1由条件 ‘A’ 触发&＃xff0c;找到‘A’的子节点值{C D},找一个begin值&＃xff0c;使得check[begin &＃43; &＃39;C&＃39;.code] &＃61; check[begin &＃43;&＃39;D&＃39;,code] &＃61; 0,这里 base[t1] &＃61; begin &＃61; 2&＃xff0c;状态t1 &＃61;67,t1下一状态为t4 &＃61; base[t1]&＃43; &＃39;C&＃39;.code ,t5 &＃61; base[t2] &＃43;&＃39;D&＃39;.code

继续向下便利&＃xff0c;不断添加字符&＃xff0c;状态转移&＃xff0c;递归的对BASE与CHECK赋值&＃xff0c;注意叶节点没有儿子&＃xff0c;则设置其base值为-index , 最终便得到由两个数组表示的Tire树。

图2.1.2表示不同于图1.1.1&＃xff0c;图2.12.使用DFA的形式来描绘&＃xff0c;节点表示state&＃xff0c;字符作为转移条件&＃xff0c;不同字符触发不同的state&＃xff0c;由图可见&＃xff0c;一个转移状态对应一个state&＃xff0c;在实现过程中&＃xff0c;可以把2者结合起来&＃xff0c;图2.1.2就会变成图1.1.1的形式了

图2.1.2

注意&＃xff1a;对于叶节点leaf.code &＃61; 0&＃xff0c;标识为词尾

1 对于有相同父节点的children&＃xff0c;其有相同的基地址值&＃xff0c;如状态 67 69 92的check值&＃61; base[root] &＃61; 1

2 每个节点表示一个状态&＃xff0c;子节点的check值即为父节点的base值

3 叶子节点的code值为0&＃xff0c;叶子节点代表一个字符序列的结尾 且base[leaf] &＃61; -index

4 对于depth &＃61; 2 的节点 其基地址为1 &＃xff0c;1&＃43;&＃39;A&＃39;.code  1&＃43;&＃39;B&＃39;.code  1&＃43;&＃39;C&＃39;.code 为三个状态在数组中的位置 分别为 67 69 92

5 对叶节点tleaf , check[tleaf] &＃61; tleaf&＃xff0c; 因为到叶节点的转移字符leaf.code &＃61; 0,寻找begin值时&＃xff0c;begin &＃43; leaf.code &＃61;tleaf ,check[begin&＃43; leaf.code] &＃61; begin &＃xff0c; 由于leaf.code &＃61; 0 , 则有begin &＃61; tleaf&＃xff0c;即check[tleaf] &＃61; tleaf

　2.2Tire树的查询

有了如上的构建过程&＃xff0c;查询就会变的很easy

只需牢记&＃xff1a;

base[s] &＃43; c &＃61; t

check[t] &＃61; base[s] 

当有 base[s] &＃61;&＃61; t 时说明 c&＃61;0 &＃xff0c;即遇到了叶子节点&＃xff0c;这时&＃xff0c;记录下其位置index&＃xff0c;然后输出Dic[index]即为匹配出来的dic中的词