阿里Java大神教你java快速过滤关键词

作者 : 开心源码 本文共4840个字,预计阅读时间需要13分钟 发布时间: 2022-05-13 共290人阅读

java过滤关键词

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

DFA简介

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

在这里插入图片形容

在这幅图中大写字母(S、U、V、Q)都是状态,小写字母a、b为动作。通过上图我们可以看到如下关系

a b b
S —–> U S —–> V U —–> V

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

在这里插入图片形容

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

在Java中实现敏感词过滤的关键就是DFA算法的实现。首先我们对上图进行剖析。在这过程中我们认为下面这种结构会更加清晰明了。

在这里插入图片形容

同时这里没有状态转换,没有动作,有的只是Query(查找)。我们可以认为,通过S query U、V,通过U query V、P,通过V query U P。通过这样的转变我们可以将状态的转换转变为使用Java集合的查找。

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

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

在这里插入图片形容

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

在这里插入图片形容

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

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

所以对于这个关键是如何来构建一棵棵这样的敏感词树。下面我已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 = 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;    }
/**     * 检查文字中能否包含敏感字符,检查规则如下:<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;    }

运行结果:

在这里插入图片形容

从上面的结果可以看出,敏感词库有771个,检测语句长度为184个字符,查出6个敏感词。总共耗时1毫秒。可见速度还是非常可观的。

点击链接加入群聊【Java交流圈】

最新2020整理收集的少量高频面试题(都整理成文档),有很多干货,包含mysql,netty,spring,线程,spring cloud、jvm、源码、算法等详细讲解,也有详细的学习规划图,面试题整理等,需要获取这些内容的朋友请加Q君样:
756584822

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 阿里Java大神教你java快速过滤关键词

发表回复