前缀树实现敏感词过滤

  

序

  最近有需求做敏感词过滤，网上查询了相关的资料，其中看到了DFA这个名词，哟呵！这词亲切啊！好歹我也是编译原理满学分的人。虽然时间过去挺久了，很多东西都忘记了。词法分析，语法分析，语义分析…这些名词还是历历在目，遥想那年：“最后一排靠门的同学，来回答一下问题” ，“我们的考试，是在炎热的夏天” …

问题思考

  好了，打住。从某种意义上来说：判断敏感词这件事 和 词法分析这个过程 是有些类似的。此法分析的时候使用了NFA,DFA来将源row分解成能够阅读的词。而判明敏感词这件事是确定词的终结状态，终结状态很明显：是敏感词，不是敏感词。同时将 词中的字符 作为输入符号。ok，消化一下..
   解决思路：将敏感词的每个字符视为改变状态的动作，在词结束之前 任何一个字符都不能让自动机达到最终状态。
   接下来思考另一个问题，该用什么数据结构来做这件事。(其实我不假思索就决定要用前缀树来做这事….) 判断敏感词 换个角度可以看做是搜索：搜索一个词的属性。这个属性是 是否为敏感词。说道这里，前缀树来做这种事情不是很适合么？（一切都确定下来了，胜利的方程式已经写下…)

开始实践

模型创建

   首先我需要一棵前缀树，所以要想富，先种树…

/*
* 前缀树节点模型
*/
class TrieNode {
    // 当前结点是否是某一敏感词的最后一个结点
    private boolean isEnd = false;

    // 用map来存储当前结点的所有子节点
    private Map<Character, TrieNode> subNodes = new HashMap<>();

    // 向指定位置添加子结点树
    public void addSubNode(Character key, TrieNode node) {
        subNodes.put(key, node);
    }

    // 根据key获得相应的子节点
    public TrieNode getSubNode(Character key) {
        return subNodes.get(key);
    }

    // 判断是否是关键字的结尾
    public boolean isKeyWordEnd() {
        return isEnd;
    }

    // 设置为关键字的结尾
    public void setKeyWordEnd(boolean isEnd) {
        this.isEnd = isEnd;
    }
}

代码实现

   Talk is cheap, show me the code!

public class SensitiveWordUtil{

    // 默认敏感词替换符
    private static final String DEFAULT_REPLACEMENT = "*";

    public static final String FILE_PATH = "你的敏感词库文件";

    // 最大匹配
    public static final String MATCH_MAX = "max";

    // 最小匹配
    public static final String MATCH_MIN = "min";

    // 根节点
    private TrieNode rootNode = new TrieNode();

    // 缓存 为了能够方便自己直观的看到现在有哪些
    private Set<String> wordspool = new HashSet<>();


    /**
    *
    * @Description:添加节点
    * @param sensitiveWord
    * @author: chenhaoyu
    * @time:Apr 8, 2019 11:19:02 AM
    */
    public void addWord(String sensitiveWord) {
        StringBuilder sb = new StringBuilder();
        TrieNode tempNode = rootNode;
        // 循环每个字节
        for (int i = 0; i < sensitiveWord.length(); ++i) {
            Character c = sensitiveWord.charAt(i);
            // 过滤特殊字符
            if (isSymbol(c)) {
                continue;
            }
            sb.append(c);
            // 获得当前字符的节点
            TrieNode node = tempNode.getSubNode(c);

            // 不存在则初始化该节点
            if (node == null) {
                node = new TrieNode();
                tempNode.addSubNode(c, node);
            }
            tempNode = node;
            if (i == sensitiveWord.length() - 1) {
                // 关键词结束， 设置结束标志
                tempNode.setKeyWordEnd(true);
            }
        }
        //将词写入缓存
        wordspool.add(sb.toString());
    }

    /**
    *
    * @Description:解禁某词
    * @param word
    * @author: chenhaoyu
    * @time:Apr 8, 2019 11:22:57 AM
    */
    public void removeWord(String word) {
        StringBuilder sb = new StringBuilder();
        TrieNode tempNode = rootNode;
        for (int i = 0; i < word.length(); ++i) {
            Character c = word.charAt(i);
            if (isSymbol(c)) {
                continue;
            }
            sb.append(c);
            TrieNode node = tempNode.getSubNode(c);
            // 不存在则继续循环
            if (node == null) {
                continue;
            }
            tempNode = node;
            if (i == word.length() - 1) {
                // 释放结束标志
                tempNode.setKeyWordEnd(false);
            }
        }
        wordspool.remove(sb.toString());
    }

