那么，屏蔽词系统到底该怎么做？

caoz 在最近一篇公众号文章《企业面试需要几轮》中提到一个面试问题:

大家都知道做互联网有很多屏蔽词要处理，那么需要对用户发布的内容，做屏蔽词过滤，先不考虑一些正则组合的情况，假设我有一个屏蔽词库，里面有几万条屏蔽词信息，然后我有个非常火爆的社区，每天用户产生海量内容，比如上百万篇文章或评论，现在我要求每篇文章都能快速通过屏蔽词库去检索，而且要求服务器可以支撑尽可能多的处理请求，毕竟这是成本啊。那么请设计一个屏蔽词过滤的算法逻辑。

碰巧我在面试中也喜欢问这个问题，可惜的是能答上来的的确不多。

单单从算法层面论，大概有 50% 的人能回答出来逐个进行 KMP 匹配（另外 50% 不知道什么是 KMP）。让他更进一步优化的话，20% 的人能想到一些粗糙的优化技巧，10% 的人能说出前缀树匹配。大部分能答出前缀树匹配的人会提到 AC 自动机，但只有一半能大概答出 AC 自动机的大概算法。到目前为止，还没有人回答过其它算法，比如 Rabin-Karp 或者 Commentz-Walter。

即使在算法层面上能回答出来 AC 自动机，在实现上候选人也只能形象地描述一下 Trie 树和失败指针，Trie 树的每一层使用一个 Set 或者哈希表数据结构。到目前为止，还没有人回答过用 Double Array 来实现 Trie，甚至连用前缀做 key 的一个大哈希表来模拟 Trie 树的优化也没有。虽然构造 Double Array Trie 的代价非常高，但内存占用非常小，检索效率也很高，特别适用于屏蔽词的场合。离线建好 Double Array Trie，推送到线上仅仅需要读入两个内存块就能完成更新，加载过程到了极简。

哪怕是回答出了高效的算法和实现，离一个真正有效的屏蔽词系统还相差很远。首先要清楚一件事，道高一尺，魔高一丈。你平时想过什么办法绕过屏蔽词系统，现在就得想办法对抗你曾经开过的脑洞。下面举几个最常见的例子：

1. 简繁体混用，大小写混用，全半角混用。首先得做归一化，繁体转简体，大写转小写，全角转半角。
2. 在屏蔽词中间加特殊字符。原串先过一遍，去掉特殊字符再过一遍。
3. 字形相近，读音相似。积累相近字典，替换为常用字再过一遍，将所有的字转为拼音再过一遍。
4. 同义词替换。加屏蔽词时考虑替换场景，或者挖掘替换词库用来替代。

上面这几种方法，说起来简单，做起来都是坑。一不小心，就把正常的内容当成包含屏蔽词干掉了。这就是为啥大家老吐槽在某些网站发帖，动不动就被屏蔽，关键就在于坏招太多，规则多了就有误伤啊！所以一个优秀的屏蔽词系统，还得尽量避免误伤情况，也有一些办法。

• 先切词，如果命中屏蔽词的范围不在切词的边缘，应该是误伤。最简单的例子是：24口交换机。
• 添加屏蔽词的例外规则，比如“成人牙刷”需要是“成人”的例外规则。

最近几年机器学习特别火，其实机器学习也特别适合这种场景，就是一个二分类问题嘛。只是超出了简单算法的范畴，这里就不展开了。

所以你看，就一个“屏蔽词过滤的算法逻辑”，就有那么多要探讨的东西。而且以目前国内大部分互联网产品的实现上来看，可能考虑的还没我这篇文章全面。这可真不是一个能轻松就回答完美的问题。