Java使用DFA实现敏感词过滤

目录

1 Java敏感词过滤

敏感词、文字过滤是一个网站必不可少的功能,如何设计一个好的、高效的过滤算法是非常有必要的。

1.1 DFA简介

在实现文字过滤的算法中,DFA是唯一比较好的实现算法。DFADeterministic Finite Automaton,也就是确定有穷自动机,它是是通过event和当前的state得到下一个state,即event+state=nextstate。下图展示了其状态的转换
Java使用DFA实现敏感词过滤
在这幅图中大写字母(S、U、V、Q)都是状态,小写字母a、b为动作。通过上图我们可以看到如下关系
Java使用DFA实现敏感词过滤
在实现敏感词过滤的算法中,我们必须要减少运算,而DFADFA算法中几乎没有什么计算,有的只是状态的转换。

1.2 Java实现DFA算法实现敏感词过滤

Java中实现敏感词过滤的关键就是DFA算法的实现。首先我们对上图进行剖析。在这过程中我们认为下面这种结构会更加清晰明了。
Java使用DFA实现敏感词过滤
同时这里没有状态转换,没有动作,有的只是Query(查找)。我们可以认为,通过S query U、V,通过U query V、P,通过V query U P。通过这样的转变我们可以将状态的转换转变为使用Java集合的查找。
诚然,加入在我们的敏感词库中存在如下几个敏感词:乌龙茶,乌龙白茶。那么需要构建成一个什么样的结构呢?
首先:query 乌 —> {龙}query 龙 —>{茶、白茶}query 茶 —>{null}query 白 —> {茶}

这样我们就将我们的敏感词库构建成了一个类似与一颗一颗的树,这样我们判断一个词是否为敏感词时就大大减少了检索的匹配范围。比如我们要判断乌龙茶,根据第一个字我们就可以确认需要检索的是那棵树,然后再在这棵树中进行检索。

1.3 具体代码实现

1.3.1 设置检索库

但是如何来判断一个敏感词已经结束了呢?利用标识位来判断。
所以对于这个关键是如何来构建一棵棵这样的敏感词树。下面Java中的HashMap为例来实现DFA算法。具体过程如下:
乌龙茶,乌龙白茶

  1. hashMap中查询看其是否在hashMap中存在,如果不存在,则证明已开头的敏感词还不存在,则我们直接构建这样的一棵树。
    跳至3。
  2. 如果在hashMap中查找到了,表明存在以开头的敏感词,设置hashMap = hashMap.get(“乌”),跳至1,依次匹配
  3. 判断该字是否为该词中的最后一个字。若是表示敏感词结束,设置标志位isEnd = 1,否则设置标志位isEnd = 0

程序实现如下:

