不要再用replaceAll做敏感词替换了(Java实现),无需第三方依赖

问题描述

在处理文本数据时，我们经常需要对敏感词进行过滤。这是一个常见的需求，尤其是在社交媒体、论坛和评论系统等需要用户生成内容的场景中。

很多人第一反应就是用replace实现敏感词的替换，这个方法虽然可以实现，但是效率实在太低，因为敏感词不是只有一个，可能会达到上万个，每次都用replace替换一遍，效率太低了。

最经典的敏感词算法可以用Trie树来实现，Trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

实现原理

我们需要实现一个敏感词过滤器，主要包括以下几个步骤：

构建一个Trie树，将敏感词存储在树中
遍历文本，查找是否包含敏感词
如果包含敏感词，替换成*号
返回过滤后的文本

Trie树的每个节点代表一个字符串（前缀），每个节点都有多个子节点，每个子节点代表一个字符。在Trie树中查找字符串的时间复杂度为O(n)，其中n为字符串的长度。

看一下Trie树的存储结构： trie

意味着相同前缀的字符串，Trie树中的节点可以共享，这样可以节省空间，比如"apple"和"app"的前缀"app"可以共享，只要文本中出现app开头的敏感词，就可以直接从app节点开始查找，而不是每个单词从新开始查找。

我们可以遍历文本中的每个字符，然后使用Trie树来检查是否存在以该字符开始的敏感词。如果存在敏感词，就用指定的替换词替换该敏感词。

Java的实现

Trie树的实现

定义了一个 TrieNode 类，用于表示Trie树中的节点。每个节点都有一个 isEnd 属性，表示该节点是否是一个单词的结束，以及一个 children 属性，表示该节点的子节点。

public class TrieNode {
    public boolean isEnd;
    public Map<Character, TrieNode> children = new HashMap<>();

    public TrieNode() {
        isEnd = false;
    }
}

定义了一个 Trie 类，用于表示Trie树。这个类有一个 root 属性，表示Trie树的根节点，以及 insert 和 search 方法，用于向Trie树中插入单词和搜索单词。

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return node.isEnd;
    }
}

实现敏感词的替换

使用 replaceSensitiveWords 方法来替换文本中的敏感词。这个方法遍历文本中的每个字符，并使用Trie树来检查是否存在以该字符开始的敏感词，如果存在敏感词，就用指定的替换词替换该敏感词。

public String replaceSensitiveWords(String text, String replacement) {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < text.length(); i++) {
        int j = i, k = i;
        TrieNode node = root;
        while (j < text.length() && node.children.containsKey(text.charAt(j))) {
            node = node.children.get(text.charAt(j));
            if (node.isEnd) {
                k = j;
            }
            j++;
        }
        if (k != i) {
            result.append(replacement.repeat(k - i + 1));
            i = k;
        } else {
            result.append(text.charAt(i));
        }
    }
    return result.toString();
}

测试

        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println("hint apple:" + trie.search("apple"));
        System.out.println(trie.replaceSensitiveWords("apple is a fruit", "*"));
        // 会输出：***** is a fruit

这里有完整的代码: trie

性能优化

这个代码算法比较适合英文比较多的场景，如果是中文场景，会导致内存占用比较高，那么就需要进行简单的优化如果大家想了解中文的优化方案可以留言或者关注我们的公众号：入职啦我们会介绍中文敏感词过滤的优化方案

结论

敏感词替换是工作中必备的功能，如果你只会用replace方法，那么你的代码效率会非常低。作为一个合格的后端工程师，你必须会用算法来解决业务问题

有些场景不需要最先进的算法，只需要用朴素的算法就可以解决问题

通过应用算法到实际问题中，提高我们的编程能力，欢迎扫码加入我们的编程实战群，也可以关注我们的公众号（入职啦），学习更多的后端编程技巧