0%

Trie树

前言

之前写了kmp算法,后面一直想写一下其他几个会的字符串算法。

Trie树

Trie树一般也叫做字典树,前缀树。

基本情景

判断一个前缀或者一个单词是否在给定的多个词(词典)中出现过以及出现过多少次。

朴素做法是用该前缀/单词与词典中的每个词去做匹配
设模式串长度为m,文本串平均长度为l,与单个词匹配的复杂度为O(lm)(朴素匹配)或者O(l+m)(kmp)。
设词典中有n个词,则复杂度为O(n\
l*m)或者O(m+l*n)

假设将问题升级,变为q组查询,每次查询给出一个模式串。那么即使是kmp匹配方式的复杂度也要变为O(q*m+q*l*n).

比较直观的字典树

直接给出一个字典树,”abcd”,”ceef”, “abe”,”abeea”, “ccz”,”eg”.

alt

每个节点都代表一个字符串(由root结点遍历到当前结点形成的字符串)。

所有节点代表的字符串正好是字典中所有词汇的所有前缀。所以字典树又叫前缀树。

也可以理解为每个边代表一个字母,这样更像自动机,不过Trie树一般还是理解为节点代表字母。

字典树的建立.查询,删除

建立

字典树的建立实际上是向当前字典树插入新的单词的过程。单纯的字典树是可动态扩展的。

对于每个单词,由root结点开始向下走,逐个匹配单词的所有字母,若匹配到某个结点则向该结点转移。若是不匹配则新建结点并转移至该节点。直到新单词的所有字母匹配完毕。

在这个过程中可以适时的打一些标记来记录其他信息,如出现次数,这个节点是否为末尾节点。
最常用的标记就是末尾节点的标记和每个节点代表字符串出现次数的标记。

查询

查询的过程比较简单,实际上就是建立过程中匹配的过程,不过需要在匹配过程中结合结点相关信息做一些数据处理。
这部分因为查询内容的不同,所以一般都是变化的。

删除

很少见删除操作。而且根据删除的东西的不同(eg:删除以某个字符串为前缀的所有字符串,删除某个字符串一次,删除某个字符串),变化也比较大。在写的时候可能很容易写错可能造成漏删/多删。需要考虑清楚要清除哪些信息即可。

不同的实现方式

一般来说就分为两种实现形式,数组形式与结构体+指针的形式。
实际上,两种写法可以互相借鉴一部分东西,并不固定。甚至可以写成链式前向星的形式。

数组的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int M=26;
const int N=1e5+10;
int ch[N][26];
int num[N];
int val[N];
int root;
int cnt;
void init(){
cnt=0;
root=0;
memset(val,0,sizeof val);
memset(num,0,sizeof num);
}
void insert(char *str){
int s=root;
for(int i=0;str[i];++i)
{
int idx=str[i]-'a';
if(!ch[s][idx]){
ch[s][idx]=++cnt;
}
s=ch[s][idx];
num[s]++;
}
val[s]=1;
}

结构体+指针的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct TrieNode
{
int num;
int val;
TrieNode *next[26];
TrieNode()
{
val = 0;
num = 0;
memset(next, 0, sizeof next);
}
} root;

void insert(char *a)
{
int k = 0;
TrieNode *p = &root;
while (a[k])
{
if (!p->next[a[k] - 'a'])
p->next[a[k] - 'a'] = new TrieNode;
p = p->next[a[k++] - 'a'];
p->num++;
}
p->val=1;
}

说明

  1. 结构体+指针的形式可以使用 new来动态分配内存,也可以像数组形式申请好需要的的空间大小。 如果动态分配内存则需要考虑释放的问题。如:

    1
    2
    3
    4
    5
    6
    7
    void Free(TrieNode *p)
    {
    for (int i = 0; i < 26; ++i)
    if (p->next[i])
    Free(p->next[i]);
    delete p;
    }
  2. 结点的数量考虑为最坏情况的 单词长度*单词数量。
    第二维根据可能出现的字母的种类,比如若全为小写则用26。
    另外选取了基准字母来方便访问数组中的值,基准字母的选择同理与字母种类。

  3. num值与val值的设置根据具体情况而定,可以根据插入时传入的参数来决定。

  4. 在新建一个节点前,必须保证其已经被初始化,若是动态分配内存则明显不需要考虑这一点。 在初始化的时候,可以全局清空,后面直接用就可以;也可以对要用的结点进行初始化即可。后者明显可以节省一些时间。

复杂度分析

在建立字典树的过程中,复杂度为O(N).N为总字母数。
查询的复杂度为O(len),len为查询串的长度

空间复杂度为O(M*N),M为字母种类

很明显字典树是一种空间换时间的方式,他对空间的消耗很大。
动态的初始化是很有必要的,不然会加上不少的时间。

当我们使用链式前向星的时候可以减少相当多的内存消耗,但是却在对某节点查询是否有给定字母的子节点时,时间消耗会加大。

其他

字典树还是非常简单的,但是它是Trie图与AC自动机的基础。
后缀自动机,回文树等也都是有类似的存储方式。