大家好,又见面了,我是你们的朋友全栈君。
IM项目需要对上边传输的消息进行必要的过滤。如果总是对着某人输入f**k就显得不太文明了。
一个通用且简单的做法是,设定一批敏感词,如果消息中出现这些词,由系统进行必要的处理。怎么实现这个功能呢?
一、能够实现敏感词过滤功能的方法有很多
方法有很多,我简单罗列了几个。
1、直接将敏感词组织成String后,利用indexOf方法来查询。
2、传统的敏感词入库后SQL查询。
3、利用Lucene建立分词索引来查询。
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)
后续文章将详细讲解怎么高效构建“前缀指针 ”,如何快速遍历母串,以及工程上如何实现的问题。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130164.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...