发掘双数组Trie (Double Array Trie)的能力

描述 Double Array Trie 的文章有很多,我在这里从另一个视角来讲 Double Array Trie。首先,是 base 和 check 的更深层含义,然后再详细说一下由此引申出来的问题。

Double Array Trie 其实就是一个树形自动机(DFA),既然是自动机,最基本的概念就是状态转移,套用的概念,状态就是结点,转移就是

不过DFA比图要多出来一点东西:状态/结点终止状态与非终止状态的区分,转移/边上有label,这个label唯一标识同一个Source结点的边集中的一员。

要表示一个图,我们首先要给状态定义一些属性,当然,转移也有属性(表1):

其中 LabelCharacter 一般是 byte, 而 StateIdentifier 只要能标识图的结点(Vertex)就可以了,不管使用哪种方式,比如可以用指针(C/C++等),或者对象引用(Java等)。
但实际上,要最简洁高效的表达StateIdentifier,只需要一个整数,对于有 个状态的DFA,这个整数的取值范围是 [0, n)

另一方面,对于一个树形的图:  VertexNum = EdgeNum + 1

Double Array Trie 回顾

在 Double Array Trie 中,StateIdentifier 就是用上面说的整数来表达的,不过有一点需要注意:Double Array Trie 是填不满的(虽然填充率通常都高达99%以上),从而,就会有一些空洞无法利用。

这里只有文字说明,因为搞一堆图实在太麻烦了。用这个简短的代码来说明:

base 和 check

base 和 check 是 Double Array Trie 的标准术语,以至于很少有人去思考它们的其它意义。

其实,base 本质上相当于(表1)中的State::children;check 就是 parent,但是在(表1)中没有对应的东西。

正是 check/parent,使得 DoubleArrayTrie 有了一种新的能力:反向搜索!具体地说,就是:给定一个StateID,可以得到这个StateID代表的那个字符串。只需要这样:

可以看出, 这个函数非常高效,从而,我们既可以用 Double Array Trie 把字符串映射到整数(进一步就可以实现Map<string,value>),也可以用整数(StateID)还原其对应的字符串。

Patricia Trie

在一般的 Trie 中,有大量的结点只有一个child,这浪费了很多空间,Patriacia Trie 把这种相邻的且只有一个孩子的结点压缩成一个结点,并把原先链接这些结点的边上的字符连接起来,形成一个字符串

更加乐观的是,一般情况下,Patriacia Trie 中所有的这些字符串 label中还有大量的冗余,怎么利用这一点呢?

三者结合:Double Array + StateID-to-String + Patricia

创建一个 Patriacia Trie,但是碰到那种字符串 label时,不保存字符串本身,而是保存一个整数,这个整数是另一个 Patriacia Trie 的 StateID,从 StateID,可以恢复出字符串 label。并且,这种方法还可以循环使用:

Trie1: strlabel is StateID of Trie2
Trie2: strlabel is StateID of Trie3
Trie3: strlabel is StateID of Trie4
……

这种思想用在 Double Array Trie 上,形式很优美,但是效果并不是很理想,因为省不了多少内存,甚至反而要用更多内存!

更紧凑的 Trie

有一种叫做 Rank-Select 的数据结构,在此之上实现一个包含 n 个结点的,这种结点之间的关系不是用指针(整数数组下标也是一种指针)表达的,内存需求只有 2.5*n bits,而基于指针的表达方式需要O(n*log(n)) bits。

如果给每条边再加上一个label,就是一个 Trie,总内存需求是 (8+2.5)*n。并且这种 Trie比 Double Array Trie 还有一些额外的查询能力。只不过速度比 Double Array Trie 要慢。

上面说的那种三者结合的数据结构,如果用这种 Trie 实现,就太完美了,nark 就实现了这种 trie,作为一种特殊的自动机,可以用来做数据库压缩!有个日本人也实现了这种Trie,还起了个 别样的名字:marisa-trie ,不过它的功能和性能比起 nark 实在是差得太多了。

作者:
该日志由 rockeet 于2014年12月20日发表在算法, 自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 发掘双数组Trie (Double Array Trie)的能力
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。