Trie

树?图?AC?

Posted by Monad on February 12, 2018

Trie 树

定义

Trie 树,又称“字典树”,是一种可以进行字符串快速匹配的多叉树结构。它有一个空的根节点,它的信息储存在边上,而不是点上。所以字符串不是直接储存在它的节点中,而是由节点所在的位置决定。

一棵正常的 Trie

注意:点中的单词不是节点中储存的内容,而是为了便于理解才标出来的。

如上图所示是一棵 Trie 树,它储存了三个单词:car, cat, cut。可以看到,一个点所表示的单词,是从根节点到达它该节点所经过的边的字母所组成的单词。
Trie 树非常好理解,对吧?Trie 树试了可以储存字符串之外,还可以储存一个数列等的有序排列,也可以用来求两个单词的公共前缀长度。定义一棵 Trie 并实现插入Insert()、搜索Search()方法也很简单。

struct NODE { NODE *next[26], *father, *suffix; int cnt; char c; } root, pool[MAX_SIZE];
int cur_node = 0;

void Insert(NODE *node, const char *st) {
    for (int i=0; st[i]; i++) {
        NODE *&next = node->next[ st[i]-'a' ];
        if (!next) {                     // 如果没有,则新建一个
            next = pool + (cur_node++);
            next -> father = node;
            next -> c = st[i];
        }
        node = next;
    }
    node->cnt ++;
}

int Search(NODE *node, const char *st) {
    for (int i=0; st[i]; i++) {
        node = node->next[ st[i]-'a' ];
        if (!node) return false;
    }
    return node->cnt;
}
// Usage: Insert(&root, "something");
//        Search(&root, "something");

Trie 树的妙用

例题:The XOR Largest Pair (出自《算法竞赛进阶指南》)
给定 N 个整数 $A_1$, $A_2$, …, $A_N$,从中选出两个进行 xor(异或)运算,求最大结果是多少?$N \leq 10^5$, $0 \leq A_i < 2^{31}$。

首先我们可以枚举两个数i, ji < j),然后求出 $A_i\ xor\ A_j$ 的最大值。但是这样做的时间复杂度是$O(N^2)$,会TLE。
更好的办法是,可以把这 N 个数看成 N 个32位的二进制数,然后把它们的01串插入 Trie 树中。因为要使 xor 的结果尽可能大,所以我们要尽可能地让两个数的最高位不同。 要求另一个数,使它与已知数进行异或得出的最大结果,我们可以从根节点出发,尽量沿着与已知数不同的二进制位走下去(如果没有不同,只能走相同的),所得出的数就是能使异或运算得到最大值的数。 我们只要枚举一个数i,在 Trie 中找出一个数j,使$A_i$ xor $j$的结果最大,然后把所有结果取一个 max 即可。时间复杂度为$O(32N)$。

Trie 图

要理解 Trie 图,建议先看 Ghastlcon 的 DFA 自动机

序言

Trie 树,很简单对吧?(坏笑)那么 Trie 图就有你好受了(坏笑×2)。Trie 树,是一种确定有限状态自动机(DFA)。是的,你没有看错,就是字典树变成了自动机。好了,吐槽完毕,下面进入正经部分(笑)。
Trie 图是在 Trie 树的基础上多连一些边,然后就可以用来解决多字符串匹配问题。
如果我们直接用 Trie 树来匹配字符串S,我们可以枚举子串的起始位置,然后在 Trie 中匹配。不过一旦匹配不成功,我们就只能往后移动一位,跟两个字符串匹配的暴力做法差不多。
那么,既然在两个字符串匹配中,KMP 可以在失配的时候利用当前信息继续高效匹配,那么 Trie 树可不可以效仿这种做法呢?

构图

这种做法就是把 Trie 树改造成 Trie 图(DFA),然后把原串放在上面跑,就可以得出结果了。那么要如何改造呢?

原 Trie 树 如上图所示,这棵 Trie 储存了三个单词:cert, erro, erec。然后现在我们有一个字符串cerror。现在要搜索cerror是否包含这三个单词。
对于第一个字符串cerror,当我们匹配到cer时,我们就走到了第 3 号节点;然后遇到了字符r时,没有路径可以走下去,那怎么办呢?重新来?
为了方便,我们定义 trie 树中从根结点到某个结点的路径上的边上的字符连起来形成的字符串为这个结点的路径字符串

去除没有用的字符 其实第 3 号节点没有r这个孩子,这说明了没有一个关键词是cerr或是以cerr为前缀的。所以此时cerrc就是多余的,没有必要保留,只需要保留err即可。
所以现在就要转移以err为路径字符串的节点(更准确地说是err的后缀)(如果没有,则跳回根节点)。但是如何快速找到这个节点呢?

后缀节点

