敏感词过滤

algorithm

在做社交类功能的时候一个躲不过的问题就是敏感词处理，这个问题的本质其实就是：在输入的一串字符串中匹配有限组“字典”中的子串，这样一个问题。

对于这样一个问题，最容易想到的处理方法就是穷举

暴力穷举

虽说是穷举，但其实所有的‘可能性’已经都在“字典”中呆着了。我们要做的就是遍历 “字典” 一个一个看取出的模式串是不是输入字符串的子串，简单粗暴易理解。

当然，这种方法的效率也是十分低下，假设这里使用 KMP 算法来进行子串匹配，KMP 算法的时间复杂度为：构建 next 数组的时间复杂度 $O(m)$ 和匹配过程的时间复杂度 $O(n)$

由于在这个问题上模式串是已经确定的一个集合，可以事先计算好所有的模式串的 next 数组保存起来重复使用，所以暂且忽略这一部分的消耗。那么整个匹配过程的时间复杂度为 $O(n*m)$ ，其中 n 为 “字典” 的规模

DFA

另外还有 DFA 的解决思路，DFA 全称 Deterministic Finite Automaton，确定有限状态自动机

对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态。

一个完整的 DFA 由五个部分组成：

1. 有限状态集合 Q
2. 输入字母表 I
3. 状态转移函数 F
4. 开始状态 s
5. 接受状态集合 E

描述出来的模型总是不那么直观，来看看一个用有向图表示的 DFA 实例（贴一张 google 搜到的图）

其中 Q = {S, A, B, C, D, E, F}
s = S
E = {C, D, E, F}

一个给定的 DFA 存在一个唯一对应的有向图

DFA 的工作过程也很简单，从起始状态开始，一个字符接一个字符地读入输入字符串，并根据转移函数一步一步地转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。

具体到敏感字这个问题上，我们把给定的敏感词 “字典” 构建成一个 DFA，对输入串进行操作。

Trie Tree

这基本就是 Trie 的思路，Trie 树本身就是一个 DFA

Trie 树又叫前缀树或者字典树，其结构大概是这样（贴一张 google 搜到的图）

它的每个节点对应 DFA 的每个状态且每个节点内会保存接受状态，每条数值就是状态转移，具体定义描述可以参见 wiki 这里就不过多介绍了，直接来应用

拿它来处理敏感词的思路很简单，在构建完成这个树后只需要从第一个字符挨个读入输入字符串，如果能够到达接受状态就表示匹配成功，否则回溯，把指针向后移位（就是接着从输入串第二个字符）再来一次上面的过程，循环这个过程直到结束。

根据上述过程可以看出，其时间复杂度为 $O(n*m)$，n 为输入字符串长度，m 为树的高度。其时间复杂度与 “字典” 规模已经无关了，这是一个很大的进步。

实现

在实现方面，可以使用通常的矩阵来存储，行表示状态，列表示输入字符，其行列对应的位置保存转移状态。这种存储方式其检索效率很高，但是不推荐使用。主要是因为可以想象，由于父子节点非常的不均匀，会导致很多位置都将是空的，这会造成矩阵的非常稀疏，从而造成空间的极大浪费。

也可以使用结构体进行存储，然后以漫天飞指针的方式进行连接，但这样的方式所占用的空间依然非常庞大。

为了节省空间并不损失查询效率，二数组Trie 的实现方式就被提了出来，它使用两个数据 base 数组和 check 数组存储整棵树，在 base 数组中以偏移的方式存储所有的状态节点，check 数组则用来存储对应状态的前驱状态。具体实现就不在这里展开来细说了，网上有各种实现版本，有兴趣的可以去看下。

AC 自动机

上面 Trie 已经把算法效率进行了大幅优化，但是可以看到每次适配还是要回溯，按照之前分享过的 KMP 算法可以可以想到这一定有改进的余地，这就是 AC 自动机的核心思路了，但其实 AC 自动机算法和 KMP 是在同一时间提出的。

AC 自动机本身也是一个 DFA，它主要由 trie 树以及其基础上的失配指针组成。这些额外的失配指针用来在查找过程中匹配失败时进行回退操作，其核心思想和 KMP 的 next 数组差不多，而不同之处在于 AC 算法的失配指针不限于单一模式串，而可能在 “字典” 中的其他子串。

举个例子（贴一张 google 的图）

直观看图果然是理解复杂问题最有效的手段之一

还有基于 hash 的思路

Hashing

当被作用于检索、校验等用途时，hashing 永远是你高效的好伙伴，而在处理上述敏感词的问题上，有一个方法正好可以高效处理

Bloom Filter

Bloom Filter 即 布隆过滤器，它由一组 hash 函数和一条很长的二进制向量组成。它可以用于检索一个元素是否在一个集合中，其空间效率和时间效率都非常漂亮。

布隆过滤器也有一个预构建的过程，它的工作过程分为两步

1. 拟定 K 个 hash 函数，把敏感词 “字典” 中的词一一通过这 K 个 hash 函数映射到二进制向量的 K 的点上
2. 把待匹配的字符串也经过这 K 个 hash 函数，然后判断得到这 K 个点是否全部命中

实现起来也很简单，首先初始化整条二进制向量每一位都为 0，然后在预处理 “字典” 的时候，把映射的二进制位置 1
然后在匹配目标字符串时，只要散列到的 K 个点全部为 1 就认为匹配成功

由于整个 “词典” 最终被表示为一个二进制向量，所以布隆过滤器的空间效率非常的高，而且它的插入及检索的时间复杂度都为 O(k) ，其中 k 为 hash 函数的个数

但他也有非常明显的缺点，其一就是如果想要删除一个元素的话，将会非常的麻烦；还有一点就是误判，因为我们使用 k 个 hash 函数对目标进行散列，不可避免的会有碰撞存在，这也就导致了误判的风险，而且随着存入的元素数量增加，误判率随之增加

当然，如果本身 “词典” 的大小就不大，那么直接使用散列表进行存储，然后设置下碰撞处理函数就可以了。

要提到一点的是，上述方法其实并不是多模式匹配的处理方法，是用的时候需要先对输入字符串进行分词操作，所以其效果也与分词效果挂钩。