公司网站建设小知识,服务器2003怎么做网站,aspx网站架设教程,互联网大赛官网入口java过滤关键词 敏感词、文字过滤是一个网站必不可少的功能#xff0c;如何设计一个好的、高效的过滤算法是非常有必要的。前段时间我一个朋友#xff08;马上毕业#xff0c;接触编程不久#xff09;要我帮他看一个文字过滤的东西#xff0c;它说检索效率非常慢。我把它程…java过滤关键词 敏感词、文字过滤是一个网站必不可少的功能如何设计一个好的、高效的过滤算法是非常有必要的。前段时间我一个朋友马上毕业接触编程不久要我帮他看一个文字过滤的东西它说检索效率非常慢。我把它程序拿过来一看整个过程如下读取敏感词库、如果HashSet集合中获取页面上传文字然后进行匹配。我就想这个过程肯定是非常慢的。对于他这个没有接触的人来说我想也只能想到这个更高级点就是正则表达式。但是非常遗憾这两种方法都是不可行的。当然在我意识里没有我也没有认知到那个算法可以解决问题但是Google知道 DFA简介
在实现文字过滤的算法中DFA是唯一比较好的实现算法。DFA即Deterministic Finite Automaton也就是确定有穷自动机它是是通过event和当前的state得到下一个state即eventstatenextstate。下图展示了其状态的转换 在这幅图中大写字母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整理收集的很多干货包含mysqlnettyspring线程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(SetString keyWordSet) {sensitiveWordMap new HashMap(keyWordSet.size()); //初始化敏感词容器减少扩容操作String key null; Map nowMap null;MapString, String newWorMap null;//迭代keyWordSetIteratorString 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 HashMapString,String();newWorMap.put(isEnd, 0); //不是最后一个nowMap.put(keyChar, newWorMap);nowMap newWorMap;}if(i key.length() - 1){nowMap.put(isEnd, 1); //最后一个}}最新2020整理收集的很多干货包含mysqlnettyspring线程spring cloud、jvm、源码、算法等详细讲解需要获取这些内容的朋友加Q君样756584822}}运行得到的hashMap结构如下
{五{星{红{isEnd0, 旗{isEnd1}}, isEnd0}, isEnd0}, 中{isEnd0, 国{isEnd0, 人{isEnd1}, 男{isEnd0, 人{isEnd1}}}}}敏感词库我们一个简单的方法给实现了那么如何实现检索呢检索过程无非就是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; //匹配标识数默认为0char word 0;Map nowMap sensitiveWordMap;for(int i beginIndex; i txt.length() ; i){word txt.charAt(i);nowMap (Map) nowMap.get(word); //获取指定keyif(nowMap ! null){ //存在则判断是否为最后一个matchFlag; //找到相应key匹配标识1 if(1.equals(nowMap.get(isEnd))){ //如果为最后一个匹配规则,结束循环返回匹配标识数flag true; //结束标志位为true if(SensitivewordFilter.minMatchTYpe matchType){ //最小规则直接返回,最大规则还需继续查找最新2020整理收集的很多干货包含mysqlnettyspring线程spring cloud、jvm、源码、算法等详细讲解需要获取这些内容的朋友加Q君样756584822break;}}}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; //匹配标识数默认为0char word 0;Map nowMap sensitiveWordMap;for(int i beginIndex; i txt.length() ; i){word txt.charAt(i);nowMap (Map) nowMap.get(word); //获取指定keyif(nowMap ! null){ //存在则判断是否为最后一个matchFlag; //找到相应key匹配标识1 if(1.equals(nowMap.get(isEnd))){ //如果为最后一个匹配规则,结束循环返回匹配标识数flag true; //结束标志位为true if(SensitivewordFilter.minMatchTYpe matchType){ //最小规则直接返回,最大规则还需继续查找最新2020整理收集的很多干货包含mysqlnettyspring线程spring cloud、jvm、源码、算法等详细讲解需要获取这些内容的朋友加Q君样756584822break;}}}else{ //不存在直接返回break;}}if(matchFlag 2 !flag){ matchFlag 0;}return matchFlag;}运行结果
