敏感词过滤算法-前缀树-java

2023-06-27 263

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 敏感词过滤算法-前缀树-java

前言

最近在做网上一个比较热门的博客项目，其中用到了前缀树进行敏感词过滤，这里记录一下

定义

• 前缀树

- 名称：Trie、字典树、查找树

- 特点：查找效率高，消耗内存大

- 应用：字符串检索、词频统计、字符串排序等

步骤

- 定义前缀树

- 根据敏感词，初始化前缀树

- 编写过滤敏感词的方法

过程

我们先定义一颗前缀树，在程序开始阶段创建前缀树对敏感词进行保存，便于后续的查找

1. // 前缀树
2. private class TrieNode {
3. 
4. // 关键词结束标识
5. private boolean isKeywordEnd = false;
6. 
7. // 子节点(key是下级字符,value是下级节点)
8. private Map<Character, TrieNode> subNodes = new HashMap<>();
9. 
10. public boolean isKeywordEnd() {
11. return isKeywordEnd;
12.         }
13. 
14. public void setKeywordEnd(boolean keywordEnd) {
15.             isKeywordEnd = keywordEnd;
16.         }
17. 
18. // 添加子节点
19. public void addSubNode(Character c, TrieNode node) {
20.             subNodes.put(c, node);
21.         }
22. 
23. // 获取子节点
24. public TrieNode getSubNode(Character c) {
25. return subNodes.get(c);
26.         }
27. 
28.     }

1. @PostConstruct
2. public void init() {
3. try (
4. InputStream is = this.getClass().getClassLoader().getResourceAsStream("sensitive-words.txt");
5. BufferedReader reader = new BufferedReader(new InputStreamReader(is));
6.         ) {
7.             String keyword;
8. while ((keyword = reader.readLine()) != null) {
9. // 添加到前缀树
10. this.addKeyword(keyword);
11.             }
12.         } catch (IOException e) {
13.             logger.error("加载敏感词文件失败: " + e.getMessage());
14.         }
15.     }
16. 
17. // 将一个敏感词添加到前缀树中
18. private void addKeyword(String keyword) {
19. TrieNode tempNode = rootNode;
20. for (int i = 0; i < keyword.length(); i++) {
21. char c = keyword.charAt(i);
22. TrieNode subNode = tempNode.getSubNode(c);
23. 
24. if (subNode == null) {
25. // 初始化子节点
26.                 subNode = new TrieNode();
27.                 tempNode.addSubNode(c, subNode);
28.             }
29. 
30. // 指向子节点,进入下一轮循环
31.             tempNode = subNode;
32. 
33. // 设置结束标识
34. if (i == keyword.length() - 1) {
35.                 tempNode.setKeywordEnd(true);
36.             }
37.         }
38.     }

在后续的搜索过程中，我们设置三个指针，指针1指向树，指针2，3指向字符串，具体流程见代码

1. /**
2.      * 过滤敏感词
3.      *
4.      * @param text 待过滤的文本
5.      * @return 过滤后的文本
6.      */
7. public String filter(String text) {
8. if (StringUtils.isBlank(text)) {
9. return null;
10.         }
11. 
12. // 指针1
13. TrieNode tempNode = rootNode;
14. // 指针2
15. int begin = 0;
16. // 指针3
17. int position = 0;
18. // 结果
19. StringBuilder sb = new StringBuilder();
20. 
21. while (position < text.length()) {
22. char c = text.charAt(position);
23. 
24. // 跳过符号
25. if (isSymbol(c)) {
26. // 若指针1处于根节点,将此符号计入结果,让指针2向下走一步
27. if (tempNode == rootNode) {
28.                     sb.append(c);
29.                     begin++;
30.                 }
31. // 无论符号在开头或中间,指针3都向下走一步
32.                 position++;
33. continue;
34.             }
35. 
36. // 检查下级节点
37.             tempNode = tempNode.getSubNode(c);
38. if (tempNode == null) {
39. // 以begin开头的字符串不是敏感词
40.                 sb.append(text.charAt(begin));
41. // 进入下一个位置
42.                 position = ++begin;
43. // 重新指向根节点
44.                 tempNode = rootNode;
45.             } else if (tempNode.isKeywordEnd()) {
46. // 发现敏感词,将begin~position字符串替换掉
47.                 sb.append(REPLACEMENT);
48. // 进入下一个位置
49.                 begin = ++position;
50. // 重新指向根节点
51.                 tempNode = rootNode;
52.             } else {
53. // 检查下一个字符
54. if(position<text.length()-1){
55.                     position++;
56.                 }
57.             }
58.         }
59. 
60. // 将最后一批字符计入结果
61.         sb.append(text.substring(begin));
62. 
63. return sb.toString();
64.     }
65. 
66. // 判断是否为符号
67. private boolean isSymbol(Character c) {
68. // 0x2E80~0x9FFF 是东亚文字范围
69. return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF);
70.     }

