Java使用Trie树算法实现敏感词替过滤、根据关键词自动联想功能

前言:

Trie树也称为字典树、单词查找树,最大的特点就是共享字符串的公共前缀来达到节省空间的目的了。
然后可以根据它的公共前缀的特性来实现敏感词过滤、自动联想等功能。

抽象出trie树的数据结构:

1、首先来看下trie树的结构图:
Java使用Trie树算法实现敏感词替过滤、根据关键词自动联想功能_第1张图片

2、从上图可以归纳出Trie树的基本性质:
①根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
②从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
③每个节点的所有子节点包含的字符互不相同。
④从第一字符开始有连续重复的字符只占用一个节点,比如上面的to,和ten,中重复的单词t只占用了一个节点

3、从上面归纳出的基本性质可以抽象出节点的class属性:
①是否为叶子节点的标志位 isWord ;
②既能存储此节点的值也能存储其所有的子节点的 children 数据结构HashMap;

4、节点 (Node )的class类代码:

        /**
     * @Title: Node
     * @Description: trie树的节点
     */
    private class Node {
        // 节点是否为叶子节点的标志;true:叶子节点,false:非叶子节点(拥有子节点的节点)
        public boolean isWord;
        // 当前节点拥有的孩子节点,使用hashmap进行存储,在查找子节点时的时间复杂度为O(1)
        public HashMap children;
 
        public Node(boolean isWord) {
            this.isWord = isWord;
            this.children = new HashMap<>();
        }
 
        public Node() {
            this(false);
        }
    }

代码奉上:

package com.lyl.trie;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
 
 
 
public class Trie {
 
    /**
     * @Title: Node
     * @Description: trie树的节点
     */
    private class Node {
        // 节点是否为叶子节点的标志;true:叶子节点,false:非叶子节点(用于子节点的节点)
        public boolean isWord;
        // 当前节点拥有的孩子节点,使用hashmap进行存储,在查找子节点时的时间复杂度为O(1)
        public HashMap children;
 
        public Node(boolean isWord) {
            this.isWord = isWord;
            this.children = new HashMap<>();
        }
 
        public Node() {
            this(false);
        }
    }
 
    // trie树的根节点
    private Node root;
    // trie树中拥有多少分枝(多少个敏感词)
    private int size;
 
    public Trie() {
        this.root = new Node();
        this.size = 0;
    }
 
    /**
     * @Description: 返回trie树中分枝树(敏感词树)
     */
    public int getSize() {
        return size;
    }
 
    /**
     * @Description: 向trie树中添加分枝/敏感词
     * @param word
     *            添加的敏感词
     */
    public void addBranchesInTrie(String word) {
        // 设置当前节点为根节点
        Node cur = root;
        char[] words = word.toCharArray();
 
        for (char c : words) {
            // 判断当前节点的子节点中是否存在字符c
            if (!cur.children.containsKey(c)) {
                // 如果不存在则将其添加进行子节点中
                cur.children.put(c, new Node());
            }
            // 当前节点进行变换,变换为新插入到节点 c
            cur = cur.children.get(c);
        }
        // 分枝添加完成后,将分枝中的最后一个节点设置为叶子节点
        if (!cur.isWord) {
            cur.isWord = true;
            // 分枝数(敏感词数)加1
            size++;
        }
    }
 
    /**
     * @Description: 判断trie树中是否存在某分枝/敏感词
     * @param word
     * @return
     */
    public boolean contains(String word) {
        Node cur = root;
        char[] words = word.toCharArray();
 
        for (char c : words) {
            if (!cur.children.containsKey(c)) {
                return false;
            }
            cur = cur.children.get(c);
        }
        // 如果存在并且遍历到trie树中某个分支最后一个节点了,那此节点就是叶子节点,直接返回true
        return cur.isWord;
    }
 
