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

作者: rockeet 发表日期: 2014年12月20日分类: 算法, 自动机评论: 0 条阅读次数: 12,511 次

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

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

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

要表示一个图，我们首先要给状态定义一些属性，当然，转移也有属性（表1）：

struct State {
    bool is_final;
    set<Transition> children;
};

struct State {

bool is_final;

set<Transition> children;

};

struct Transition {
    LabelCharacter  label;
    StateIdentifier target;
};

struct Transition {

LabelCharacter label;

StateIdentifier target;

};

其中 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%以上)，从而，就会有一些空洞无法利用。

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

struct State {
    uint base     : 31;
    uint is_final :  1;
    uint check    : 31;
    uint is_free  :  1;
};

struct State {

uint base : 31;

uint is_final : 1;

uint check : 31;

uint is_free : 1;

};

class DoubleArrayTrie {
    vector<State> states;
public:
    uint state_move(uint curr, byte ch) const {
        uint target = states[curr].base + ch;
        if (states[target].check == curr)
             return target;
        else return nil;
    }
};

class DoubleArrayTrie {

vector<State> states;

public:

uint state_move(uint curr, byte ch) const {

uint target = states[curr].base + ch;

if (states[target].check == curr)

return target;

else return nil;

}

};

base 和 check

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

其实，base 本质上相当于（表1）中的State::children；check 就是 parent，但是在（表1）中没有对应的东西。

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

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;
}

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 实在是差得太多了。