引入
在笔者的项目中有一个对敏感词检测并替换的需求，这个需求应该算很常见的，而且也有很多的方式可以解决，主要的解决方式有这几种：
- 暴力匹配
- KMP算法
- Trie（字典树）
- AC自动机
- 正则匹配
- ……
在本文及笔者的项目中采用了Trie的方式，其他的实现方式笔者感兴趣可以自行了解。采用Trie的优缺点如下：
优点：
- 节省了大量的字符存储空间和字符匹配时间
- 随着字典树不断完善，新增的分支会越来越少
缺点：
下面我们来看看如何实现
Trie
Trie也就是字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
在一般的设计中，要求Trie在结构设计中：
本文中的实现也采用上述原则，实现代码如下所示：
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
|
public class TrieNode {
private Character data;
private boolean end = false;
private final Map<Character, TrieNode> nextNodes;
public TrieNode() {
nextNodes = new HashMap<>();
}
public TrieNode(Character data) {
this.data = data;
nextNodes = new HashMap<>();
}
public boolean isEnd() {
return end;
}
public void setEnd(boolean end) {
this.end = end;
}
public TrieNode getNextNode(Character data) {
return nextNodes.get(data);
}
public TrieNode addNextNode(Character character) {
if (nextNodes.get(character) == null) {
nextNodes.put(character, new TrieNode(character));
}
return nextNodes.get(character);
}
}
|
敏感词检测并替换
在本文中，敏感词检测及替换的原则是先根据敏感词先建立对应的字典树（在项目中要注意将其设为单例的，避免敏感词缺失或者造成空间浪费），然后再根据要检测或修改的字符串逐位进行匹配：
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
public class IllegalWordMatcher {
private final TrieNode root = new TrieNode();
public void setMatchList(List<String> matchList) {
matchList.forEach(this::addWord);
}
public void addWord(CharSequence word) {
int n = word.length();
TrieNode temp = root;
for (int i = 0; i < n - 1; i++) {
temp = temp.addNextNode(word.charAt(i));
}
temp.addNextNode(word.charAt(n - 1)).setEnd(true);
}
public String replace(CharSequence text) {
return replace(text, '*');
}
public String replace(CharSequence text, Character replace) {
if (isBlank(text)) {
return text.toString();
}
assert root.getKeyWordCount() != 0: "The match trie is null";
StringBuilder result = new StringBuilder();
int size = text.length();
int begin = 0, now = 0;
TrieNode temp = root;
while (now < size) {
TrieNode next = temp.getNextNode(text.charAt(now));
if (next == null) {
result.append(text.charAt(begin));
now = begin + 1;
begin = now;
temp = root;
}
else if (next.isEnd()) {
for (int i = begin; i <= now; i++) {
result.append(replace);
}
now++;
begin = now;
temp = root;
}
else {
now++;
temp = next;
}
}
result.append(text.subSequence(begin, text.length()));
return result.toString();
}
public boolean isLegal(String text) {
if (isBlank(text)) {
return true;
}
assert root.getKeyWordCount() != 0: "The match trie is null";
int size = text.length();
int begin = 0, now = 0;
TrieNode temp = root;
char[] textChars = text.toCharArray();
while (now < size) {
TrieNode next = temp.getNextNode(text.charAt(now));
if (next == null) {
now = begin + 1;
begin = now;
temp = root;
}
else if (next.isEnd()) {
return false;
}
else {
now++;
}
}
return true;
}
public boolean isBlank(CharSequence charSequence) {
if (charSequence == null || "".contentEquals(charSequence)) {
return true;
}
for (int i = 0; i < charSequence.length(); i++) {
if (charSequence.charAt(i) != ' ') {
return false;
}
}
return true;
}
}
|
总结
这次的分享就到这里了，建议读者可以自己实现一下，在这里还推荐一款高性能非法词(敏感词)检测组件 ToolGood.Words(Java版)，支持多语言版本，感兴趣的读者还可以看看源码参照他的实现。
