java使用DFA算法实现敏感词过滤 java使用dfa算法实现敏感词过滤效果

DFA检索敏感词的原理就是将敏感词生成一个索引map，将每个敏感词的每个字符生成对应的索引树，检索字符子串是否为敏感词时，只要根据一个字符即可找到对应的map，下一个字符又可以根据现有的map获取，如此循环，大大缩减的搜索范围，提高了搜索效率。

DFA算法无需引入任何jar，只要生成索引树和检索索引树即可，

所以本文的核心为索引树的生成和索引树的检索，

代码如下：

package com.silverbox.user.web.htmdemo;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
/**
 * 敏感词处理器
 * 使用DFA算法实现敏感词过滤
 * @author sjs
 *
 */
//@Component
public class DFAUtils {
	public static HashMap<String, Object> dfaStore;//索引存储表
    public static final int minMatchMode=1;//最小匹配模式敏感词
    public static final int maxMatchMode=2;//最大匹配模式敏感词
    
    
  /*  
    
    {
    	垃 = {
    		isEnd = 0,
    		圾 = {
    			分 = {
    				子 = {
    					isEnd = 1
    				},
    				isEnd = 0
    			},
    			isEnd = 1
    		}
    	}, 东 = {
    		亚 = {
    			病 = {
    				夫 = {
    					子 = {
    						isEnd = 1
    					},
    					isEnd = 1
    				},
    				isEnd = 0
    			},
    			isEnd = 0
    		},
    		isEnd = 0
    	}, 好 = {
    		垃 = {
    			isEnd = 0,
    			圾 = {
    				啊 = {
    					isEnd = 1
    				},
    				isEnd = 0
    			}
    		},
    		isEnd = 0
    	}
    }
    
   */ 
    public static void buildDFAMap(Set<String> set){
        HashMap<String, Object> tmpMap;
        //创建map的大小
        dfaStore=new HashMap<>(set.size());
        //对set里的字符串进行循环
        for(String key:set){
            //对每个敏感字符串进行设置索引，每个敏感词从map的最外层开始检索
            tmpMap=dfaStore;
            for(int i=0;i<key.length();i++){
                //循环每一个字符，作为map的key
                String currentChar=String.valueOf(key.charAt(i));
                //获取key对应map的value，value本身也是一个map
                HashMap<String, Object> map=(HashMap<String, Object>)tmpMap.get(currentChar);
                
                //如果value对应的map为空，则创建一个map
                if(map==null){
                    map=new HashMap<String,Object>();
                    tmpMap.put(currentChar, map);
                }
                
                if(map.containsKey("isEnd")&&map.get("isEnd").equals("1")){
                    continue;
                }
                if(i!=key.length()-1){
                	map.put("isEnd", "0");
                }
                else{
                	map.put("isEnd", "1");
                }
                //一直让里层的map循环
                tmpMap=map;
            }
        }
        //System.out.println(dfaStore);
    }
    /** 用创建的dfaStore，根据匹配模式matchMode检验字符串text是否存在敏感词，返回对应的敏感词
     * @param text 要检查是否有敏感词在内的字符串
     * @param matchMode 匹配模式，如‘dafaf垃圾分子daasfsf’，1为最短匹配，会检查出垃圾，2为最长匹配，会检查出垃圾分子
     * @return
     */
    public static String toGetSensitiveString(String text,int matchMode){
        Set<String> set=new HashSet<>();
        for(int i=0;i<text.length();i++){
            //matchType是针对同一个begin的后面，在同一个begin匹配最长的还是最短的敏感词
            int length=getSensitiveString(text,i,matchMode);
            if(length>0){
                
                return text.substring(i,i+length);
                
            }
        }
        return null;
    }
    /**查找字符串是否存在敏感词，返回subSting的长度
     * @param text
     * @param startIndex
     * @param matchMode  1：最小匹配模式，一旦匹配到敏感词即返回，2：最大匹配模式  ，找到敏感词后，还会尝试往后找，可能还存在更长的敏感词
            * 如：  垃圾、垃圾分子   都是敏感词，最短匹配原则就是找到垃圾马上终止，最大匹配则是找到了垃圾后，还会尝试找到更长的，如果找到垃圾分子，垃圾就不返回了
                    返回垃圾分子
     * @return
     */
    public static int getSensitiveString(String text,int startIndex,int matchMode){
        //当前匹配的长度
        int tmpLength=0;
        //返回的结果长度
        int subStrLength=0;
        HashMap<String, Object> tmpMap=dfaStore;
        for(int i=startIndex;i<text.length();i++){
            String tmpChar=String.valueOf(text.charAt(i));
            //根据key获取子map，此处一直遍历子map
            tmpMap=(HashMap<String, Object>)tmpMap.get(tmpChar);
            //nowMap里面没有这个char，说明不匹配，直接返回
            if(tmpMap==null){
                break;
            }
            else{
                tmpLength++;
                if("1".equals(tmpMap.get("isEnd"))){
                    subStrLength=tmpLength;
                    //如果..匹配模式是最小模式，找到最短的敏感词即退出，否则会尝试找最长的敏感词
                    if(matchMode==minMatchMode){
                        break;
                    }
                }
            }
        }
        return subStrLength;
    }
    
    
    
    public static void main(String[] args) {
    	String text="dafaf东亚病夫daasf东亚病夫sf";
    	Set<String> set=new HashSet<>();
        set.add("垃圾");
        set.add("垃圾分子");
        set.add("好垃圾啊");
        set.add("东亚病夫");
        set.add("东亚病夫子");
        //将集合放到算法里，这里可以优化放入redis等都可以
        buildDFAMap(set);
        //调用敏感检测方法返回敏感词
        String result = toGetSensitiveString(text, 1);
        System.out.println("原文："+text);
        System.out.println("敏感词："+result);
	}
}

运行结果