项目场景
基于 Spring Boot 的论坛系统:用户发布的内容需进行敏感词过滤。
前置知识
前缀树
- Q:前缀树和普通N叉树的区别?
- A:前缀树(Trie,也称字典树、单词查找树或键树)。
- 设计目的:
- 前缀树:专门设计用于高效地存储和检索字符串集合中的键(字符串)。它的结构允许快速的查找、插入和删除操作,特别适合于字符串前缀匹配,如自动补全、拼写检查、敏感词过滤等场景。
- 普通N叉树:是一种更通用的树形数据结构,其中每个节点可以有任意数量(包括零)的子节点,最多可达N个。它没有特定于字符串处理的特性,广泛应用于各种需要多路分支的数据结构场景,如文件系统的目录结构、表达式树等。
- 节点结构:
- 前缀树:每个节点通常包含一个字符和一个映射到其子节点的字符到节点的映射(如HashMap或数组)。根节点通常不表示任何字符,而从根到任意叶节点的路径上的字符序列组成一个字符串,叶节点或标记为关键词结束的节点代表一个完整的字符串。
- 普通N叉树:节点可能包含数据以及指向其子节点的指针数组或列表,但这些子节点之间的关系不一定有特定的字符关联,节点的数据结构和含义更多样。
- 查找效率:
- 前缀树:由于其特殊的结构设计,前缀树支持高效的前缀匹配,可以在O(L)时间内(L为关键词长度)查找到所有具有相同前缀的字符串,或者确定某个字符串是否在集合中。
- 普通N叉树:查找效率依赖于树的具体形态和查找算法,一般情况下不如前缀树在字符串前缀匹配上的效率高。
- 空间利用率:
- 前缀树:可能会有较高的空间消耗,因为它存储了所有字符串的公共前缀,特别是当存储的字符串有很多相似前缀时。
- 普通N叉树:空间使用更加灵活,取决于树的形状,但通常不会为了存储前缀信息而额外消耗空间。
- 设计目的:
总之,前缀树是一种针对字符串处理优化的特殊N叉树,强调了字符串前缀的高效存储和查询,而普通N叉树则是一种更为通用的结构,适用于多种类型的多路分支数据组织。
实现方式
解决方案一:读取敏感词文件生成前缀树+构建敏感词过滤器
前缀树
- 名称:Trie 、字典树、查找树
- 特点:查找效率高,消耗内存大
- 应用:字符串检索、词频统计、字符串排序等
敏感词过滤器
- 定义前缀树
- 根据敏感词,初始化前缀树
- 编写过滤敏感词的方法
1. 导入敏感词文件 src/main/resources/sensitive_words.txt
此处为示例文件内容。
1
2
3
4
5
6
|
元 购物车 fuck abc bf be |
2. 构建敏感词过滤器 SensitiveFilter
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
package com.example.filter; import com.example.constant.SensitiveConstant; import lombok.extern.slf4j.Slf4j; import org.apache.commons.lang3.CharUtils; import org.apache.commons.lang3.StringUtils; import org.springframework.stereotype.Component; import javax.annotation.PostConstruct; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; /** * 敏感词过滤器 */ @Slf4j @Component public class SensitiveFilter { // 创建前缀树的根节点 private final TrieNode rootNode = new TrieNode(); /** * 初始化,读取敏感词 */ @PostConstruct // 确保在Bean初始化后执行 public void init() { // 1. 从类路径加载敏感词文件: 使用文件存储敏感词库可以直接进行一次性读取和处理,无需依赖数据库系统,并且保证离线可用。 try (InputStream inputStream = this .getClass().getClassLoader().getResourceAsStream(SensitiveConstant.SENSITIVE_WORDS_FILE); InputStreamReader inputStreamReader = new InputStreamReader(inputStream); BufferedReader bufferedReader = new BufferedReader(inputStreamReader); // Java 7及以后的版本中,引入了一项称为"try-with-resources"的新特性,它允许自动管理资源,确保在try语句块执行完毕后,不论是否发生异常,都会正确关闭或释放资源 ) { // 2. 逐行读取敏感词并加入到前缀树中 String keyword; while ((keyword = bufferedReader.readLine()) != null ) { this .addKeyWord(keyword); } } catch (IOException ex) { log.error( "敏感词文件读取失败: " + ex.getMessage()); } } /** * 将敏感词添加到前缀树中 * @param keyword 待添加的敏感词 */ private void addKeyWord(String keyword) { // 1. 初始化操作,将当前处理节点设为根节点 TrieNode tempNode = rootNode; // 2. 将待添加的敏感词字符串转换为字符数组以便遍历 char [] chars = keyword.toCharArray(); // 3. 遍历字符数组,逐个字符构建前缀树 for ( int i = 0 ; i < chars.length; i++) { // 3.1. 从当前处理节点的子节点Map中获取当前字符对应的节点 TrieNode childrenNode = tempNode.getChildrenNode(chars[i]); // 3.1.1 若当前字符没有对应的节点,则创建一个新节点,并放入当前处理节点的子节点Map中 if (childrenNode == null ) { childrenNode = new TrieNode(); tempNode.setChildrenNode(chars[i], childrenNode); } // 3.2. 若当前字符为敏感词字符串的最后一个字符,则标记当前字符的对应节点为敏感词的结尾节点 if (i == chars.length - 1 ) { childrenNode.setKeywordEnd( true ); } // 3.3. 移动到下一层,使当前字符对应的节点成为新的当前处理节点,继续构建或遍历过程 tempNode = childrenNode; } } /** * 过滤文本,移除或替换其中的敏感词,并返回处理后的文本 * @param text 待过滤的文本 * @return 过滤后的文本 */ public String filter(String text) { // 1. 检查输入文本是否为空或仅包含空白字符,如果是,则直接返回null,表示无内容无需过滤 if (StringUtils.isBlank(text)) { return null ; } // 2. 初始化变量 TrieNode tempNode = rootNode; // 2.1. 初始化为前缀树的根节点,用于遍历查找。 int begin = 0 , end = 0 ; // 2.2. 分别用于标记待检查文本区间的起始和结束位置 StringBuilder result = new StringBuilder(); // 2.3. 累积过滤后的文本 // 3. 遍历整个文本进行过滤处理 while (begin < text.length()) { char c = text.charAt(end); // 3.1. 遇到符号字符 if (isSymbol(c)) { // 3.1.1. 如果当前处于根节点,即没有匹配到任何敏感词的开始,直接保留符号,并移动begin if (tempNode == rootNode) { result.append(c); begin++; } // 3.1.2. 跳过当前符号,并继续检查下一个字符 end++; continue ; } // 3.2. 检查当前字符区间text[begin...end]是否是某个敏感词的一部分 tempNode = tempNode.getChildrenNode(c); // 3.2.1. 如果当前字符没有对应的子节点,即text[begin...end]不是敏感词的组成部分 if (tempNode == null ) { result.append(text.charAt(begin)); // 3.2.1.1. 保存begin位置的字符到结果 end = ++begin; // 3.2.1.2. 移动begin和end指针,准备检查下一个可能的敏感词 begin++; end = begin; tempNode = rootNode; // 3.2.1.3. 重置tempNode为根节点准备下一轮匹配 } // 3.2.2. 如果当前字符路径已到达一个敏感词的结尾,即text[begin...end]是敏感词 else if (tempNode.isKeywordEnd()) { result.append(StringUtils.repeat(SensitiveConstant.REPLACEMENT, end - begin + 1 )); // 3.2.2.1. 替换敏感词区间 begin = ++end; // 3.2.2.2. 移动begin和end指针,准备检查下一个可能的敏感词 end++; begin = end; tempNode = rootNode; // 3.2.2.3. 重置tempNode为根节点准备下一轮匹配 } // 3.2.3. 如果当前字符区间text[begin...end]是潜在敏感词的一部分但不是结尾,继续匹配下一个字符 else { // 3.2.3.1. 检查下一个字符是否存在,存在则移动end指针;否则,回退begin到当前位置,准备重新匹配 if (end < text.length() - 1 ) { end++; } else { end = begin; } } } // 4. 将剩余未检查的文本(若有)添加到结果中 result.append(text.substring(begin)); // 5. 返回过滤后的文本 return result.toString(); } /** * 判断字符是否为符号字符 * @param character 待判断的字符 * @return true表示是符号字符,需要跳过;false表示不是符号字符,不跳过 */ private boolean isSymbol(Character character) { // 0x2E80~0x9FFF是东亚文字: 判断字符是否不属于ASCII字母数字且不在东亚文字范围内 return !CharUtils.isAsciiAlphanumeric(character) && (character < 0x2E80 || character > 0x9FFF ); } /** * 内部类,定义前缀树的节点 */ private static class TrieNode { private boolean isKeywordEnd = false ; // 当前节点是否为敏感词的末尾节点 private final Map<Character, TrieNode> childrenNode = new HashMap<>(); // 当前节点的子节点 // Getter和Setter方法 public boolean isKeywordEnd() { return isKeywordEnd; } public void setKeywordEnd( boolean keywordEnd) { isKeywordEnd = keywordEnd; } public TrieNode getChildrenNode(Character c) { return childrenNode.get(c); } public void setChildrenNode(Character c, TrieNode node) { childrenNode.put(c, node); } } } |
这里我把敏感词过滤器的相关常量都写到一个常量类里了,也可以直接写在过滤器里。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package com.example.constant; /** * 敏感词过滤器的相关常量 */ public class SensitiveConstant { /** * 敏感词文件名称 */ public static final String SENSITIVE_WORDS_FILE = "sensitive_words.txt" ; /** * 用于替换敏感词的字符 */ public static final Character REPLACEMENT = '*' ; } |
3. 测试与使用
创建一个测试类测一下就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package com.example.filter; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import static org.junit.jupiter.api.Assertions.*; @SpringBootTest class SensitiveFilterTest { @Autowired private SensitiveFilter sensitiveFilter; @Test void filter() { String result = sensitiveFilter.filter( "accfuckxx元bitch购物车bitchjwbc" ); System.out.println(result); } } |
运行结果:
acc****xx*bitch***bitchjwbc
可以实现过滤,但是完全基于敏感词文件内容,需要自行完善文件。也许可以结合正则表达式扩展?不是很灵活,没研究过了。
解决方案二:使用第三方插件 houbb/sensitive-word(推荐)
houbb/sensitive-word
项目源码:https://github.com/houbb/sensitive-word
1. 添加依赖
1
2
3
4
5
|
< dependency > < groupId >com.github.houbb</ groupId > < artifactId >sensitive-word</ artifactId > < version >0.17.0</ version > </ dependency > |
2. 测试与使用(使用默认过滤策略)
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
|
package com.example.filter; import com.github.houbb.sensitive.word.core.SensitiveWordHelper; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import static org.junit.jupiter.api.Assertions.*; @SpringBootTest class SensitiveFilterTest { @Autowired private SensitiveFilter sensitiveFilter; @Test void filter() { String result = sensitiveFilter.filter( "accfuckxx元bitch购物车bitchjwbc" ); System.out.println(result); System.out.println( "-------------------------------" ); result = SensitiveWordHelper.replace( "accfuckxx元bitch购物车bitchjwbc" ); System.out.println(result); result = SensitiveWordHelper.replace( "Ⓕⓤc⒦ the bad words" ); System.out.println(result); result = SensitiveWordHelper.replace( "ⒻⒻⒻfⓤuⓤ⒰cⓒ⒦ the bad words" ); System.out.println(result); result = SensitiveWordHelper.replace( "fffuuck the bad words" ); System.out.println(result); } } |
运行结果:
acc****xx*bitch***bitchjwbc
——————————-
acc****xx元bitch购物车bitchjwbc
**** the bad words
ⒻⒻⒻfⓤuⓤ⒰cⓒ⒦ the bad words
fffuuck the bad words
可以实现基础过滤。比读取文件更方便。
(忽略掉这里的“元”和“购物车”。只是为了文章过审把一些很offensive的词换成了随便写的词嗯。)
如果要设置更多需要过滤的内容,可以参考以下步骤。
3. 构建配置类SensitiveWordConfig
(使用自定义过滤策略)
自己按照需求调一下就好。
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
|
package com.example.config; import com.github.houbb.sensitive.word.bs.SensitiveWordBs; import com.github.houbb.sensitive.word.support.ignore.SensitiveWordCharIgnores; import com.github.houbb.sensitive.word.support.resultcondition.WordResultConditions; import com.github.houbb.sensitive.word.support.tag.WordTags; import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; /** * 配置类,用于设置敏感词过滤器的自定义过滤策略 * 更多配置见 https://github.com/houbb/sensitive-word */ @Configuration public class SensitiveWordConfig { /** * 初始化引导类 * @return 初始化引导类 * @since 1.0.0 */ @Bean public SensitiveWordBs sensitiveWordBs() { SensitiveWordBs wordBs = SensitiveWordBs.newInstance() .ignoreCase( true ) // 忽略大小写,默认值为true .ignoreWidth( true ) // 忽略半角圆角,默认值为true .ignoreNumStyle( true ) // 忽略数字的写法,默认值为true .ignoreChineseStyle( true ) // 忽略中文的书写格式,默认值为true .ignoreEnglishStyle( true ) // 忽略英文的书写格式,默认值为true .ignoreRepeat( false ) // 忽略重复词,默认值为false .enableNumCheck( false ) // 是否启用数字检测,默认值为false .enableEmailCheck( false ) // 是有启用邮箱检测,默认值为false .enableUrlCheck( false ) // 是否启用链接检测,默认值为false .enableIpv4Check( false ) // 是否启用IPv4检测,默认值为false .enableWordCheck( true ) // 是否启用敏感单词检测,默认值为true .numCheckLen( 8 ) // 数字检测,自定义指定长度,默认值为8 .wordTag(WordTags.none()) // 词对应的标签,默认值为none .charIgnore(SensitiveWordCharIgnores.defaults()) // 忽略的字符,默认值为none .wordResultCondition(WordResultConditions.alwaysTrue()) // 针对匹配的敏感词额外加工,比如可以限制英文单词必须全匹配,默认恒为真 .init(); return wordBs; } } |
4. 测试与使用(使用自定义过滤策略)
在刚刚的配置类中已经启用了数字检测。
1
|
.enableNumCheck( true ) // 是否启用数字检测,默认值为false |
测一下。
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
|
package com.example.filter; import com.github.houbb.sensitive.word.bs.SensitiveWordBs; import com.github.houbb.sensitive.word.core.SensitiveWordHelper; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import static org.junit.jupiter.api.Assertions.*; @SpringBootTest class SensitiveFilterTest { ... @Autowired private SensitiveWordBs sensitiveWordBs; ... @Test void test() { String result = sensitiveWordBs.replace( "accfuckxx元bitch购物车bitchjwbc" ); System.out.println(result); result = sensitiveWordBs.replace( "Ⓕⓤc⒦ the bad words" ); System.out.println(result); result = sensitiveWordBs.replace( "ⒻⒻⒻfⓤuⓤ⒰cⓒ⒦ the bad words" ); System.out.println(result); result = sensitiveWordBs.replace( "fffuuck the bad words" ); System.out.println(result); result = sensitiveWordBs.replace( "12345678dwnoxcw" ); System.out.println(result); result = sensitiveWordBs.replace( "123456789dwnoxcw" ); System.out.println(result); result = sensitiveWordBs.replace( "一二三四五六七八九dwnoxcw" ); System.out.println(result); result = sensitiveWordBs.replace( "这个是我的微信:9⓿二肆⁹₈③⑸⒋➃㈤㊄" ); System.out.println(result); } } |
运行结果:
acc****xx元bitch购物车bitchjwbc
**** the bad words
*********** the bad words
******* the bad words
********dwnoxcw
*********dwnoxcw
*********dwnoxcw
这个是我的微信:************
就很好用了。
(忽略掉这里的“元”和“购物车”。只是为了文章过审把一些很offensive的词换成了随便写的词嗯。)
两种实现方式的对比
- 自行构建前缀树过滤器:
- 优势:高度定制,易于理解与维护,无外部依赖。
- 劣势:开发耗时,需优化性能,学习成本。
- 使用第三方开源项目:
- 优势:快速集成,功能成熟,社区支持。
- 劣势:依赖管理,安全风险,定制受限。
根据项目需求紧迫性、定制化需求及团队技术背景综合选择。简单需求或有定制化要求倾向自建;追求快速、功能全面则推荐使用现成开源方案。