Trie树总结
阅读原文时间:2023年07月08日阅读:4

Trie,又经常叫前缀树,字典树等等。它有很多变种,如后缀树,Radix Tree/Trie,PATRICIA tree,以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。


定义

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

trie中的键通常是字符串,但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串位元,可以用于表示整数或者内存地址


基本性质

1.根节点不包含字符,除根节点意外每个节点只包含一个字符。

2.从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

3.每个节点的所有子节点包含的字符串不相同。


优点:

可以最大限度地减少无谓的字符串比较,故可以用于词频统计和大量字符串排序。

缺点: 虽然不同单词共享前缀,但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针(不包含卫星数据)。

应用场景:

(1) 字符串检索 事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。

1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。

(2)文本预测、自动完成,see also,拼写检查

(3)词频统计

若无内存限制:Trie + “k-大/小根堆”(k为要找到的数目)。

否则,先hash分段再对每一个段用hash(另一个hash函数)统计词频,再要么利用归并排序的某些特性(如partial_sort),要么利用某使用外存的方法。

(4)排序

Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。 比如给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

(5)字符串最长公共前缀

Trie树利用多个字符串的公共前缀来节省存储空间,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。

eg: 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?

解决方案:首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。 而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

  • 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;
  • 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;

(6)字符串搜索的前缀匹配

trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。 Trie树检索的时间复杂度可以做到n,n是要检索单词的长度, 如果使用暴力检索,需要指数级O(n^2)的时间复杂度。

(7) 作为其他数据结构和算法的辅助结构

如后缀树,AC自动机等(后缀树可以用于全文搜索


模板

题目

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e6 + 5;
int cnt = 1, Trie[MAXN][26];
int End[MAXN];

void Insert(char s[], int len) {
    int p = 1;
    for(int i = 0; i < len; i++) {
        int ch = s[i] - 'a';
        if(Trie[p][ch] == 0)
            Trie[p][ch] = ++cnt;
        p = Trie[p][ch];
    }
    End[p]++;
}

int search(char s[], int len) {
    int p = 1;
    for(int i = 0; i < len; i++) {
        int ch = s[i] - 'a';
        p = Trie[p][ch];
        if(!p)
            return false;
    }
    return End[p];
}

char st[MAXN], ask[MAXN];
int main() {
    int n, m;
    scanf ("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf ("%s", st);
        Insert(st, strlen(st));
    }
    for(int i = 1; i <= m; i++) {
        scanf ("%s", st);
        int len = 0, ans = 0;
        for(int j = 1; j <= strlen(st); j++)
            ans += search(st, j);
        printf("%d\n", ans);
    }
    return 0;
}