测试

完整代码

1. @Component
2. public class SensitiveFilter {
3. 
4. // 实例化log
5. private static final Logger logger = LoggerFactory.getLogger(SensitiveFilter.class);
6. 
7. // 替换符
8. private static final String REPLACEMENT = "***";
9. 
10. // 根节点
11. private TrieNode rootNode = new TrieNode();
12. 
13. @PostConstruct
14. public void init() {
15. try (
16. InputStream is = this.getClass().getClassLoader().getResourceAsStream("sensitive-words.txt");
17. BufferedReader reader = new BufferedReader(new InputStreamReader(is));
18.         ) {
19.             String keyword;
20. while ((keyword = reader.readLine()) != null) {
21. // 添加到前缀树
22. this.addKeyword(keyword);
23.             }
24.         } catch (IOException e) {
25.             logger.error("加载敏感词文件失败: " + e.getMessage());
26.         }
27.     }
28. 
29. // 将一个敏感词添加到前缀树中
30. private void addKeyword(String keyword) {
31. TrieNode tempNode = rootNode;
32. for (int i = 0; i < keyword.length(); i++) {
33. char c = keyword.charAt(i);
34. TrieNode subNode = tempNode.getSubNode(c);
35. 
36. if (subNode == null) {
37. // 初始化子节点
38.                 subNode = new TrieNode();
39.                 tempNode.addSubNode(c, subNode);
40.             }
41. 
42. // 指向子节点,进入下一轮循环
43.             tempNode = subNode;
44. 
45. // 设置结束标识
46. if (i == keyword.length() - 1) {
47.                 tempNode.setKeywordEnd(true);
48.             }
49.         }
50.     }
51. 
52. /**
53.      * 过滤敏感词
54.      *
55.      * @param text 待过滤的文本
56.      * @return 过滤后的文本
57.      */
58. public String filter(String text) {
59. if (StringUtils.isBlank(text)) {
60. return null;
61.         }
62. 
63. // 指针1
64. TrieNode tempNode = rootNode;
65. // 指针2
66. int begin = 0;
67. // 指针3
68. int position = 0;
69. // 结果
70. StringBuilder sb = new StringBuilder();
71. 
72. while (position < text.length()) {
73. char c = text.charAt(position);
74. 
75. // 跳过符号
76. if (isSymbol(c)) {
77. // 若指针1处于根节点,将此符号计入结果,让指针2向下走一步
78. if (tempNode == rootNode) {
79.                     sb.append(c);
80.                     begin++;
81.                 }
82. // 无论符号在开头或中间,指针3都向下走一步
83.                 position++;
84. continue;
85.             }
86. 
87. // 检查下级节点
88.             tempNode = tempNode.getSubNode(c);
89. if (tempNode == null) {
90. // 以begin开头的字符串不是敏感词
91.                 sb.append(text.charAt(begin));
92. // 进入下一个位置
93.                 position = ++begin;
94. // 重新指向根节点
95.                 tempNode = rootNode;
96.             } else if (tempNode.isKeywordEnd()) {
97. // 发现敏感词,将begin~position字符串替换掉
98.                 sb.append(REPLACEMENT);
99. // 进入下一个位置
100.                 begin = ++position;
101. // 重新指向根节点
102.                 tempNode = rootNode;
103.             } else {
104. // 检查下一个字符
105. if(position<text.length()-1){
106.                     position++;
107.                 }
108.             }
109.         }
110. 
111. // 将最后一批字符计入结果
112.         sb.append(text.substring(begin));
113. 
114. return sb.toString();
115.     }
116. 
117. // 判断是否为符号
118. private boolean isSymbol(Character c) {
119. // 0x2E80~0x9FFF 是东亚文字范围
120. return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF);
121.     }
122. 
123. // 前缀树
124. private class TrieNode {
125. 
126. // 关键词结束标识
127. private boolean isKeywordEnd = false;
128. 
129. // 子节点(key是下级字符,value是下级节点)
130. private Map<Character, TrieNode> subNodes = new HashMap<>();
131. 
132. public boolean isKeywordEnd() {
133. return isKeywordEnd;
134.         }
135. 
136. public void setKeywordEnd(boolean keywordEnd) {
137.             isKeywordEnd = keywordEnd;
138.         }
139. 
140. // 添加子节点
141. public void addSubNode(Character c, TrieNode node) {
142.             subNodes.put(c, node);
143.         }
144. 
145. // 获取子节点
146. public TrieNode getSubNode(Character c) {
147. return subNodes.get(c);
148.         }
149. 
150.     }
151. 
152. }

敏感词过滤算法-前缀树-java

前言

定义

步骤

过程

测试

完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

敏感词过滤算法-前缀树-java

前言

定义

步骤

过程

测试

完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景