Trie 树原理及其敏感词过滤的实现

Trie 树也称为字典树、单词查找树,最大的特点就是共享字符串的公共前缀,这样可以达到节省空间的目的。像我们在使用搜索引擎输入某些关键字的时候,搜索引擎会自动弹出一些相关的信息,这些都是通过 Trie 树实现的。

Trie 树的数据结构

Trie 树的根节点不存任何数据,每个分支都代表一个完整的字符串。来看看 Trie 树的结构:

从上图可以归纳出Trie树的基本性质:

  1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
  2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符互不相同。
  4. 从第一字符开始有连续重复的字符只占用一个节点,比如上面的 to 和 ten,中重复的单词 t 只占用了一个节点。

从这几条基本性质我们可以抽象出节点的 class 属性:

  1. 是否为叶子节点的标志位 isWord。
  2. 既能存储当前节点的值也能存储其所有的子节点的数据结构HashMap。

先从稍微简单的实现开始

在 Java 中,Trie 树可以使用 HashMap 实现,因为一个节点的子节点个数未知,而 HashMap 可以动态扩展,而且可以在 O(1) 的时间复杂度内判断某个子节点是否存在。以 LeetCode 208 为例,来看看这种实现方式。

首先定义 Trie 树的节点,节点的结构为 HashMap,key 为字符串中的字符,value 为这个节点的子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TrieNode {

// 子节点(key是下级字符,value是下级节点)
private Map<Character, TrieNode> subNodes = new HashMap<>();

// 添加子节点
public void addSubNode(Character c, TrieNode subNode) {
subNodes.put(c, subNode);
}

// 获取子节点
public TrieNode getSubNode(Character c) {
return subNodes.get(c);
}
}

再来看看 Trie 树的主函数,在初始化树时,使用构造函数构造一个不存数据的根节点。在插入字符串时,从根节点开始判断树中是否已经包含了这个字符串的当前字符,如果不存在这个字符则新建节点保存当前字符,插入结束的时候设置结束标识,这里简单的用'#'来标记。

search() 和 startsWith() 函数也是类似,从根节点开始查找 HashMap 中是否存在对应的子节点。这两个函数的唯一区别是在字符串遍历完成的时候,search() 需要判断当前字符是否已经走到了 Trie 树的叶子节点,而 startsWith() 函数不需要。

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
37
38
39
40
41
42
43
44
45
46
47
class Trie {
TrieNode root;

/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}

/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curNode = this.root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode subNode = curNode.getSubNode(c);

// 如果没有这个节点则新建
if (subNode == null) {
subNode = new TrieNode();
curNode.addSubNode(c, subNode);
}
// 指向子节点,进入下一循环
curNode = subNode;
}
// 设置结束标识
curNode.addSubNode('#', new TrieNode());
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode curNode = this.root;
for (int i = 0; i < word.length(); i++) {
curNode = curNode.getSubNode(word.charAt(i));
if (curNode == null) return false;
}
return curNode.getSubNode('#') != null;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode curNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
curNode = curNode.getSubNode(prefix.charAt(i));
if (curNode == null) return false;
}
return true;
}
}

进一步实现敏感词过滤

在实现敏感词过滤前,首先需要初始化 Trie 树,将所有敏感词作为字符串全部插入到 Trie 树中。

其实原理还是和之前一样的,只不过相对于上面的代码来说,我们需要多增加一个指针。因为敏感词在字符串的位置我们是不知道的嘛,所以我们只能增加一个指针,对整个字符串进行遍历,寻找敏感词开始的位置,剩下的逻辑就和上面的代码相似了,如下图所示。这里假设在 Trie 树中已经初始化好了 bca、bcf、de 这几个敏感词。

首先 p1 指针指向 root,指针 p2 和 p3 指向字符串中的第一个字符。算法从字符 a 开始,检测有没有以 a 作为前缀的敏感词,在这里就直接判断 root 中有没有 a 这个子节点即可。没有的话将 p2 和 p3 同时右移,而如果存在以 a 作为前缀的敏感词,那么就只右移 p3 继续判断 p2 和 p3 之间的这个字符串是否是敏感词。如果在字符串中找到敏感词,那么可以用其他字符串如 * 代替。接下来不断循环直到整个字符串遍历完成就可以了。

这样的算法时间复杂度是多少呢?构建敏感词的时间复杂度是可以忽略不计的,因为构建完成后我们是可以无数次使用的。所以我们来看看查找敏感词的时间复杂度。如果字符串的长度为 n,而每个敏感词查找的时间复杂度是 O(m),我们需要对字符串遍历 n 遍,所以查找敏感词的这个过程的时间复杂度为 O(m * n)。