敏感词过滤算法：前缀树算法

大家好，又见面了，我是你们的朋友全栈君。

背景

平时我们在逛贴吧、牛客网的时候，我们经常可以看到一些形如 “***”的符号，通过上下文，我们也可以很容易猜到这些词原来是骂人的话，只是被系统和谐了。那么这是如何实现的呢？作为普通人，我们最先想到的一种办法就是把所有敏感串存入一个列表中，然后用户每发一条内容后台就把该内容与敏感串列表的每一项进行匹配，然后把匹配的字符进行和谐。显然这样的效率是很低的。非常影响性能，那么我们有没有其他的算法呢？这就是我这篇博文打算介绍的。

原理讲解

1.首先建立个敏感词前缀树

根节点为空

2.准备好待处理字符串： 哈哈大王八子大猪蹄子哦 ，声明三个指针，分别指向前缀树的根节点以及待处理字符串的开始字符

3.position指向的字符与根节点的所有子节点进行匹配，不匹配，position 和 begin分别指向待处理字符串的下一个字符，tempNode依旧指向 根节点

4.依旧不匹配，position 和begin继续向前走一位，指向“大”，treeNode依旧指向根节点

5.此时 根节点有一个子节点 与 position指向的字符相等，都为‘大’，则tempNode 指向该节点，同时position前进一步，指向‘王’

6.此时把position指向的‘王’ 和 tempNode的所有子节点进行匹配，匹配失败，说明 从begin起头所有串是不存在敏感词的，可以直接输出。此时begin前进一位，position回退到begin的位置，tempNode回退到根节点

7.此时再把position指向的‘王’与tempNode的所有子节点进行匹配，匹配成功，所以tempNode指向该节点，同时position前进一位，指向’八‘

8.此时再把position指向的‘王’ 与tempNode的所有子节点进行匹配，匹配成功，此时tempNode 指向它的子节点‘八’，同时position前进一位。

9.继续把position指向的字符与tempNode的所有子节点进行匹配，匹配失败。说明以begin起头的不存在非法字符，可以加入到结果集中。 此时begin向前走一位，position回退到begin的位置，同时tempNode回退到根节点。

10.同理，可以发现子’子’不匹配，则直接把它加入结果集，同时position 和begin 向前走一位，tempNode指向根节点。

此时position指向 ‘大’，与tempNode的所有 子节点进行匹配，匹配成功，则position和tempNode都走一位，循环执行….

直到position指向‘子’，tempNode指向‘蹄’

 11.此时把position与tempNode的所有子节点进行匹配，匹配成功，tempNode指向它的子节点‘子’，此时检查发现tempNode是敏感词树的叶子节点，说明从begin+1开始的位置 到 position这段是敏感词，用和谐词替换掉。替换之后position前进一位，begin跳到position的位置，tempNode回退到根节点

以上，就是全部流程啦，理解了之后看代码就简单多啦

代码讲解

1.前缀树节点结构

private class TreeNode{

        //是否最后一个字
        private boolean isKeyWordsEnd = false;

        //子节点
        private Map<Character,TreeNode> subNodes = new HashMap<>();

        public void addSubNode(Character key, TreeNode node){
            subNodes.put(key,node);
        }

        public TreeNode getSubNode(Character key){
            return subNodes.get(key);
        }

        public boolean isKeyWordsEnd(){
            return isKeyWordsEnd;
        }

        public void setKeyWordsEnd(Boolean end){
            isKeyWordsEnd = end;
        }
    }

2.构建前缀树的方法

public void addSensitiveWord(String words){

        TreeNode tempNode = rootNode;

        for(int i = 0;  i < words.length(); i++){

            Character c = words.charAt(i);
            if(!isSymbol(c)){
                continue;
            }

            TreeNode node = tempNode.getSubNode(c);
            if (node == null){
                node = new TreeNode();
                tempNode.addSubNode(c,node);
            }
            // 指针移动
            tempNode = node;

            //如果到了最后一个字符
            if(i == words.length() -1){
                tempNode.setKeyWordsEnd(true);
            }

        }

    }

3.算法具体实现

public String filter(String text){

        if (StringUtils.isEmpty(text)){
            return text;
        }

        String sensitiveWords = "***";
        StringBuilder result = new StringBuilder();

        TreeNode tempNode = rootNode;
        int begin = 0;
        int position = 0;

        while (position < text.length()){

            Character 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));
                begin++;
                position = begin;
                tempNode = rootNode;
                continue;
            }else if(tempNode.isKeyWordsEnd()){
                //替换敏感词
                result.append(sensitiveWords);

                position++;
                begin = position;
                tempNode = rootNode;
            }else {
                position++;
            }

        }
        result.append(text.substring(begin)); //把剩下的动加入合法集

        return result.toString();
    }

小结

最近一直在做项目，所以有一段时间没写文章了，项目也快完成了，就把在项目中使用的一个算法做了下总结，希望能给读者一些帮助。