DFA算法如何应用于内容敏感词的高效过滤？

本文共计3897个文字，预计阅读时间需要16分钟。

DFA算法通过构建一棵树状查找结构，然后根据输入在该结构中进行高效查找。例如，我们有一个包含以下敏感词的词库：我爱你、我爱你他、我爱你她、我爱你它。

DFA 算法是通过提前构造出一个 树状查找结构，之后根据输入在该树状结构中就可以进行非常高效的查找。

设我们有一个敏感词库，词酷中的词汇为：
我爱你
我爱他
我爱她
我爱你呀
我爱他呀
我爱她呀
我爱她啊

那么就可以构造出这样的树状结构：

设玩家输入的字符串为：白菊我爱你呀哈哈哈

我们遍历玩家输入的字符串 str，并设指针 i 指向树状结构的根节点，即最左边的空白节点：
str[0] = ‘白’ 时，此时 tree[i] 没有指向值为 ‘白’ 的节点，所以不满足匹配条件，继续往下遍历
str[1] = ‘菊’，同样不满足匹配条件，继续遍历
str[2] = ‘我’，此时 tree[i] 有一条路径连接着 ‘我’ 这个节点，满足匹配条件，i 指向 ‘我’ 这个节点，然后继续遍历
str[3] = ‘爱’，此时 tree[i] 有一条路径连着 ‘爱’ 这个节点，满足匹配条件，i 指向 ‘爱’，继续遍历
str[4] = ‘你’，同样有路径，i 指向 ‘你’，继续遍历
str[5] = ‘呀’，同样有路径，i 指向 ‘呀’
此时，我们的指针 i 已经指向了树状结构的末尾，即此时已经完成了一次敏感词判断。我们可以用变量来记录下这次敏感词匹配开始时玩家输入字符串的下标，和匹配结束时的下标，然后再遍历一次将字符替换为 * 即可。
结束一次匹配后，我们把指针 i 重新指向树状结构的根节点处。