敏感词过滤算法实现

说到敏感词过滤，我也觉得这里没有必要写这个文章，因为前人已经前前后后有过很多种算法解决该问题。这里我之所以写这个文章，是因为我自己自创了一种算法（真的是自创哦，因为我在写这个算法的时候，完全是自己想出来的方式，没有借鉴任何代码！灵感来自于一篇文章中的一句话“如果能扫描一遍文本就能将所有的词找出来，那速度就是最快的”）。想法不周到或想得不周到，请大家砖头轻拍

 

背景

在网络日益发达的现在，也伴随着有益信息与造成不稳定因素的信息也随之日益泛滥，为了网民的思想健康，也为了社会的和谐，在许多对外公共场合下，有些内容是要经过审查才能显示的。在网络审查初期，都是通过人工审核，这种审核方式虽然准确且智能，但与网络文字产生的速度相比，其效率就显示微不足道了！因此，自动化的系统处理方式的需求越来越强烈……

目前拥有的处理方式

有需求就有市场，因此自动化处理的方式自然而然随之如雨后春笋般地迅速产生了一大批！其处理方式都是基于一点：敏感词库！然后基于该词库对目标文本进行敏感词提取操作，因此各自动化处理方式的唯一差别就在于敏感词提取算法的不同，因为算法不同，效率不同、结果也可能不同。而对于敏感词过滤算法来说，要掌握两个关键点：效率和准确率！效率就是对于大批量敏感词和长段的目标文本处理时要能在很短时间内响应；准确率就是对于一个敏感词要尽量区分语境，不能误将非敏感词判断为敏感词而过滤掉（如我们敏感词库的精确匹配与模糊匹配的定义）！
就我所知，目前较为流行且成熟的算法有：

简单文本搜索与替换

这种方式是最简单的，就是循环把每个敏感词在目标文本中从头到尾搜索一遍，如果有文本高亮或替换的话，那就找到一个就处理一个。这种方式的优缺点如下：

优点：

1. 算法简单。对于开发人员来说，简单的算法会使代码实现上简单，开发难度最小！

   缺点：

2. 效率太低。因为循环每个敏感词，所以当敏感词很多、目标文本很长时，其效率可以说是该算法的致命问题！
3. 匹配准备率太低。比如，有一个敏感词为as，那它边hash、class等中的as都会被匹配甚至被处理。
   所以这个算法绝对不能使用！

传说中的DFA算法（亦称自动机算法）

上面的算法是以敏感词库为主体，对目标文本进行匹配，而这个算法是以目标文本为主体，其算法大概为：将所有敏感词构建为词图（即是将所有敏感词组织为一个图状关系，即，以任意一个字都可以查出以该字为开头的词），然后对文本进行逐一搜索并看每个字是否在图中存在，如果存在看是否有对应的词存在，如果存在，则匹配成功，记录下来，继续往下搜索直到搜索完整个文本！其详细的算法原理参见：http://wenku.baidu.com/view/2e9dad18a8114431b90dd896.html。

优点：

1. 效率高于上面的算法；

缺点：

1. 理论算法太过复杂，开发成本很大，而且网上没有该算法的源码或相应的包！而且该算法匹配率也比较低。再者就是该算法巨耗内存,而且启动很慢。

网友自创的TTMP算法（自称 字符串多模式精确匹配）

其算法主要原理为：
1、首先扫描文章里面的每一个字符，只有当某一个字符是脏字表中任意一个脏词的第一个字符（称为“起始符”），我们才试图看看接下来是否是脏字（触发检索）。
2、但是我们也不是毫无头绪的就开始循环脏字表的每一个词条：
2.1、我们往后检索一个字符，先看一下这个字符是否是脏字表里面的任意一个字符，如果不是，就表明不可能是脏字表中的任何一个条目，就可以退出了。
2.2、如果是，我们就取从第一个被检出字符到目前扫描到的字符之间的字符串，求哈希值，看看能否从哈希表中检出一个脏词。
如果检出了，那就大功告成，否则继续检索后面一个字符（重复2.1、2.2），直至找不到，或者超出脏字表条目最大的长度。
2.3、如果都找不到，或者超长，那么接下来就回到刚才的那个“起始符”后一个字符继续扫描（重复1、2），直至整个文章结束。
详细的算法说明参考：http://www.cnblogs.com/sumtec/archive/2008/02/01/1061742.html。

