手把手教你java快速过滤关键词

墨蓝 2021-09-03 09:36 515阅读 0赞

## java过滤关键词 ##

> 敏感词、文字过滤是一个网站必不可少的功能，如何设计一个好的、高效的过滤算法是非常有必要的。前段时间我一个朋友（马上毕业，接触编程不久）要我帮他看一个文字过滤的东西，它说检索效率非常慢。我把它程序拿过来一看，整个过程如下：读取敏感词库、如果HashSet集合中，获取页面上传文字，然后进行匹配。我就想这个过程肯定是非常慢的。对于他这个没有接触的人来说我想也只能想到这个，更高级点就是正则表达式。但是非常遗憾，这两种方法都是不可行的。当然，在我意识里没有我也没有认知到那个算法可以解决问题，但是Google知道！

https://blog.csdn.net/shayukaifa/article/details/110940596

## DFA简介 ##

在实现文字过滤的算法中，DFA是唯一比较好的实现算法。DFA即Deterministic Finite Automaton，也就是确定有穷自动机，它是是通过event和当前的state得到下一个state，即event+state=nextstate。下图展示了其状态的转换

![在这里插入图片描述][20201209205325313.png]  
在这幅图中大写字母（S、U、V、Q）都是状态，小写字母a、b为动作。通过上图我们可以看到如下关系

a b b  
S -----> U S -----> V U -----> V

在实现敏感词过滤的算法中，我们必须要减少运算，而DFA在DFA算法中几乎没有什么计算，有的只是状态的转换。

![在这里插入图片描述][resize_m_lfit_w_962_pic_center]

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

在Java中实现敏感词过滤的关键就是DFA算法的实现。首先我们对上图进行剖析。在这过程中我们认为下面这种结构会更加清晰明了。  
![在这里插入图片描述][20201209205455898.png]  
同时这里没有状态转换，没有动作，有的只是Query（查找）。我们可以认为，通过S query U、V，通过U query V、P，通过V query U P。通过这样的转变我们可以将状态的转换转变为使用Java集合的查找。

诚然，加入在我们的敏感词库中存在如下几个敏感词：日本人、日本鬼子、毛.泽.东。那么我需要构建成一个什么样的结构呢？

首先：query 日 —> \{本\}、query 本 —>\{人、鬼子\}、query 人 —>\{null\}、query 鬼 —> \{子\}。形如下结构：

![在这里插入图片描述][20201209205545981.png]

下面我们在对这图进行扩展：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXl1a2FpZmE_size_16_color_FFFFFF_t_70]  
这样我们就将我们的敏感词库构建成了一个类似与一颗一颗的树，这样我们判断一个词是否为敏感词时就大大减少了检索的匹配范围。比如我们要判断日本人，根据第一个字我们就可以确认需要检索的是那棵树，然后再在这棵树中进行检索。

但是如何来判断一个敏感词已经结束了呢？利用标识位来判断。

所以对于这个关键是如何来构建一棵棵这样的敏感词树。下面我已Java中的HashMap为例来实现DFA算法。具体过程如下：

日本人，日本鬼子为例

1、在hashMap中查询“日”看其是否在hashMap中存在，如果不存在，则证明已“日”开头的敏感词还不存在，则我们直接构建这样的一棵树。跳至3。

2、如果在hashMap中查找到了，表明存在以“日”开头的敏感词，设置hashMap = hashMap.get(“日”)，跳至1，依次匹配“本”、“人”。

3、判断该字是否为该词中的最后一个字。若是表示敏感词结束，设置标志位isEnd = 1，否则设置标志位isEnd = 0；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXl1a2FpZmE_size_16_color_FFFFFF_t_70 1]  
**程序实现如下：**

