1.前缀树

- 名称：Trie、字典树、查找树 - 特点：查找效率高，消耗内存大 - 应用：字符串检索、词频统计、字符串排序等

2.敏感词过滤器

- 定义前缀树 - 根据敏感词，初始化前缀树 - 编写过滤敏感词的方法

3.代码实现

@Component public class SensitiveFilter { private static final Logger logger = LoggerFactory.getLogger(SensitiveFilter.class); // 替换符 private static final String REPLACEMENT = "***"; // 初始化根节点 private TrieNode rootNode = new TrieNode(); @PostConstruct public void init() { try ( InputStream is = this.getClass().getClassLoader().getResourceAsStream("sensitive-words.txt"); BufferedReader reader = new BufferedReader(new InputStreamReader(is)); ) { String keyword; while ((keyword = reader.readLine()) != null) { // 添加到前缀树 this.addKeyword(keyword); } } catch (IOException e) { logger.error("加载敏感词文件失败: " + e.getMessage()); } } // 将一个敏感词添加到前缀树中 private void addKeyword(String keyword) { TrieNode tempNode = rootNode; for (int i = 0; i < keyword.length(); i++) { char c = keyword.charAt(i); // 查看是否有这个子节点 TrieNode subNode = tempNode.getSubNode(c); // 没有就创建 if (subNode == null) { // 初始化子节点 subNode = new TrieNode(); tempNode.addSubNode(c, subNode); } // 指向子节点,进入下一轮循环 tempNode = subNode; // 设置结束标识 if (i == keyword.length() - 1) { tempNode.setKeywordEnd(true); } } } /** * 过滤敏感词 * * @param text 待过滤的文本 * @return 过滤后的文本 */ public String filter(String text) { if (StringUtils.isBlank(text)) { return null; } // 指针1，指向根 TrieNode tempNode = rootNode; // 指针2，不回头，一直向前移动 int begin = 0; // 指针3 int position = 0; // 结果 StringBuilder sb = new StringBuilder(); // 因为指针3会先达到最后位置，所以用指针3作为判断条件会减少循环 while (position < text.length()) { char c = text.charAt(position); // 跳过符号 if (isSymbol(c)) { // 若指针1处于根节点,将此符号计入结果,让指针2向下走一步 if (tempNode == rootNode) { sb.append(c); begin++; } // 无论符号在开头或中间,指针3都向下走一步 position++; continue; } // 检查下级节点 tempNode = tempNode.getSubNode(c); // 以begin开头的字符串不是敏感词 if (tempNode == null) { sb.append(text.charAt(begin)); // 进入下一个位置，begin向右移动，并且position和begin保持一致。 position = ++begin; // 归位：重新指向根节点 tempNode = rootNode; } else if (tempNode.isKeywordEnd()) { // 发现敏感词,将begin-position字符串替换掉 sb.append(REPLACEMENT); // 进入下一个位置 begin = ++position; // 重新指向根节点 tempNode = rootNode; } else { // 检查下一个字符 position++; } } // 将最后一批字符计入结果 sb.append(text.substring(begin)); return sb.toString(); } // 判断是否为符号 private boolean isSymbol(Character c) { // 0x2E80~0x9FFF 是东亚文字范围 return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF); } // 前缀树结构 private class TrieNode { // 关键词结束标识 private boolean isKeywordEnd = false; // 子节点(key是下级字符,value是下级节点) private Map<Character, TrieNode> subNodes = new HashMap<>(); public boolean isKeywordEnd() { return isKeywordEnd; } public void setKeywordEnd(boolean keywordEnd) { isKeywordEnd = keywordEnd; } // 添加子节点 public void addSubNode(Character c, TrieNode node) { subNodes.put(c, node); } // 获取子节点 public TrieNode getSubNode(Character c) { return subNodes.get(c); } } }