我的文章会先发布到个人博客后，再更新到简书，可以到个人博客或者gzh获取更多内容。
介绍
互联网在方便我们的同时，也不是不法之徒的“法外之地”。敏感词、文字过滤是手游或者互联网上必不可少的功能。正常的屏蔽字表现是基于一个屏蔽字库，里面有非常多的违禁关键词，但凡字库内的关键词出现在游戏内的文本中，会要求以*的方式替代。常用的算法有暴力算法、kmp算法、trie树和AC自动机。
- 暴力算法（也叫朴素算法）：是最简单易懂的一种算法，逐一比较字符串每一个字符与屏蔽词的字符进行匹配，存在一定的缺点，即存在时间复杂度极高的情况。
- KMP 算法是一种高效的字符串匹配算法，属于经典算法，是 D.E. Knuth、J.H. Morris 和 V.R. Pratt 三人在 1977 年相继发表的论文中提出的。 KMP 算法与暴力算法不同，主要是通过预处理模式串 (即常用的屏蔽词)，得出对应的数组 next 数组。它可以有效地减少匹配时不必要的字符比较次数。
- Trie 树: 又称字典树、前缀树，是一种有序树，是一种哈希树的变种。算法的核心就是建立一个加载了所有敏感词库的trie树，然后通过前缀匹配的方式在trie树中查找所有匹配的敏感词。
- AC 自动机: 一种基于Trie树的字符串匹配算法是，它的核心思想有点像是将trie树与kmp算法结合，在trie树的每个节点上增加失效指针，当关键字匹配失败后，通过失效指针跳另一个关键字进行非重复字段匹配, （例如设Trie树的单词cat匹配失败，但是在Trie树中存在另一个单词cart，失配指针就会指向前缀ca）。
本文主要介绍一下trie树和AC自动机算法。
trie树
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这
个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
维基百科
一颗保存了8个敏感词(我是你大爷、我是你哥哥、你大爷、中国、中国人、中国人民、中国人权、国之利刃)的trie树如下：
红色表示是否是一个敏感词的结束。
Trie 是一种高效的索引方法。在树结构中，每个节点对应一个字符，从父节点到有标记结束的子节点表示一个关键字。它的优势在于具有高效的查询和插入操作。具体的实现代码有多种，包括递归、迭代等多种形式，可以使用指针、数组、链表等不同方式进行实现。
golang实现
定义结构
定义两个结构体类型：TrieNode 和 Trie。TrieNode 表示 Trie 树中的一个节点，包含一个子节点映射（children）和一个标记（isEnd），用于指示这个节点是否代表了一个完整的单词。
//定义trie的节点与trie树
type TrieNode struct {
children map[rune]*TrieNode // 以unicode为key的子节点map
isEnd bool // 这个节点是否代表敏感词的结尾
}
type Trie struct {
root *TrieNode
}
func NewTrieNode() *TrieNode {
return &TrieNode{
children: make(map[rune]*TrieNode),
}
}
func NewTrie() *Trie {
return &Trie{
root: NewTrieNode(),
}
}
添加敏感词
AddWord 方法用于将单词添加到 Trie 树中。它遍历单词中的每个字符，将字符添加到 Trie 树中对应的节点的 children 映射中。如果节点不存在，则创建一个新的节点。最后，它将最后一个节点标记为 isEnd。
func (t *Trie) AddWord(word string) {
node := t.root
for _, c := range word {
if _, ok := node.children[c]; !ok {
node.children[c] = NewTrieNode()
}
node = node.children[c]
}
node.isEnd = true
}
匹配敏感词
isMatch 方法用于检查给定的字符序列是否匹配 Trie 树中的任何单词。它遍历字符序列，并检查每个字符是否对应 Trie 树中的节点。如果字符没有对应的节点，则返回匹配长度为零和匹配失败标记。如果找到一个节点，它将标记 find 设置为 true，并将匹配长度设置为该节点的深度加一。
// 匹配敏感词
func (t *Trie) isMatch(text []rune) (int, bool) {
find := false
var length int
node := t.root
for i, ch := range text {
child, ok := node.children[ch]
if !ok {
return length, find
}
node = child
if node.isEnd {
find = true
length = i + 1
}
}
return length, find
}
替换敏感词
Replace 方法用于替换文本中匹配 Trie 树中任何单词的部分。它将文本分解为单独的字符，然后遍历每个字符。对于每个字符，它检查以该字符为起点的所有可能的匹配，并将匹配替换为给定的替换字符。替换后的结果存储并返回。
func (t *Trie) Replace(text string, replace rune) string {
var result strings.Builder
tmp := []rune(text)
for i := 0; i < len(tmp); {
length, ok := t.isMatch(tmp[i:])
if !ok {
result.WriteRune(tmp[i])
i++
continue
}
for j := 0; j < length; j++ {
result.WriteRune(replace)
}
i += length
}
return result.String()
}
测试
func main() {
trie := NewTrie()
trie.AddWord("中国")
trie.AddWord("中国人")
trie.AddWord("中国小说网")
//res: 我是***国人民共和国公民
fmt.Println("res:", trie.Replace("我是中国人民共和国公民", '*'))
}
Aho-Corasick算法
Aho-Corasick算法是一种多模式匹配算法，用于在一个文本串中查找多个模式串。该算法由Alfred Aho和Margaret Corasick在1975年提出，是一个快速且高效的字符串匹配算法。Aho-Corasick算法使用了类似于Trie树的数据结构来存储所有的模式串，并利用BFS广度优先搜索的方法计算出每个节点的失败指针（也称为失配指针），即当某个字符无法匹配时，自动机应该转移到哪个状态继续匹配。
在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。该算法主要依靠构造一个有限状态机（类似于在一个trie树中添加失配指
针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设Trie树的单词cat匹配失败，但是在Trie树中存在另一个单词cart，失配指针就会指向前缀ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。
维基百科
构建失效指针示例
上面图一 8个敏感词构建的trie树，用ac算法改造一下加上失效指针后如下：
红色表示是否是一个敏感词的结束, 虚线表示trie节点的连接，蓝色实线表示失效指针的跳转（每个节点都有一个失效指针，没标明节点的失效指针都指向root节点）
golang实现
定义结构
创建一个 trie 数据结构来存储模式，相比原始TrieNode增加了失效指针
type TrieNode struct {
children map[rune]*TrieNode
fail *TrieNode
length int
}
func NewTrieNode() *TrieNode {
return &TrieNode{
children: make(map[rune]*TrieNode),
length: -1,
}
}
type ACAutomaton struct {
root *TrieNode
}
func NewACAutomaton() *ACAutomaton {
return &ACAutomaton{root: NewTrieNode()}
}
构件失效指针
用 BFS 遍历 trie 树中的所有节点，对于每个节点，将其与其祖先节点的 fail 指针构建链接，这样就可以在匹配时实现自动跳转。
func (ac *ACAutomaton) Build() {
queue := make([]*TrieNode, 0)
ac.root.fail = nil
queue = append(queue, ac.root)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for ch, child := range node.children {
failNode := node.fail
for failNode != nil && failNode.children[ch] == nil {
failNode = failNode.fail
}
if failNode == nil {
child.fail = ac.root
} else {
child.fail = failNode.children[ch]
}
queue = append(queue, child)
}
}
}
敏感词替换
在替换时，我们从 trie 树的根节点开始，根据文本中的字符进行跳转，如果到达某个节点后无法继续跳转，就将跳转到该节点的 fail 指针所指向的节点，如果到达某个节点后无法继续跳转并且该节点是某个模式串的末尾节点，并在匹配到字符串时用指定字符替换原来的字符串。
func (ac *ACAutomaton) Replace(text []rune, replace rune) string {
res := text
node := ac.root
for i, char := range text {
child, ok := node.children[char]
for node != ac.root && !ok {
node = node.fail
child, ok = node.children[char]
}
node = child
if node == nil {
node = ac.root
}
if node.length != -1 && i+1 >= node.length {
for j := i + 1 - node.length; j < i+1; j++ {
res[j] = replace
}
node = ac.root
}
}
return string(res)
}
测试
func main() {
ac := NewACAutomaton()
ac.AddWord("中国")
ac.AddWord("中国人")
ac.AddWord("中国小说网")
ac.Build()
//res: 我是***民共和国公民
fmt.Println("res:", ac.Replace("我是中国人民共和国公民", '*'))
}
两者对比
时间复杂度
Trie树和AC自动机都是字符串匹配算法中常用的数据结构，它们的时间复杂度有所不同。Trie树用于单模式串匹配，时间复杂度为O(m*L)，其中m为Trie树的节点数，L为模式串的长度。而AC自动机用于多模式串匹配，时间复杂度为O(n+Z)，其中n为文本串的长度，Z为所有模式串的长度之和。
AC自动机退化
极端情况下，AC算法模式串构造出的Trie的所有fail都指向的根节点，那么显然此时AC自动机与Trie做多模匹配时的时间开销一样。
但是考虑到实际业务中几乎不可能出现这种极端情况，AC自动机的效率相比Trie会高很多（尤其是在纯英文文本的多模匹配上）
测试
以下效率对比皆基于本人所在的项目组所使用的屏蔽词库
- 正常聊天文本长度（含敏感词）
//其中爸、妈、妈的、爸爸、妈妈、爷爷、奶、奶奶为敏感词
//testStr = "爸爸的爸爸叫爷爷爸爸的妈妈叫奶奶妈妈的妈妈叫外婆外婆也可以叫姥姥"
func BenchmarkAC_Replace(b *testing.B) {
//fmt.Println(a.Replace(testStr, '*'))
for i := 0; i < 100000; i++ {
(a.Replace(testStr, '*'))
}
}
func BenchmarkTrie_Replace(b *testing.B) {
//fmt.Println(t.Replace(testStr, '*'))
for i := 0; i < 100000; i++ {
(t.Replace(testStr, '*'))
}
}
//测试结果如下
//goos: linux
//goarch: amd64
//pkg: blog.chabon.site/blog/src
//cpu: Intel(R) Xeon(R) Silver 4216 CPU @ 2.10GHz
//BenchmarkAC_Replace-64 1000000000 0.1020 ns/op
//BenchmarkTrie_Replace-64 1000000000 0.1176 ns/op
- 正常聊天文本长度（不含敏感词）
//testStr2 = "我爱吃饭的事情大概大家都知道，我爱摸鱼的事情我觉得大家也都清楚的"
func BenchmarkAC_Replace2(b *testing.B) {
//fmt.Println(a.Replace(testStr2, '*'))
for i := 0; i < 100000; i++ {
//fmt.Println(a.Replace(testStr2, '*'))
(a.Replace(testStr2, '*'))
}
}
func BenchmarkTrie_Replace2(b *testing.B) {
//fmt.Println(t.Replace(testStr2, '*'))
for i := 0; i < 100000; i++ {
//fmt.Println(t.Replace(testStr2, '*'))
(t.Replace(testStr2, '*'))
}
}
//测试结果如下
//goos: linux
//goarch: amd64
//pkg: blog.chabon.site/blog/src
//cpu: Intel(R) Xeon(R) Silver 4216 CPU @ 2.10GHz
//BenchmarkAC_Replace2-64 1000000000 0.1095 ns/op
//BenchmarkTrie_Replace2-64 1000000000 0.1245 ns/op
由于只是简单案例测试一下，速度差别不是很大，只能从结果知道匹配速度AC自动机是由于Trie树的。
内存占用
由于trie树节点多了失效指针，所以AC自动机内存占用肯定会比trie树占用多。
将我们自己项目目前用到的屏蔽字(221.7kb)加入后,写个benchmark测试文件,得出
ac自动机屏蔽字部分占 2560.11kB
trie 屏蔽字部分占 2048.08kB
ac自动机比trie多出500k左右，多占用25%
总结
AC自动机具有优于Trie树的多模式匹配能力。在匹配过程中，AC自动机能够同时匹配多个模式串，不仅提高了匹配速度，而且减少了冗余匹配。AC自动机的时间复杂度为O(n+Z)，其中n为文本串的长度，Z为所有模式串的长度之和，这意味着AC自动机的匹配速度是与模式串数量和长度成正比的，对于大量的长模式串，AC自动机的优势更加明显。
因此，对于单模式串匹配，使用Trie树更为合适，而对于多模式串匹配，使用AC自动机更加适合。
所以如果随着项目屏蔽字的长度与数量等提升，用AC自动机替换Trie树是可以考虑的。
