需求背景
大家有没有做过屏蔽敏感词的需求呢,这个需求一般来说很常见了。比如,系统中有一段话:
我爱吃肯德基
要求【肯德基】三个词给屏蔽掉,屏蔽后的语句显示为:
我爱吃***
常规的做法可能是查询敏感词库中的敏感词,循环每一个敏感词,然后去输入的文本中从头到尾搜索一遍,看是否存在此敏感词。
但是如果敏感词很多,对于匹配也是很耗性能的。
这里介绍使用DFA算法匹配敏感词,并进行处理。性能要优于常规处理方法。
什么是DFA算法
“在计算理论中,确定有限状态自动机或确定有限自动机(英语:deterministic finite automaton, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表E的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。
——来自*
”
这里的确定意思为:状态以及引起状态转换的事件都是可确定的,不存在"意外"。有限指的是:状态以及事件的数量都是可穷举的。
DFA算法在匹配关键字上面有广泛的应用。
比如上面的关键词【肯德基】,【肯尼玛】。我们可以抽取成上面的树状模型。椭圆表示状态,状态与状态之间的连线叫事件。
当然这里只是简单的介绍DFA是什么,想深入的童鞋可以看看这篇文章:
“常用的DFA最小化算法?- 知乎 -https://www.zhihu.com/question/39767421
”
里面介绍了如何将正常数据构造成DFA形式。
Java代码实战
现在我们开始做一个示例吧
现在我们指定了敏感词【"二愣子","二蛋","狗娃"】,我们按照上面的方式重新构造数据结构:
如上图,我们构造了3组数据,每个节点有一个状态标记,1代表节点结束,也就是敏感词结束,0代表还未结束。
数据结构Json形式如下:
接下来就是如何实现代码了。
首先我们将敏感词汇添加进入set集合中:
private Set<String> readSensitiveWordFile() {
Set<String> set = Sets.newHashSet();
set.add("二愣子");
set.add("二蛋");
set.add("狗娃");
return set;
}
当然,实际情况需要从数据库中读取,或者从文件中读取,然后在加载进入set集合。接下来我们将set中的数据重新构造成上面Json格式的,Java这里需要使用Map来存储。
我们创建一个sensitiveWordMap
来存储敏感词,这里实际就是map套map的过程,我们来调试看看map的结构:
上面的数据结构Map是不是看晕了,其实就是我之前提到Json格式。
在系统初始化时就将敏感词构造好。
我们将敏感词的结构构造好后,就开始匹配句子了。
如上代码,我们需要将句子中的字符一个一个的循环,如果(Map) nowMap.get(word) != null
,说明匹配到了敏感词,这里如果isEnd
的结束符为1,代表敏感词结束,即匹配到了一个敏感词。
我们还会遇到上图的情况,【二蛋】是一个敏感词,【蛋疼】也是一敏感词。在【蛋】这个节点中,是【二蛋】的结束节点,是【蛋疼】的开始节点。我们通过代码:
SensitiveWordFilter.minMatchTYpe == matchType
判断,如果为true
,我们在【蛋】结束之后就不再往下匹配,并将匹配到的index返回。之后再进入下一个循环了。反之。
上面我们拿到匹配到的敏感词的index,接下来就要将句子中的敏感词显示出来了。
我们将其存入set集合中:
Set<String> sensitiveWordList = new HashSet<>();
这里大家发现一个问题没有:
“获取敏感词index循环了一次txt句子,获取敏感词字符又循环了一次,大家有没有办法减少一次循环呢