那么,屏蔽词系统到底该怎么做?

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口交换机。
  • 添加屏蔽词的例外规则,比如“成人牙刷”需要是“成人”的例外规则。

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

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

《那么,屏蔽词系统到底该怎么做?》上有2条评论

  1. 1. 对于我而言,即便我掌握了上述你所有描述的方法实现,我也只会使用最简单和原始的那一种方法。
    原因很简单,和价值观不符,我相信那些方法可以使用在更有"意义"的领域。

    2. 技术上,我认为这是一件不可能完成的任务。你所提到的“一不小心就把正常内容干掉了”,恐怕不是如此吧?恐怕事实情况是你把大部分正常内容都给干掉了吧。

    阿桑奇在大使馆接受采访时被问到:“你有多久没有见过外面的阳光了”?
    阿桑奇答道:“你知道,人是一种适应力非常强的动物,他们会尝试去适应任何可能的环境变化。”

    你不要低估人的适应能力和创造力,信息的意义是人所赋予的,他不是一层不变的。结构也不是一层不变的,比如藏头诗(我很不情愿的举这个例子,毕竟这不是一段非常愉快的历史)。

    所以,我们面对的是什么?
    一群自称工程师的人,还有他们那可笑的算法。

    1. 从“价值观”这个词来看,你可能把屏蔽词理解成了某种政治意味上的词。但实际上在企业中,有很多非政治场合的屏蔽词系统,比如 antispam,比如要进行品牌或者版权保护,这篇文章只是技术讨论,并不确定地预设某个具体场景。

发表评论

电子邮件地址不会被公开。 必填项已用*标注