前缀树过滤敏感词算法

前缀树的基本性质
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

数据结构：每一个TrieNode中定义一个哈希表，含有孩子节点的，即下一个字符的TrieNode。

    private class TrieNode {

        // true 关键词的终结 ； false 继续
        private boolean end = false;

        // key下一个字符，value是对应的节点
        private Map<Character, TrieNode> subNodes = new HashMap<>();

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

        // 获取下个节点
        TrieNode getSubNode(Character key) {
            return subNodes.get(key);
        }

        boolean isKeywordEnd() {
            return end;
        }

        void setKeywordEnd(boolean end) {
            this.end = end;
        }

        public int getSubNodeCount() {
            return subNodes.size();
        }
    }

类中设置成员变量，根节点，不包含任何字符。

    private TrieNode rootNode = new TrieNode();

添加敏感词到前缀树中

注意构造树时如果根节点没有孩子节点，要初始化再添加到哈希表中。

    private void addWord(String lineTxt) {
        TrieNode tempNode = rootNode;
        // 循环每个字节
        for (int i = 0; i < lineTxt.length(); ++i) {
            Character c = lineTxt.charAt(i);
            // 过滤空格
            if (isSymbol(c)) {
                continue;
            }
            TrieNode node = tempNode.getSubNode(c);

            if (node == null) { // 没初始化
                node = new TrieNode();
                tempNode.addSubNode(c, node);
            }

            tempNode = node;

            if (i == lineTxt.length() - 1) {
                // 关键词结束， 设置结束标志
                tempNode.setKeywordEnd(true);
            }
        }
    }

过滤敏感词

设置了三个指针帮助判断。
如果字符是空格类型，并且是根节点情况，直接添加字符，移动begin，pos指针，temp不变。相当于直接跳过再接着寻找。非根节点则只用移动pos指针。因为非根节点情况相当于已经再寻找敏感词的过程中了，只需要跳过该空格继续寻找即可。
在当前节点的哈希表中寻找是否有对应字符的孩子节点，如果未找到，当前字符不是敏感词。直接添加当前字符。pos，begin指针后移一位，temp指针回到根节点。
如果找到并且不是关键字结尾，只需要pos指针移动。
如果找到并且是关键字结尾，添加关键字。pos指针后移一位，begin指向pos，temp返回根节点。
注意最后还要添加result.append(text.substring(begin));因为当最后循环不是敏感词时候，只会移动Pos而没有添加。所以最后一次遍历不能漏掉。

    public String filter(String text) {
        if (StringUtils.isBlank(text)) {
            return text;
        }
        String replacement = DEFAULT_REPLACEMENT;
        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替换掉
                result.append(replacement);
                position = position + 1;
                begin = position;
                tempNode = rootNode;
            } else {
                ++position;
            }
        }
        result.append(text.substring(begin));
        return result.toString();
    }

因为有可能存在敏感词中间夹着宫格，非法字符等形式，所以必须对这种类型进行判断。判断逻辑可以不同。

    private boolean isSymbol(char c) {
        int ic = (int) c;
        // 0x2E80-0x9FFF 东亚文字范围
        return !CharUtils.isAsciiAlphanumeric(c) && (ic < 0x2E80 || ic > 0x9FFF);
    }

具体项目中，可以将关键字保存到文件，然后读取文件构建前缀树

    @Override
    public void afterPropertiesSet() throws Exception {
        rootNode = new TrieNode();

        try {
            InputStream is = Thread.currentThread().getContextClassLoader()
                    .getResourceAsStream("SensitiveWords.txt");
            InputStreamReader read = new InputStreamReader(is);
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineTxt;
            while ((lineTxt = bufferedReader.readLine()) != null) {
                lineTxt = lineTxt.trim();
                addWord(lineTxt);
            }
            read.close();
        } catch (Exception e) {
            logger.error("读取敏感词文件失败" + e.getMessage());
        }
    }