Double Array Trie

提到Trie应该都不陌生,它是一种常用词语检索的高效数据结构,通过聚合前缀节省空间。Trie的节点中保存子节点的方式可以通过数组或者链表,数组的大小需要覆盖所有的字符,而使用链表需要利用map映射,但是map本身也会存在一定的空间浪费,当然也有人考虑使用链表来保存,但是那样却会使检索的时间复杂度增加。一棵典型的Trie Tree的结构如下所示:

而DAT(Double Array Trie)则结合了Array和List的特点,实现查询效率和存储空间的双赢。DAT本质是确定有限自动机(Deterministic Finite Automaton ,DFA), 意思就是状态有限,且给定当前状态和转移变量时,下一个状态也就唯一被确定了。假设我们现在有个字典,字典中的所有的字符是转移变量,这些字符所有的前缀(包括自己本身)就是状态.

Double Array Trie具体是通过base和check两个数组来实现,base数组用来存储当前状态,以便进行状态转移,base[i]为负则表示该节点为终止状态;check数据则用来表示当前状态的前驱状态。但是仅仅依靠base数组,是无法实现判断字符串是否在词典中的,因为有可能存在一个不在词典中的字符,使得其状态转移到一个叶子节点上,比如说转移到某个节点s1, 也存在另外一个节点s2,其base[s2]为负,那么如果s1的转移变量编码为s2-base[s1]时,即使这个转移变量代表的字符不在词典中,那么整个字符串也会被认为是在词典中,明显就不符合预期,所以需要check数组对当前状态的前置状态进行限定,使得这个过程被唯一确定!

对于当前状态s, 以及字符的编码(也称之为变量)c, base和check数组有如下的转移关系(转移是在原始的trie树中进行的,节点表示当前状态,边可以表示转移条件,但是这棵trie树在base和check数组的生成过程中并没有保存)

base[s] + c = t
check[t] = base[s]

并且从当前状态转移的所有的状态的check值都相同。正常来讲,base数组和check数组的值可以是任意值,只要保证对应的约束条件即可,所以可以在生成trie树的过程中对base和check数组进行赋值.

对于当前的节点(状态为s),从1开始枚举,直到找到一个begin,使得check[begin+c]=0, c为当前节点的转移变量(理解为trie树某个节点与所有子节点之间的边),然后将begin赋值为check[begin+c], 也即check[begin+c] = begin, 另外对于叶子节点,编码设置为0,从而有check[begin]=begin, 所以在匹配的过程中可以通过check[i]是否等于i判断当前状态是否匹配成功,并且有base[s] = begin. 那么这个过程该怎么实现呢?

在实现base和check数组的生成过程中,需要对trie树的词典进行字典序,从而可以通过left,right两个指针(表示词典词汇的索引)来表示所有以根节点到当前节点的字符串为前缀的词典数据,假设词典中有如下数据:

一举
一举一动
一举成名
一举成名天下知
万能
万能胶

那么对于根节点,其left=0,right=6;对于『一』所转移的节点,其left=0,right=4;定义trie的节点为:

参考资料

双数组Trie树(DoubleArrayTrie)Java实现

Double Array Trie

Leave a Reply

Your email address will not be published. Required fields are marked *