JAVA使用前缀树(Tire树)实现敏感词过滤、词典搜索

JAVA前缀树敏感词过滤 JAVA前缀树 2023-01-03 12:01:10 839人浏览独家记忆

Python 官方文档：入门教程 => 点击学习

摘要

目录简介Trie树code结论简介有时候需要对用户输入的内容进行敏感词过滤，或者实现查找文本中出现的词典中的词，用遍历的方式进行替换或者查找效率非常低，这里提供一个基于Trie树的

简介

有时候需要对用户输入的内容进行敏感词过滤，或者实现查找文本中出现的词典中的词，用遍历的方式进行替换或者查找效率非常低，这里提供一个基于Trie树的方式，进行关键词的查找与过滤，在词典比较大的情况下效率非常高。

Trie树

Trie树，又叫前缀树，多说无益，直接看图就明白了

词典：[“猪狗”, “小狗”, “小猫”, “小猪”, “垃圾”, “狗东西”]

Tire数据结构：

在这里插入图片描述

code

树节点node.class


public class Node {
    
    private Map<Character, Node> nextNodes = new HashMap<>();

    public void addNext(Character key, Node node){
        nextNodes.put(key, node);
    }

    public Node getNext(Character key){
        return nextNodes.get(key);
    }

    public boolean isLastCharacter(){
        return nextNodes.isEmpty();
    }
}

搜索类TrieSearcher.class


public class TrieSearcher {

    private Node root = new Node();

    
    public void addWord(String Word) {
        Node tmpNode = root;
        for (char c : word.toCharArray()) {
            Node node = tmpNode.getNext(c);
            if (null == node) {
                node = new Node();
                tmpNode.addNext(c, node);
            }
            tmpNode = node;
        }
    }

    
    public String replace(String text, String afterReplace) {
        StringBuilder result = new StringBuilder(text.length());
        Node tmpNode = root;
        int begin = 0, pos = 0;
        while (pos < text.length()) {
            char c = text.charAt(pos);
            tmpNode = tmpNode.getNext(c);
            if (null == tmpNode) {
                result.append(text.charAt(begin));
                begin++;
                pos = begin;
                tmpNode = root;
            } else if (tmpNode.isLastCharacter()) {
                // 匹配完成, 进行替换
                result.append(afterReplace);
                pos++;
                begin = pos;
                tmpNode = root;
            } else {
                // 匹配上向后移
                pos++;
            }
        }
        result.append(text.substring(begin));
        return result.toString();
    }

    
    public Map<String, Integer> find(String text) {
        Map<String, Integer> resultMap = new HashMap<>(16);
        Node tmpNode = root;
        StringBuilder word = new StringBuilder();
        int begin = 0, pos = 0;
        while (pos < text.length()) {
            char c = text.charAt(pos);
            tmpNode = tmpNode.getNext(c);
            if (null == tmpNode) {
                begin++;
                pos = begin;
                tmpNode = root;
            } else if (tmpNode.isLastCharacter()) {
                // 匹配完成
                String w = word.append(c).toString();
                resultMap.put(w, resultMap.getOrDefault(w, 0) + 1);
                pos++;
                begin = pos;
                tmpNode = root;
                word = new StringBuilder();
            } else {
                // 匹配上向后移
                word.append(c);
                pos++;
            }
        }
        return resultMap;
    }
}

测试Main.class

public class Main {
    public static void main(String[] args) {
        TrieSearcher trieSearcher = new TrieSearcher();
        Stream.of("猪狗", "小狗", "小猫", "小猪", "垃圾", "狗东西").forEach(trieSearcher::addWord);
        String sentence = "你好，小狗，小猪，今天天气真好。";
        System.out.println(trieSearcher.replace(sentence, "***"));
        System.out.println(trieSearcher.find(sentence));
    }
}

输出：