发掘双数组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,只需要一个整数,对于有 n 个状态的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代表的那个字符串。只需要这样:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
string get_string(uint stateID) const { uint child = stateID; string str; while (0 != child) { // 0 is root uint parent = states[child].check; uint first_child = states[parent].base; byte label = child - first_child; str.push_back(label); child = parent; } reverse(str.begin(), str.end()); return str; } |
可以看出, 这个函数非常高效,从而,我们既可以用 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 实在是差得太多了。