前言
最近在做网上一个比较热门的博客项目，其中用到了前缀树进行敏感词过滤，这里记录一下
定义
• 前缀树
- 名称：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. }