/**
     * 读取敏感词库,将敏感词放入HashSet中,构建一个DFA算法模型:<br>
     * 乌 = {
     *      isEnd = 0
     *      龙 = {<br>
     *           isEnd = 1
     *           茶 = {isEnd = 0
     *                叶= {isEnd = 1}
     *                }
     *           白  = {
     *                  isEnd = 0
     *                   茶 = {
     *                        isEnd = 1
     *                       }
     *               }
     *           }
     *      }
     *  桌 = {
     *      isEnd = 0
     *      子 = {
     *          isEnd = 0
     *          板 = {
     *              isEnd = 0
     *              凳 = {
     *                   isEnd = 1
     *                  }
     *              }
     *          }
     *      }
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    private void addSensitiveWordToHashMap(Set<String> keyWordSet) {
        sensitiveWordMap = new HashMap(keyWordSet.size());     //初始化敏感词容器,减少扩容操作
        String key = null;  
        Map nowMap = null;
        Map<String, String> newWorMap = null;
        //迭代keyWordSet
        Iterator<String> iterator = keyWordSet.iterator();
        while(iterator.hasNext()){
            key = iterator.next();    //关键字
            nowMap = sensitiveWordMap;
            for(int i = 0 ; i < key.length() ; i++){
                char keyChar = key.charAt(i);       //转换成char型
                Object wordMap = nowMap.get(keyChar);       //获取
                
                if(wordMap != null){        //如果存在该key,直接赋值
                    nowMap = (Map) wordMap;
                }
                else{     //不存在则,则构建一个map,同时将isEnd设置为0,因为他不是最后一个
                    newWorMap = new HashMap<String,String>();
                    newWorMap.put("isEnd", "0");     //不是最后一个                    nowMap.put(keyChar, newWorMap);
                    nowMap = newWorMap;
                }
                
                if(i == key.length() - 1){
                    nowMap.put("isEnd", "1");    //最后一个                }
            }
        }
    }

运行得到的hashMap结构如下:
{桌={子={板={isEnd=0, 凳={isEnd=1}}, isEnd=0}, isEnd=0}, 乌={isEnd=0, 龙={isEnd=0, 茶={isEnd=1}, 白={isEnd=0, 茶={isEnd=1}}}}}

1.3.2 查询检索库

敏感词库我们一个简单的方法给实现了,那么如何实现检索呢?检索过程无非就是hashMapget实现,找到就证明该词为敏感词,否则不为敏感词。过程如下:假如我们匹配桌子板凳

  1. 第一个字,我们在hashMap中可以找到。得到一个新的map = hashMap.get(“”)
  2. 如果map == null,则不是敏感词。否则跳至3
  3. 获取map中的isEnd,通过isEnd是否等于1来判断该词是否为最后一个。如果isEnd == 1表示该词为敏感词,否则跳至1。

通过这个步骤我们可以判断桌子板凳为敏感词,但是如果我们输入桌子椅子则不是敏感词了。

/**
     * 检查文字中是否包含敏感字符
     */
    @SuppressWarnings({ "rawtypes"})
    public int CheckSensitiveWord(String txt,int beginIndex,int matchType){
        boolean  flag = false;    //敏感词结束标识位:用于敏感词只有1位的情况
        int matchFlag = 0;     //匹配标识数默认为0
        char word = 0;
        Map nowMap = sensitiveWordMap;
        for(int i = beginIndex; i < txt.length() ; i++){
            word = txt.charAt(i);
            nowMap = (Map) nowMap.get(word);     //获取指定key
            if(nowMap != null){     //存在,则判断是否为最后一个
                matchFlag++;     //找到相应key,匹配标识+1 
                if("1".equals(nowMap.get("isEnd"))){       //如果为最后一个匹配规则,结束循环,返回匹配标识数
                    flag = true;       //结束标志位为true   
                    if(SensitivewordFilter.minMatchTYpe == matchType){    //最小规则,直接返回,最大规则还需继续查找
                        break;
                    }
                }
            }
            else{     //不存在,直接返回
                break;
            }
        }
        if(matchFlag < 2 && !flag){     
            matchFlag = 0;
        }
        return matchFlag;
    }

在文章末尾我提供了利用Java实现敏感词过滤的文件下载。下面是一个测试类来证明这个算法的效率和可靠性

1.3.3 测试检索库

public static void main(String[] args) {
        SensitivewordFilter filter = new SensitivewordFilter();
        System.out.println("敏感词的数量:" + filter.sensitiveWordMap.size());
        String string = "两只黄鹂鸣翠柳,一行白鹭上青天。窗含西岭千秋雪,门泊东吴万里船";
        System.out.println("待检测语句字数:" + string.length());
        long beginTime = System.currentTimeMillis();
        Set<String> set = filter.getSensitiveWord(string, 1);
        long endTime = System.currentTimeMillis();
        System.out.println("语句中包含敏感词的个数为:" + set.size() + "。包含:" + set);
        System.out.println("总共消耗时间为:" + (endTime - beginTime));
    }
上一篇:乒乓球比赛预测


下一篇:Python实现点与点、点与线的批量近邻匹配(TransBigData)