# 介绍
字典树(Trie)是一种树形数据结构,用于处理多模式串字符串匹配,解决字符串快速查找的问题
核心思想:利用字符串之间的公共前缀,将重复的前缀合并存储
# 实现 Trie
Trie 是一个多叉树,因此需要存储多个子节点
# 经典方式
通过数组来存储,每个字符对应到一个数组下标,每个下标存储相应的子节点(引用)
点此展开查看代码
class TrieNode {
public char data;
public TrieNode[] children = new TrieNode[26];
public boolean isData = false;
public TrieNode(char data) {
this.data = data;
}
}
public class Trie {
private TrieNode root = new TrieNode('/'); // Root node does not store data
public void insert(char[] text) {
TrieNode p = this.root;
for (char data : text) {
int idx = data - 'a';
if (p.children[idx] == null) {
p.children[idx] = new TrieNode(data);
}
p = p.children[idx];
}
p.isData = true;
}
public boolean find(char[] text) {
TrieNode p = this.root;
for (char data : text) {
int idx = data - 'a';
if (p.children[idx] == null) {
return false;
}
p = p.children[idx];
}
return p.isData;
}
}
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
27
28
29
30
31
32
33
34
35
36
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
27
28
29
30
31
32
33
34
35
36
效率分析:对于频繁的字符串查找,Trie 树非常高效
- 够建 Trie 树需要扫描所有的字符串(字符串集合),因此时间复杂度为 O(n),n 为所有字符串长度之和
- 够建成功后,每次查询只需要 O(k),k 为要查询的字符串长度,与 n 或者字符串集合里元素个数无关
内存消耗:Trie 树是一种空间换时间的数据结构,尽管通过存储相同的前缀子串,可以节省存储整个字符串集合的空间内存,但是每个节点都需要存储一个引用(指针)数组,当字符种类繁多,且集合中重复前缀并不多时,将会产生很大的内存浪费
# 优化方法
- 牺牲部分查询效率,将每个节点中的数组换成其他数据结构:跳表、散列表、红黑树等
- 缩点优化(压缩节点):对于只有一个子节点的节点,且此节点不是一个串的结束节点,可以将此节点与子节点压缩合并
# 对比散列表、红黑树
Trie 树适用的要求:
- 字符串集合的字符集不能太大 => 浪费存储空间,即使优化,也会降低效率
- 集合中重复的前缀子串比较多 => 否则同样浪费存储空间
- 数据存储不连续 => 缓存不友好
- 需要自己实现 => 容易出现问题
因此,对于精确匹配查找,工程中更常使用散列表和红黑树(无需自己实现,且效率也不低)。Trie 树更擅长前缀匹配查找
# AC 自动机
Trie 树与 AC 自动机的关系就像,朴素的单模式串匹配算法与 KMP 的关系一样,在 Trie 树的基础上添加了匹配失败时的 next 数组
// TODO