其它可查算法

其它查到的算法还有：KMP算法是单模匹配算法，BM据说也是单模式的算法，WM算法是多模匹配……好吧，我承认，到最后的时候，我没有耐心再看下去了，因为这些算法都说自己很厉害，可是却都没有放出具体完整的可用的算法程序出来！开发难度还是存在的，这些方法都不是我的菜

我设想的一个算法——基于分词组件结合向量相似运算

在无尽的苦海探寻的过程中，我的大学数学知识不断滴从的我意识深处涌了出来！我突然想起一个可能可行的办法：因为网络上有许多性能很不错的分词工具（jar包形式的也大有存在），而且大学时有一种向量算法可以计算两个向量间的相似度的能力，于是就想到是否可以使用向量算法来解决该问题。该算法的主体思想为：将所有敏感词构建为一个向量，再将目标文本用分词工具分成若干个词并构建成另一个向量，然后将这两个向量进行相似值计算，得出哪些向量元素相同，并最终得知该目标文本中存在哪些敏感词！
呃……看来我还是对不起祖国对不起党！我已经不记得相应的向量算法了，而且也没有找到一个计算两个向量元素之间相同的算法（因为向量的高级算法太多、太复杂了）！看来从我意识深处涌出来的只是一些影子~
所以，这只是一个设想，而非真正实现方案！

敏感词过滤算法（自命名：聚合词树查询法）

该算法基于DFA并结合许多算法并进行相应的简化，最终其算法基本原理为：将所有敏感词库按模块聚合构建成一个词树（所谓聚合，就是将相同字开头的部分进行聚合，以减少对词的查询范围，相当于建立敏感词索引，如：他奶奶的、他妈的、他娘的，这三个词，聚合构建成词树时，“他”字就是这三个词的索引，同时每个词的结尾都有一个结束标志和该词的一些描述，如敏感级别等），然后从头到尾扫描一遍目标文本，当遇到以敏感词树中的索引的字时，查看后面的文本是否构成敏感词（如果这里有以这个敏感词开头的更长的敏感词时，以更长的为匹配结果，并判断该词在文本中前后是否有分隔符来区别其匹配方式），如果是则记录，一遍扫描完之后所有敏感词即被扫描出来了！

结语

我的这个算法不一定是最好的，但相比较上面几种算法，从成本、效果等整体上来说是很合适的！另外网上还有许多一些未公开算法的过滤方式，这些算法因为无法获知其算法，而无法为我所借鉴，因此平添几许遗憾！另外还有著名的算法有：KMP算法是单模匹配算法，BM据说也是单模式的算法，WM算法是多模匹配（WM算法详细描述：http://blog.chinaunix.net/space.php?uid=20435679&do=blog&cuid=228430）的等等。
该方法还有许多可优化的空间，如可增加多线程、可优化判断已记录的词直接跳过不匹配等方式。
算法的效率要注意尽量满足两点：尽量少的扫描目标文本（包括尽量少的回扫目标文本），尽快能从敏感词库中找到指定的词！不断做到这两点，则效率就越高！

效率上还有提升空间

目前只是单线程的一种操作，而且算法实现的代码上可能还有一些小小的改进余地，如变量定义与数据结构的定义等方面的实现。

匹配能力较弱

不能对处理的关键词匹配，比如，“鸦 片”是一个敏感词的话，那如果用户刻意把它们分开，如写成“鸦$片”，那就无法匹配上了！

还可以运用于很多场景

运用的场景很多，如高亮指定的词、分词（可以指定以最长或最短模式匹配）、拼音与汉字间的转换等等字符串匹配功能！

注：附件中有两个文件，一个ppt，用于演示该算法的过程（用office2007打开效果最佳）；一个是源代码；请大家自己浏览，谢谢！

 

现在想来，这个名称更贴切的应该叫“关键词快速查找算法”！——2013-04-17注

评论

11 楼 hellohank 2012-11-26  

weareyou-006 写道

