博客增加敏感词过滤功能

背景

昨天看知乎看到有举报不良内容的入口，想到应该可以给博客增加内容过滤。想了下似乎也不难实现，用Trie树就可以，那么说干就干

前置知识

对字典树有了解。这里就不讲了，网上很多学习资料，如

关于中文字符敏感词需额外的处理。这里顺带提一下，Java内使用的中文字符串编码为UTF-16；至于IDE和浏览器显示，一般也是UTF-8，UTF-16,GBK这些。而这些编码方式，都是Unicode的一种实现。想了解Unicode和UTF-8这些编码的关系，可以阅读 ref

实现思路

初始化生成敏感词集Trie树
扫描一遍源串，如果遇到当前字属于敏感词前缀，记录位置P1
P2从P1开始，往后扫描，求得最长敏感词前缀串，记为S[P1,P2]
校验S[P1,P2]是否是一个敏感词。（是敏感词前缀不一定是敏感词，敏感词一定是敏感词前缀）。如果是，替换敏感内容为'*'，P1指向P2+1;如果不是，P1继续后溯

时间复杂度：记源串长度M，构建的Trie树高度为lgN, 总时间复杂度是 O(MlgN)
空间复杂度：构建敏感词集的字典树开销

Trietree

关键部分代码

package com.jquan.blog.joey.util;

import org.junit.Test;

import java.util.HashMap;

public class WorldFilterUtil {
    public static String[] sensWord = new String[]{"xxxx"};//敏感词集，不方便放上来了；后面有时间再添加到后台admin管理
    public static Trie sensTree;
    public static boolean isInitial; //只需要初始化一次


    /**
     * trie树包含一段前缀，这段前缀不一定是敏感词
     * 但是一段字符串是敏感词，肯定是trie树包含的前缀
     * @param originalStr 源字符串
     */
    public static String filter(String originalStr) {
        if(originalStr == null || originalStr.length()==0) return  originalStr;

        char[] originalStrCrr = originalStr.toCharArray();
        boolean find = false;

        if (!isInitial) {
            trieInitial();
            isInitial = true;
        }

        for (int i = 0; i < originalStr.length(); i++) {
            String startWorld = originalStr.substring(i, i + 1);
            if (!sensTree.startsWithPrefix(startWorld)) continue;

            //存在以该字开头的前缀
            int j = i + 1;
           
            while (j <= originalStr.length() && sensTree.startsWithPrefix(originalStr.substring(i, j)))
                j++; //是前缀往后移动j指针

            if (sensTree.search(originalStr.substring(i, j - 1))) { //找到敏感词
                find = true;
                for (int m = i; m < j - 1; m++) {
                    originalStrCrr[m] = '*';
                }
            }

        }
        if (find) return String.valueOf(originalStrCrr);
        return originalStr;

    }

    public static void trieInitial() {
        //初始化得到一个敏感词前缀树
        sensTree = new Trie();
        for (String e : sensWord) {
            sensTree.addWord(e);
        }
        return;
    }
    
}

class Trie {
    HashMap<Character, Trie> subs;
    boolean isEnd;
    int preFixCou;
    int cou;

    public Trie() {
        subs = new HashMap<>();
    }

      /**
     * 添加敏感词
     * @param word 敏感词
     * */
    public void addWord(String word) {
        if (word == null || word.length() == 0) return;
        
        Trie curNode = this;
        for (int i = 0; i < word.length(); i++) {
            if (curNode.subs.containsKey(word.charAt(i))) {
                curNode = curNode.subs.get(word.charAt(i));
                curNode.preFixCou++;
                continue;
            }
            Trie newNode = new Trie();
            curNode.subs.put(word.charAt(i), newNode);
            curNode = newNode;
            curNode.preFixCou++;
        }
        curNode.isEnd = true;
        curNode.cou++;
    }

     /**
     *含有前缀
     * @param word 前缀串
     * */
    public boolean startsWithPrefix(String word) {
        Trie curNode = this;
        for (int i = 0; i < word.length(); i++) {
            if (curNode.subs.containsKey(word.charAt(i))) {
                curNode = curNode.subs.get(word.charAt(i));
                continue;
            }
            return false;
        }
        if (curNode.preFixCou > 0) return true;
        return false;
    }

     /**
     *含有含有该敏感词
     * @param word 敏感词串
     * */
    public boolean search(String word) {
        Trie curNode = this;
        for (int i = 0; i < word.length(); i++) {
            if (curNode.subs.containsKey(word.charAt(i))) {
                curNode = curNode.subs.get(word.charAt(i));
                continue;
            }
            return false;
        }
        if (curNode.isEnd) return true;
        return false;
    }
}

测试结果

测试留言墙

测试博客评论区