    /**
    * @Description:判断是否是一个符号 这个方法是个神来之笔。可以和谐掉 中间夹着乱码的敏感词，但是还有有些缺陷
    * @param c
    * @return
    * @author: 在哪看的忘记了
    * @time:Apr 8, 2019 11:19:23 AM
    */
    private boolean isSymbol(char c) {
        int ic = (int) c;
        // 0x2E80-0x9FFF 东亚文字范围
        return !((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
        && (ic < 0x2E80 || ic > 0x9FFF);
    }

    /**
    *
    * @Description:过滤敏感词
    * @param text 原文本
    * @param type 过滤模式 MATCH_MAX / MATCH_MIN
    * @return
    * @author: chenhaoyu
    * @time:Apr 8, 2019 11:19:37 AM
    */
    public String filter(String text, String type) {
        if (text.trim().length() == 0) {
            return text;
        }
        StringBuilder result = new StringBuilder();

        TrieNode tempNode = rootNode;
        int begin = 0; // 回滚数
        int position = 0; // 当前比较的位置

        while (position < text.length()) {
            char c = text.charAt(position);
            // 特殊字符跳过
            if (isSymbol(c)) {
                if (tempNode == rootNode) {
                    result.append(c);
                    ++begin;
                }
                ++position;
                continue;
            }

            tempNode = tempNode.getSubNode(c);
            // 当前位置的匹配结束
            if (tempNode == null) {
                // 以begin开始的字符串不存在敏感词
                result.append(text.charAt(begin));
                // 跳到下一个字符开始测试
                position = begin + 1;
                begin = position;
                // 回到树初始节点
                tempNode = rootNode;
            } else if (tempNode.isKeyWordEnd()) {
                // 发现敏感词， 从begin到position的位置用replacement替换掉
                position = position + 1;
                result.append(getStar(position - begin));
                begin = position;
                // 如果是最小匹配，直接将dfa下一个输入置为根节点，从头开始检测
                if (type.equals(MATCH_MIN)) {
                    tempNode = rootNode;
                } else {
                    // 当最大匹配时，如果已经Str已经到头，或者树已经没有下一个子节点，那么重置dfa下一个输入
                    if (position >= text.length()) {
                        tempNode = rootNode;
                    } else {
                        TrieNode nextNode = tempNode.getSubNode(text.charAt(position));
                        if (nextNode == null) {
                            tempNode = rootNode;
                        }
                    }
                }
            } else {
                ++position;
            }
        }
        result.append(text.substring(begin));
        return result.toString();
    }

    /**
     * 
     * @Description:获得指定数量的替换符号
     * @param num
     * @return
     * @author: magic chen
     * @time:Apr 7, 2021 6:22:28 PM
     */
    private static String getStar(int num) {
        StringBuilder star = new StringBuilder();
        for (int i = 0; i < num; i++) {
            star.append(DEFAULT_REPLACEMENT);
        }
        return star.toString();
    }

    /**
    *
    * @Description:获得当前的所有敏感词
    * @return
    * @author: chenhaoyu
    * @time:Apr 8, 2019 2:48:53 PM
    */
    public Set<String> sensitiveWords() {
        return wordspool;
    }

    /**
    *
    * @Description:根据文件 构造前缀树
    * @author: chenhaoyu
    * @time:Apr 8, 2019 11:20:42 AM
    */
    public void addWordsFromFile(String filepath) {
        File file = new File(filepath);
        if (file.exists() && file.isFile()) {
                try (FileReader reader = new FileReader(file); BufferedReader br = new BufferedReader(reader);) {
                String str;
                while ((str = br.readLine()) != null) {
                    addWord(str);
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }


}

大功告成？

   到这里，其实我已经发现了一个问题了….很多理论上的东西我已经不记得了，本来还想着画个DFA的状态图，结果发现…画出了NFA的图之后就进行不下去了，百度回忆了一下。嗯…子集构造法，最小DFA，抹去死状态….告辞！

结语

  整片文就没几个汉字，是我懒了还是不会说话了。我觉得应该是这篇文选题的问题，理论上的东西已经忘记了，只记得个大约摸的操作方法，好在代码还是会写的。我在想啥时候重新开始更新设计模式这个大坑呢？毕竟那边话多…
  最后还是要感谢沈老师，要不是那几句魔咒一般的口头禅，我不可能会记住这些东西…还有借我抄笔记的学霸…
   Lastvt 拜拜~