    /**
     * @Description: 如果一段话中有trie树中存储的敏感词则需将其进行替换为 **; 例如:尼玛的,替换为 **的
     * @param word
     *            一段话,如果有敏感词需要被替换的词
     * @return
     */
    public String sensitiveWordReplace(String word) {
        System.out.println("敏感词替换前:" + word);
 
        Node cur = root;
        char[] words = word.toCharArray();
        // 需要被替换的敏感词
        StringBuilder oldTemp = new StringBuilder();
        // 需要替换成的星号
        StringBuilder starTemp = new StringBuilder();
 
        for (char c : words) {
            if (!cur.children.containsKey(c)) {
            // 如果当前字符不是空格、换行符、tab键的话  
                if (Character.isWhitespace(c)  && oldTemp.length() > 0 ) {  
                    // 重新从根节点遍历 敏感树  
                 oldTemp.append(c);  
                    starTemp.append("*");  
                }
                // 如果当前节点的孩子节点中没有此单词则直接跳过此循环,进入下次循环
                continue;
            }
            if (!cur.isWord) {
                // 拼接上word和trie树都有的字符
                oldTemp.append(c);
                starTemp.append("*");
                cur = cur.children.get(c);
            }
            if (cur.isWord) {
                // 进行敏感词替换
                word = word.replaceAll(oldTemp.toString(), starTemp.toString());
                // 清空StringBuilder中内容
                oldTemp.delete(0, oldTemp.length());
                starTemp.delete(0, starTemp.length());
                // 查找一个敏感词并替换后,需要重新从根节点进行遍历,所以当前节点指向root
                cur = root;
            }
        }
        System.out.println("敏感词替换后:" + word);
        return word;
    }
 
    // 存放trie树中查询到的联想词
    private List list = new ArrayList();
 
    /**
     * @Description: 利用trie的公共前缀特性,可以实现关键词自动联想
     * @param word
     */
    public void prefixMatching(String word, Node root) {
        Node cur = root;
        char[] words = word.toCharArray();
        StringBuilder str = new StringBuilder();
        str.append(word);
 
        for (int i = 0; i < words.length; i++) {
            if (!cur.children.containsKey(words[i])) {
                System.out.println("无关联词!");
                return;
            }
            cur = cur.children.get(words[i]);
        }
        dfs(str, cur);
        System.out.println("[ " + word + " ]在trie树中的联想词:" + Arrays.toString(list.toArray()));
    }
 
    /**
     * @Description: 节点遍历
     * @param word
     *            需要查找的词
     * @param root
     *            开始遍历的根节点
     */
    public void dfs(StringBuilder word, Node root) {
        Node cur = root;
        if (cur.isWord) {
            list.add(word.toString());
            if (cur.children.size() == 0) {
                return;
            }
        }
        for (Character s : cur.children.keySet()) {
            word.append(s);
            // 递归调用
            dfs(word, cur.children.get(s));
            word.delete(word.length() - 1, word.length());
        }
    }
 
    // test
    public static void main(String[] args) {
        Trie t = new Trie();
        // 插入敏感词
        t.addBranchesInTrie("麻痹");
        t.addBranchesInTrie("尼玛的");
        t.addBranchesInTrie("狗日的");
 
        // 插入联想词
        t.addBranchesInTrie("联想云科技");
        t.addBranchesInTrie("联盟");
        t.addBranchesInTrie("联和利泰扩招了");
 
        System.out.println("trie树中分枝的个数:" + t.size);
 
        String word = "尼玛的";
        System.out.println("Trie树中是否存在[ " + word + " ]敏感词: " + t.contains(word));
        // 敏感词替换测试
        t.sensitiveWordReplace("衮,尼 玛 的 傻子,你麻痹的,你各狗日的,早晚揍死你。");
 
        // trie树实现联想测试
        t.prefixMatching("联", t.root);
    }
 
}

代码运行输出:

trie树中分枝的个数:6
Trie树中是否存在[ 尼玛的 ]敏感词: true
敏感词替换前:衮,尼玛的傻子,你麻痹的,你各狗日的,早晚揍死你。
敏感词替换后:衮,***傻子,你**的,你各***,早晚揍死你。
[ 联 ]在trie树中的联想词:[联想云科技, 联和利泰扩招了, 联盟]

❤不要忘记留下你学习的足迹 [点赞 + 收藏 + 评论]嘿嘿ヾ

一切看文章不点赞都是“耍流氓”,嘿嘿ヾ(◍°∇°◍)ノ゙!开个玩笑,动一动你的小手,点赞就完事了,你每个人出一份力量(点赞 + 评论)就会让更多的学习者加入进来!非常感谢! ̄ω ̄=

参考资料:

1、【图解算法面试】记一次面试:说说游戏中的敏感词过滤是如何实现的?

2、前缀树(Trie)原理及Java实现

3、Trie树(字典树/前缀树)Java实现

4、Trie 树实现搜索引擎自动联想

你可能感兴趣的