前缀树过滤敏感词算法

港控/mmm° 2021-10-01 11:24 379阅读 0赞

前缀树的基本性质  
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());
            }
        }