<返回更多

如何用Java实现屏蔽敏感词功能

2021-04-01  今日头条  Lvshen的技术小屋
加入收藏

需求背景

大家有没有做过屏蔽敏感词的需求呢,这个需求一般来说很常见了。比如,系统中有一段话:

我爱吃肯德基

要求【肯德基】三个词被屏蔽掉,屏蔽后的语句显示为:

我爱吃***

常规的做法可能是查询敏感词库中的敏感词,循环每一个敏感词,然后去输入的文本中从头到尾搜索一遍,看是否存在此敏感词。

但是如果敏感词很多,对于匹配也是很耗性能的。

这里介绍使用DFA算法匹配敏感词,并进行处理。性能要优于常规处理方法。

什么是DFA算法

在计算理论中,确定有限状态自动机确定有限自动机(英语:deterministic finite automaton, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表E的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。

——来自维基百科

这里的确定意思为:状态以及引起状态转换的事件都是可确定的,不存在"意外"。有限指的是:状态以及事件的数量都是可穷举的。

DFA算法在匹配关键字上面有广泛的应用。

如何用Java实现屏蔽敏感词功能

 

比如上面的关键词【肯德基】,【肯尼玛】。我们可以抽取成上面的树状模型。椭圆表示状态,状态与状态之间的连线叫事件。

当然这里只是简单地介绍DFA是什么,想深入的童鞋可以看看这篇文章:

常用的DFA最小化算法? - 知乎
-https://www.zhihu.com/question/39767421

里面介绍了如何将正常数据构造成DFA形式。

JAVA代码实战

现在我们开始做一个示例吧

现在我们指定了敏感词【"二愣子","二蛋","狗娃"】,我们按照上面的方式重新构造数据结构:

如何用Java实现屏蔽敏感词功能

 

如上图,我们构造了3组数据,每个节点有一个状态标记,1代表节点结束,也就是敏感词结束,0代表还未结束。

数据结构Json形式如下:

如何用Java实现屏蔽敏感词功能

 

接下来就是如何实现代码了。

首先我们将敏感词汇添加进入set集合中:

private Set<String> readSensitivewordFile() {
   Set<String> set = Sets.newHashSet();
   set.add("二愣子");
   set.add("二蛋");
   set.add("狗娃");
   return set;
}

当然,实际情况需要从数据库中读取,或者从文件中读取,然后再加载进入set集合。接下来我们将set中的数据重新构造成上面Json格式的,Java这里需要使用Map来存储。

如何用Java实现屏蔽敏感词功能

 

我们创建一个sensitiveWordMap来存储敏感词,这里实际就是map套map的过程,我们来调试看看map的结构:

如何用Java实现屏蔽敏感词功能

 

上面的数据结构Map是不是看晕了,其实就是我之前提到Json格式。

如何用Java实现屏蔽敏感词功能

 

在系统初始化时就将敏感词构造好。

如何用Java实现屏蔽敏感词功能

 

我们将敏感词的结构构造好后,就开始匹配句子了。

如何用Java实现屏蔽敏感词功能

 

如上代码,我们需要将句子中的字符一个一个的循环,如果(Map) nowMap.get(word) != null,说明匹配到了敏感词,这里如果isEnd的结束符为1,代表敏感词结束,即匹配到了一个敏感词。

如何用Java实现屏蔽敏感词功能

 

我们还会遇到上图的情况,【二蛋】是一个敏感词,【蛋疼】也是一敏感词。在【蛋】这个节点中,是【二蛋】的结束节点,是【蛋疼】的开始节点。我们通过代码:

SensitiveWordFilter.minMatchTYpe == matchType

判断,如果为true,我们在【蛋】结束之后就不再往下匹配,并将匹配到的index返回。之后再进入下一个循环了。反之。

上面我们拿到匹配到的敏感词的index,接下来就要将句子中的敏感词显示出来了。

如何用Java实现屏蔽敏感词功能

 

我们将其存入set集合中:

Set<String> sensitiveWordList = new HashSet<>();

这里大家发现一个问题没有:

获取敏感词index循环了一次txt句子,获取敏感词字符又循环了一次,大家有没有办法减少一次循环呢

这个问题大家阔以思考一下。

然后我们将句子中的敏感词替换成指定的字符。

如何用Java实现屏蔽敏感词功能

 

比如我们将敏感词替换成 "*"。

测试代码

我们来测试下代码

如何用Java实现屏蔽敏感词功能

 

我们选取了《凡人修仙传》中的一段句子:

"韩立被村里人叫作“二愣子”,可人并不是真愣真傻,反而是村中首屈一指的聪明孩子,但就像其他村中的孩子一样,除了家里人外,他就很少听到有人正式叫他名字“韩立”,倒是“二愣子”“二愣子”的称呼一直伴随至今。而之所以被人起了个“二愣子”的绰号,也只不过是因为村里已有一个叫“愣子”的孩子了。这也没啥,村里的其他孩子也是“狗娃”“二蛋”之类的被人一直称呼着,这些名字也不见得比“二愣子”好听了哪里去。"

测试的结果为:

如何用Java实现屏蔽敏感词功能

 

关于DFA的思考

这里我们将敏感词构造成map,相对于普通的方法,我们不用循环敏感词,直接用hash表的形式。效率会快很多。但是我们循环了两次句子txt,如果我们的句子很大,那就对性能有影响,如果我们的敏感词库很大,构建的map集合就会很大,这样就会很占用内存

进阶-一种基于AC自动机的高性能匹配算法

关于DFA算法的问题,这里又有一种AC自动机的算法,也可以实现敏感词匹配。网上有关于AC自动机的论文,有兴趣的童鞋阔以下载看看:

PARA-AC:一种基于AC自动机的高性能匹配算法-AET-电子技术应用
-http://www.chinaaet.com/tech/designApplication/3000125061

什么是AC自动机呢?

AC自动机全称是Aho-CorasickAutoMaton,和Trie树一样是多模式字符串匹配算法。并且它与Trie树的关系就相当于KMP与BF算法的关系一样,AC自动机的效率要远远超出Trie树

AC自动机对Trie进行了改进,在Trie的基础上结合了KMP算法的思想,在树中加入了类似next数组的失效指针。

AC自动机的构建主要包含以下两个操作

将多个模式串构建成Trie树

为Trie树中每个节点构建失败指针

如何用Java实现屏蔽敏感词功能

 

这里给大家推荐一个项目,基于AC自动机的高性能敏感词匹配:

GitHub - toolgood/ToolGood.Words: 一款高性能敏感词(非法词/脏字)检测过滤组件,附带繁体简体互换,支持全角半角互换,汉字转拼音,模糊搜索等功能。
-https://github.com/toolgood/ToolGood.Words

感谢这个大佬提供的开源项目。

敏感词构造的数据结构:

如何用Java实现屏蔽敏感词功能

 

封装的数据结构为

如何用Java实现屏蔽敏感词功能

 

匹配替换敏感词代码如下:

如何用Java实现屏蔽敏感词功能

 

代码中的TrieNode2为存储的敏感词结合构

我们用AC自动机算法测试敏感词

如何用Java实现屏蔽敏感词功能

 

如上代码,test为我们要测试的句子,list为设置的敏感词,测试结果如下:

如何用Java实现屏蔽敏感词功能

 

我们对比DFA算法的耗时:

如何用Java实现屏蔽敏感词功能

 

AC自动机耗时低于1ms,而DFA自动机的耗时大于了1ms,当然这里只是初略的测试。需要有意义的性能测试还需要加大敏感词库和测试句子的量。

好了,今天的文章到这里就结束了,文章介绍了AC与DFA两种算法屏蔽敏感词以及其性能,当然AC自动机的原理还是比较复杂的,本文就不做详细介绍了,有兴趣的同学可以多了解下相关知识。

参考

AC自动机:如何实现敏感词过滤? -
https://blog.csdn.net/qq_35423154/article/details/109181973

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>