我们定义一个结点的路径字符串的后缀对应的结点为它的后缀结点,这样定义的节点可能有多个,我们取后缀最长的节点为后缀节点。
我们可以预处理每一个节点的后缀节点。首先,根节点和第二层节点的后缀节点就是根节点,这是边界。然后其他节点的后缀节点可以分解为子问题。

后缀节点的子问题 如图所示是某个节点的路径字符串,设当前节点为K。因为到达K需要经过x这个字符,所以它的后缀节点一定有一条x边,并且其路径字符串一定是K的路径字符串去掉x的后缀。
所以把上述条件整合一下,就可以得出一下步骤:首先临时定义点SK的父节点的后缀节点,然后如果S没有x边,就一直取S为它的后缀节点,直到S为根节点或Sx边。
为了使前面的节点处于已经求好的状态,这里预处理最好采用 BFS 顺序。

那么我们再回到上面那个问题,我们可以找到 3 的后缀节点为 6,6 有一条r边指向 7(如果没有x边,则继续找其后缀节点)。
所以我们从 7 开始匹配,遇到了o,走到 8,匹配成功。

统计数量

如果把上面的例题改成求包含指定单词中的多少个,那又怎么办呢?
我们可以对于每一个走到的节点,(用一个新变量)回溯其后缀节点,把这些节点的cnt值累加入答案中,然后设置为已访问即可。

总结步骤

预处理后缀节点
  1. 根节点和第二层节点的后缀节点就是根节点(这是边界);
  2. 对于其他某个节点K,我们可以临时定义SK的父节点的后缀节点,c为到达K的边的字符,然后如果S没有c边,就一直取S为它的后缀节点,直到S为根节点或Sc边。

求后缀节点的代码如下:

void InitSuffix(NODE *root) {
    deque<NODE*> q;
    NODE *cur, *p;

    q.push_back(root);
    while (!q.empty()) {
        cur = q.front();
        q.pop_front();

        if (cur == root || cur->father == root)   // 边界
            cur->suffix = root;
        else {
            int c = cur->c - 'a';
            p = cur->father->suffix;              // 子问题
            while (!p->next[c] && p != root) // 继续找后缀节点
                p = p -> suffix;
            cur->suffix = p->next[c]? p->next[c] : root;
        }

        for (int i=0; i<26; i++)                  // BFS
            if (cur->next[i])
                q.push_back(cur->next[i]);
    }
}
匹配过程

设原串为S,当前字符为c,当前节点为T。首先从根节点出发。

  1. 如果Tc节点,则走向c节点;
  2. 否则,一直寻找其后缀节点(与“预处理后缀节点”差不多),直到根节点或该节点有c孩子。
  3. 然后对于每一个走到的节点,(用一个新变量)回溯其后缀节点,把这些节点的cnt值累加入答案中,然后设置为已访问。

代码如下:

int Search(NODE *root, const char *str) {
	int cnt = 0;
	NODE *cur = root;                        // 从根节点开始
	for (int i=0, c; str[i]; i++) {
		c = str[i] - 'a';
		while (!cur->next[c] && cur != root) // 继续找后缀节点
			cur = cur -> suffix;
		cur = cur -> next[c];
		cur = cur? cur : root;

		// 统计数量
		for (NODE *tmp = cur; tmp != root && tmp->cnt != -1; tmp = tmp->suffix) {
			cnt += tmp -> cnt;
			tmp -> cnt = -1;
		}
	}
	return cnt;
}

时空复杂度

设关键词总长度为$L_1$,文本(被搜索的内容)的长度为$L_2$。

空间复杂度

如上面的代码所示,申请内存的只有Insert(),申请的数量为 Trie 树的总结点数,最坏为$L_1$。所以空间复杂度为$O(L_1C)$(C为字符集的字符数量)。
当然,我们没有必要每个节点储存 C 条边。如果只储存有用边,那么边的总数就是点的数量,所以优化后的空间复杂度为$O(L_1)$。

时间复杂度

先说结论吧,Trie 图的时间复杂度是$O(L_1 + L_2)$。
首先while循环可以会造成一定的错觉。while循环是用来找下一步到哪个节点,为了方便,我们把while循环简称为child(node, c)函数,也就是找nodec孩子。
那么我们要研究的就是child()的时间复杂度。并且child()每执行一次一定至少往上走 1 层。

  1. 建图过程:建图过程无非是求后缀节点的过程,所以对于每个节点,child回溯的次数不会超过树的深度(通常情况下不大),可看作一个常数;
  2. 搜索过程:如果把搜索过程看成是一个光标在图中漫游的过程,那么光标要不往下走,要不往上走,而且只有往上走才有可能重复执行child()。那么child()总共最多会执行$L_2$次。

所以其时间复杂度是$O(L_1 + L_2)$

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可,转载请注明:“转载自:Trie