/**
        * 读取敏感词库，将敏感词放入HashSet中，构建一个DFA算法模型：<br>
        * 中 = {
        *      isEnd = 0
        *      国 = {<br>
        *           isEnd = 0
        *           人 = {isEnd = 0
        *                民 = {isEnd = 1}
        *                }
        *           男  = {
        *                  isEnd = 0
        *                   人 = {
        *                        isEnd = 1
        *                       }
        *               }
        *           }
        *      }
        *  五 = {
        *      isEnd = 0
        *      星 = {
        *          isEnd = 0
        *          红 = {
        *              isEnd = 0
        *              旗 = {
        *                   isEnd = 1
        *                  }
        *              }
        *          }
        *      }最新2020整理收集的很多干货，包含mysql，netty，spring，线程，spring cloud、jvm、源码、算法等详细讲解，需要获取这些内容的朋友加QQ群：756584822
        * @author chenming 
        * @date 2014年4月20日 下午3:04:20
        * @param keyWordSet  敏感词库
        * @version 1.0
        */
       @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");    //最后一个
                   }
               }最新2020整理收集的很多干货，包含mysql，netty，spring，线程，spring cloud、jvm、源码、算法等详细讲解，需要获取这些内容的朋友加Q君样：756584822
           }
       }

运行得到的hashMap结构如下：

{五={星={红={isEnd=0, 旗={isEnd=1}}, isEnd=0}, isEnd=0}, 中={isEnd=0, 国={isEnd=0, 人={isEnd=1}, 男={isEnd=0, 人={isEnd=1}}}}}

敏感词库我们一个简单的方法给实现了，那么如何实现检索呢？检索过程无非就是hashMap的get实现，找到就证明该词为敏感词，否则不为敏感词。过程如下：假如我们匹配“中国人民万岁”。

1、第一个字“中”，我们在hashMap中可以找到。得到一个新的map = hashMap.get("")。

2、如果map == null，则不是敏感词。否则跳至3

3、获取map中的isEnd，通过isEnd是否等于1来判断该词是否为最后一个。如果isEnd == 1表示该词为敏感词，否则跳至1。

通过这个步骤我们可以判断“中国人民”为敏感词，但是如果我们输入“中国女人”则不是敏感词了。

/**
         * 检查文字中是否包含敏感字符，检查规则如下：<br>
         * @author chenming 
         * @date 2014年4月20日 下午4:31:03
         * @param txt
         * @param beginIndex
         * @param matchType
         * @return，如果存在，则返回敏感词字符的长度，不存在返回0
         * @version 1.0
         */
        @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){    //最小规则，直接返回,最大规则还需继续查找最新2020整理收集的很多干货，包含mysql，netty，spring，线程，spring cloud、jvm、源码、算法等详细讲解，需要获取这些内容的朋友加Q君样：756584822
                            break;
                        }
                    }
                }
                else{     //不存在，直接返回
                    break;
                }
            }
            if(matchFlag < 2 && !flag){     
                matchFlag = 0;
            }
            return matchFlag;
        }

运行结果：

![在这里插入图片描述][20201209205854540.png]  
从上面的结果可以看出，敏感词库有771个，检测语句长度为184个字符，查出6个敏感词。总共耗时1毫秒。可见速度还是非常可观的。  
![点击链接加入群聊【Java交流圈】][Java]

[**最新2020整理收集的一些高频面试题（都整理成文档），有很多干货，包含mysql，netty，spring，线程，spring cloud、jvm、源码、算法等详细讲解，也有详细的学习规划图，面试题整理等，需要获取这些内容的朋友请加Q君样：  
756584822**][2020_mysql_netty_spring_spring cloud_jvm_Q_ _ 756584822]

[20201209205325313.png]: /images/20210724/4fbaea64f7e94ca592237bc6e10fb9d0.png
[resize_m_lfit_w_962_pic_center]: /images/20210724/b76dc99fde8346fb9eac25e9d0aac46e.png
[20201209205455898.png]: /images/20210724/f4066a864e4f4f6cb78f18fb3cad1e52.png
[20201209205545981.png]: /images/20210724/e394b0e3cdd74a8b8c9ab43ad8666957.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXl1a2FpZmE_size_16_color_FFFFFF_t_70]: /images/20210724/e6b7ce7c22f14bc2978a432409369dd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXl1a2FpZmE_size_16_color_FFFFFF_t_70 1]: /images/20210724/6e3b61f35dff4c5ca541e27772424ade.png
[20201209205854540.png]: /images/20210724/dae0a718e4a7429b9489cae464fdd958.png
[Java]: /images/20210724/46a473d968b0433689857d56d13917bd.png
[2020_mysql_netty_spring_spring cloud_jvm_Q_ _ 756584822]: https://jq.qq.com/?_wv=1027&k=0IsBuUb0