博客

前缀树

• 名称:Trie、字典树、查找树

• 特点:查找效率高，消耗内存大

• 应用:字符串检索、词频统计、字符串排序等

敏感词过滤器

• 定义前缀树

• 根据敏感词，初始化前缀树

• 编写过敏敏感词的方法

前缀树的特点

• 根节点不包含任何字符
• 除了根节点以外的都只包含了一个字符
• 需要在叶节点之后加一个标记

前缀树匹配算法:


三个指针 第一个指向树:二个指针，分别指向单词的第一个和最后一个

检测结果存储在StringBuilder之中

如何协调呢?指针2永远都是往后走，但是指针3有个不断来回摆动的过程。

StringBuilder = xwa******ff 如果为敏感词的话直接跳过替换成*

代码实现

//前缀树(内部类) 做好标记 维护好上下级的关系

    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);
        }
    }

初始化构造树方法

    private TrieNode rootNode = new TrieNode();
    @PostConstruct
    //表示的是在容器调用这个Bean的构造方法之后init()方法会自动被调用
    //Bean在服务器自动的时候会被自动调用
    public void init(){
        try(
            //从类加载器中去加载内容，也就是从classes目录中去加载，文件也会被加载
            InputStream is = this.getClass().getClassLoader().getResourceAsStream("sensitive-words");
            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);
            }
        }
    }

//判断是否为符号

//判断是否为符号
    private boolean isSymbol(Character c){
        //0x2E80-0x9FFF是东亚文字范围
        return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF);
}

//过滤敏感词,因为需要被外界经常调用，所以是一个公用的方法
    //输入的是原文，输出的是替换后的字符串 利用的是我们前面讲的算法
    public String filter(String text){
        if(StringUtils.isBlank(text)){
            return null;
        }
        //根指针
        TrieNode tempNode = rootNode;
        //指针2
        int begin = 0;
        //指针3
        int position = 0;
        //结果
        StringBuilder sb = new StringBuilder();
        //以指针三作为循环终止条件，效率会高一些
        while(position < text.length()){
            char c = text.charAt(position);
            //过滤符号
            if(isSymbol(c)){
                //当特殊符号出现在第一个字符的时候，begin和position都需要++
                //否则只需要position++即可
                if(tempNode == rootNode){
                    sb.append(c);
                    begin ++;
                }
                //无论符号在开头还是中间，指针3都向下走一步
                position ++;
                continue;
            }
            //检查下一个节点
            tempNode = tempNode.getSubNode(c);
            //以begin开头的字符串不可能为敏感词，将begin位置处的字符加入到sb中
            if(tempNode == null){
                sb.append(text.charAt(begin));
                //进入下一个位置，position和begin保持一致
                position = ++begin;
                //tempNode重新指向rootNode
                tempNode = rootNode;
            }
            //是敏感词汇，需要替换begin-position之间的所有字符
            else if(tempNode.isKeywordEnd == true){
                sb.append(REPLACEMENT);
                begin = ++position; //posotion进入下一个位置
                tempNode = rootNode;
            }
            //还无法做出判断，position往后继续检查下一个字符
            else{
                position ++;
            }
        }
        // 将最后一批字符计入结果
        sb.append(text.substring(begin));
        return sb.toString();
    }