请问楼主，此匹配算法的树形结构占用内存大吗？

不大的~
因为是树形结构，所以会将有一定的压缩的。比如：“他妈的”，和“他娘的”两个词来说，构成树之后，“他”就会只存一个就够了（后面的“的”还是会分别存储的）~

10 楼 weareyou-006 2012-11-19  

请问楼主，此匹配算法的树形结构占用内存大吗？

9 楼 hellohank 2012-06-14  

xurichusheng 写道

SWAnalyzer
没有这个类呀

你下载的是改进版本吧？因为改进版本我改了一下类名。
改进版本主要做了两件事：
1、使用主体程序可以多实例运行；
2、更改主体类名，这个可以在下载包中的readme.txt中有说明的；

8 楼 xurichusheng 2012-06-12  

SWAnalyzer
没有这个类呀

7 楼 hellohank 2012-06-06  

confident_f 写道

SWAnalyzer.addWord

hellohank 写道

shiminwang 写道

请问楼主，怎么用呢

使用前先调用SWAnalyzer.addWord方法，将所有敏感词加入内容（这是一次性操作，第一次使用时操作一下，后面就不需要操作了），然后直接调用SWAnalyzer.analysis方法（方法很多，具体使用方式看方法注释）

另外，使用方法我好像已经写在附件里面的readme.txt文档中了

没有addWord方法啊

因为addWord是非静态方法，因为我不建议大家在使用过程中而添加词，所以没有将其定义为静态方法~

6 楼 confident_f 2012-05-30  

SWAnalyzer.addWord

hellohank 写道

shiminwang 写道

请问楼主，怎么用呢

使用前先调用SWAnalyzer.addWord方法，将所有敏感词加入内容（这是一次性操作，第一次使用时操作一下，后面就不需要操作了），然后直接调用SWAnalyzer.analysis方法（方法很多，具体使用方式看方法注释）

另外，使用方法我好像已经写在附件里面的readme.txt文档中了

没有addWord方法啊

5 楼 confident_f 2012-05-30  

楼主，使用方法没有写在readme里面啊。高亮指定的词、分词（可以指定以最长或最短模式匹配）、拼音与汉字间的转换等等字符串匹配这些都怎么用啊？能写个使用说明吗

4 楼 hellohank 2012-02-16  

yuanyeekong 写道

Module
Level
Pattern
请问这几个参数在应用中有什么作用呢?

这是一些公用的业务规则，Module：说明是哪个模块下的敏感词，因为一个系统下有多个板块组成，如：新闻板块、评论板块、发送邮件板块等，而有时候在这几个板块中，它们对敏感词的定义和要求是不尽相同的，因此有这个参数将其区分；
Level：这是区分敏感词的敏感级别的，比如：有的词是打死人也不能出现的，这就是我们说的严令禁止的敏感词，但有些词却是可以商量的，我们叫建议不使用。进行区分对待后，可以针对不同类型的敏感词做相应的处理，如高亮的颜色不一样等；
Pattern：这表示什么样的匹配方式是敏感词，举个例子：“这是他妈妈的东西”，其中“妈的”是敏感词，如果匹配方式为“不精确匹配，也就是模糊匹配”，那这里面的“妈的”就会被认为是敏感词，而如果匹配方式要求为“独立精确匹配”，那因为它的前后都有字，因此认为它是一个定语，而不是骂人的敏感词！比如说：“你……妈的！”那个情况下就是敏感词了，因为它是独立精确存在！
不知道这样解析算不算清晰？呵呵

3 楼 yuanyeekong 2012-02-16  

Module
Level
Pattern
请问这几个参数在应用中有什么作用呢?

2 楼 hellohank 2011-12-28  

shiminwang 写道

请问楼主，怎么用呢

使用前先调用SWAnalyzer.addWord方法，将所有敏感词加入内容（这是一次性操作，第一次使用时操作一下，后面就不需要操作了），然后直接调用SWAnalyzer.analysis方法（方法很多，具体使用方式看方法注释）

另外，使用方法我好像已经写在附件里面的readme.txt文档中了

1 楼 shiminwang 2011-12-27  

请问楼主，怎么用呢