流水不争先,争的是滔滔不绝

怎么设计高效的敏感词过滤系统(一)

即时通讯软件开发 云聊IM 5046℃

IM项目需要对上边传输的消息进行必要的过滤。如果总是对着某人输入f**k就显得不太文明了。

一个通用且简单的做法是,设定一批敏感词,如果消息中出现这些词,由系统进行必要的处理。怎么实现这个功能呢?

一、能够实现敏感词过滤功能的方法有很多

方法有很多,我简单罗列了几个。

  1. 1、直接将敏感词组织成String后,利用indexOf方法来查询。
  2. 2、传统的敏感词入库后SQL查询。
  3. 3、利用Lucene建立分词索引来查询。
  4. 4、利用DFA算法来进行。

显然,方法1和方法2在性能上基本无法满足IM系统高效处理消息的需求,放弃。

方法3,采用Lucene建立本地分词索引,将消息内容分词后,在索引库里搜索。这个方法较复杂,且分词效率也不会很高,放弃。

大多数的敏感词过滤系统采用的是方法4,DFA算法。

二、DFA简介

DFA是什么?这里有必要简单介绍一下这个概念(这部分看不懂没关系,可以跳过)。

1、DFA定义

DFA翻译成中文是“确定有穷自动机 ”

定义:一个确定有穷自动机(DFA)M是一个五元组:M=(K,Σ,f,S,Z)其中

① K是一个有穷集,它的每个元素称为一个状态;

② Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号字母表;

③ f是转换函数,是K×Σ→K上的映射(且可以是部分函数),即,如 f(ki,a)=kj,(ki∈K,kj∈K)就意味着,当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态;

④ S ∈ K是唯一的一个初态;

⑤ Z⊂K是一个终态集,终态也称可接受状态或结束状态。

2、DFA例子

3、DFA状态图表示

假定DFA M含有m个状态,n个输入字符,那么这个状态图含有m个节点,每个节点最多有n个弧射出,整个图含有唯一一个初态点和若干个终态点,初态节点冠以双箭头“=>”,终态节点用双圈表示,若f(ki ,a)=kj,则从状态结点ki到状态节点kj画标记为a的弧。

4、DFA所接受

对于Σ* 中的任何符号串t,若存在一条从初态到某一终态的道路,且这条道路上所有弧的标记连接成的字符串等于t,则称t可为DFA M所接受,若M的初态同时又是终态,则空字可为M所识别(接受)。

即:若 t∈ Σ* , f(S, t)=P, 其中S为M的开始状态,P∈Z,Z为 终态集。

则称 t 为 DFA M所接受(识别)。

如果看懂了DFA的介绍,我们可以这么理解敏感词过滤系统。用需要被过滤的敏感词构建一个DFA(确定有穷自动机 ),然后遍历需要过滤的文本,判断文本中是否有DFA可接受(识别)的字符串即可。

如果没有看懂DFA,看下边一节也OK。

三、用Trie树构建DFA

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

假设有b,abc,abd,bcd,abcd,efg,hii 这7个单词(实际使用中,这些单词就是敏感词),我们构建的树如下图

如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。

过滤敏感词,就是把需要过滤的文本,从第一个字开始,逐个字往后在Trie树中查找。如果能走到树的结束节点,则就能发现敏感词!

四、防止回溯

1、回溯的场景

看一句话待过滤的文本(以下简称母串)“瓜子二手车成交量全国领先”,再看下图模拟的几个敏感词。我们来看看检索过程。

(1)第1个字“瓜”在Trie树的第一层节点(第一层节点有“二”、“瓜”、“西”三个字);继续(在中间的子树)往后找“子”字,在树枝的后续节点;继续找“二”,继续找“手”,继续找“车”,”车”字无法找到,查找失败。

(2)(这里不能从“二”字开始找,需要回溯到“子”字,万一有“子”字开始的敏感词呢 )第2个字“子”不在Trie树第一层节点,查找失败。

(3)第3个字“二”字,在Trie树第一层节点……

(4)后续文字按此方法逐字往后查找即可。

这个查找方法能够求解,但是效率不高(注意第2步),我们读到了后边的文字,但是由于没有命中,检索发生了回退,导致效率下降。事实上,我们在第1步已经比较过“二手”这个词,如果能利用第1步中比较的结果,直观感觉是能够加快匹配出“二手车”这个敏感词的。

2、前缀指针

前面的场景很像字符串查找的KMP算法,KMP算法可以防止字符串查找过程中的指针回溯。那Trie树的结构有没有办法也避免这种情况发生呢?

答案是肯定的。参考KMP算法(百度一下你就知道了) 的最长相同前后缀的方法,来避免回溯。

这里首先需要理解“前缀”、“后缀”的思想。如果不了解这两个概念,推荐一篇KMP算法讲得特别清楚的博文http://www.cnblogs.com/c-cloud/p/3224788.html(一定要读)。

为了避免回溯,参考KMP的next数组,在Trie图中定义“前缀指针 ”

“前缀指针 ”定义:从根节点到节点P可以得到一个字符串S,节点P的前缀指针定义为 指向树中出现过的S的最长后缀(不能等于S)

后续文章将详细讲解怎么高效构建“前缀指针 ”,如何快速遍历母串,以及工程上如何实现的问题。

转自公众号:普通程序员

作者:封宇

版权声明:部分文章、图片等内容为用户发布或互联网整理而来,仅供学习参考。如有侵犯您的版权,请联系我们,将立刻删除。
点击这里给我发消息