问题描述

实现原理

Java的实现

Trie树的实现

实现敏感词的替换

测试

性能优化

结论

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

小葵

2024-05-24

🏷

java面试题

问题描述

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

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

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

实现原理

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

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

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

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

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

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

search

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方法,那么你的代码效率会非常低。作为一个合格的后端工程师,你必须会用算法来解决业务问题

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

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

友情链接:

Copyright© 2024 杭州园中葵科技有限公司 版权所有