Java DAF 有穷自动机算法算法实现敏感词检测

背景

查询敏感词我这边了解到的又两种方法:

1、使用 contains() 对比是否含有字符串,直接从数据库查询出来敏感词,然后遍历对比。

2、使用反向 like 直接在 MySQL 数据库模糊查询。

以上两种方法在敏感词较少的时候查询速度还不错,但是随着敏感词增多还是会有一定的服务器压力,所以我们就有了 DAF 有穷自动机算法算法。

DAF 算法简介

1、解释:

​ DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。它是是通过 event 和当前的 state 得到下一个 state ,即 event + state = nextstate。理解为系统中有多个节点,通过传递进入的 event ,来确定走哪个路由至另一个节点,而节点是有限的。

2、构造描述

​ 以下面的例子,我们首先是‘王‘、’八’两个字,然后有个分叉点,分别是‘蛋’、‘羔’、‘子’,首先就是构建敏感词库,这两个敏感词库的 hash 表构造也如下图所示。

image.png

代码实现

1、工具类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
package com.zeno.common.utils; 

/***
* @Description: 敏感词过滤工具类
* @Param:
* @return:
* @Author: dds
* @Date: 2022/9/21 11:17
*/

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

@SuppressWarnings({"unchecked", "rawtypes"})//抑制多类型的警告
public class SensitiveFilterUtil {
/**
* 敏感词集合
*/
public static HashMap sensitiveWordMap;

/**
* 初始化敏感词库,构建DFA算法模型
*/
public static void initContext(HashSet<String> set) {
initSensitiveWordMap(set);
}

/**
* 初始化敏感词库,构建DFA算法模型
*
* @param sensitiveWordSet 敏感词库
*/
private static void initSensitiveWordMap(Set<String> sensitiveWordSet) {
//初始化敏感词容器,减少扩容操作
sensitiveWordMap = new HashMap<String, String>(sensitiveWordSet.size());
Map<Object, Object> temp;
Map<Object, Object> newWorMap;
//遍历sensitiveWordSet
for (String key : sensitiveWordSet) {
temp = sensitiveWordMap;
for (int i = 0; i < key.length(); i++) {
//转换成char型
char keyChar = key.charAt(i);
//库中获取关键字
Object wordMap = temp.get(keyChar);
//如果存在该key,直接赋值,用于下一个循环获取
if (wordMap != null) {
temp = (Map) wordMap;
} else {
//不存在则,则构建一个map,同时将isEnd设置为0,因为他不是最后一个
newWorMap = new HashMap<>();
//不是最后一个
newWorMap.put("isEnd", "0");
temp.put(keyChar, newWorMap);
temp = newWorMap;
}
//最后一个
if (i == key.length() - 1) temp.put("isEnd", "1");
}
}
}

/**
* 判断文字是否包含敏感字符
* <p>
* 文本
* <p>
* 若包含返回true,否则返回false
*/
public static boolean contains(String txt) {
boolean flag = false;
for (int i = 0; i < txt.length(); i++) {
int matchFlag = checkSensitiveWord(txt, i); //判断是否包含敏感字符
if (matchFlag > 0) {//大于0存在,返回true
flag = true;
}
}
return flag;
}

/**
* 检查文字中是否包含敏感字符,检查规则如下:
*
* @param txt
* @param beginIndex
* @return 如果存在, 则返回敏感词字符的长度, 不存在返回0
*/
private static int checkSensitiveWord(String txt, int beginIndex) {
//敏感词结束标识位:用于敏感词只有1位的情况
boolean flag = false;
//匹配标识数默认为0
int matchFlag = 0;
char word;
Map nowMap = sensitiveWordMap;
for (int i = beginIndex; i < txt.length(); i++) {
word = txt.charAt(i);
//获取指定key
nowMap = (Map) nowMap.get(word);
if (nowMap != null) {//存在,则判断是否为最后一个
//找到相应key,匹配标识+1
matchFlag++;
//如果为最后一个匹配规则,结束循环,返回匹配标识数
if ("1".equals(nowMap.get("isEnd"))) {
//结束标志位为true
flag = true;
}
} else {//不存在,直接返回
break;
}
}
if (matchFlag < 2 || !flag) {//长度必须大于等于1,为词
matchFlag = 0;
}
return matchFlag;
}

/**
* 获取文字中的敏感词
* <p>
* txt文字
*/
public static HashSet getSensitiveWord(String txt) {
HashSet hashSet = new HashSet();
for (int i = 0; i < txt.length(); i++) {
//判断是否包含敏感字符
int length = checkSensitiveWord(txt, i);
if (length > 0) {//存在,加入list中
hashSet.add(txt.substring(i, i + length));
i = i + length - 1;//减1的原因,是因为for会自增
}
}
return hashSet;
}


/**
* context是要校验的内容。返回结果是list,为空说明没有敏感词
*
* @param context
* @return
*/
public static HashSet checkTxt(String context, HashSet<String> set) {
initContext(set);
//包含敏感词返回所有敏感词数据
return getSensitiveWord(context);
}
}

2、工具类使用

1
2
3
4
5
6
7
8
9
10
11
12
13
//敏感词
HashSet<String> set = new HashSet<>();
//查询敏感词数据库,这里我是查询的自己的数据库
List<Map> isSensitive = userService.findIsSensitive(username);
for (Map is : isSensitive) {
//获取敏感词,set 进 HashSet 进行比对
set.add(is.getString("sensitive_word"));
}
// SensitiveFilterUtil.checkTxt(username, set) 为使用 DFA 算法进行敏感词检测,传入 username 为需要检测的字段。当 checkTxt() 查出来为空,则代表没有敏感词
if (StringUtils.isNotEmpty(SensitiveFilterUtil.checkTxt(username, set))) {
msg = "用户名包含敏感词,请重新输入";
return msg;
}

Java DAF 有穷自动机算法算法实现敏感词检测
https://tdsgpo.top/2022/09/21/Java DAF 有穷自动机算法算法实现敏感词检测/
作者
DDS
发布于
2022年9月21日
许可协议