JAVA中的DFA算法构建敏感词树，从0开始！

前一阵做项目涉及到敏感词检测问题，因为这个模块要求不是很高，应用场景就是用户在文章下面评论，或者发布留言等需要管理员进行审核，所以要在给管理员审核的页面对评论内容中的敏感词标红、判断内容是否有敏感词等，这样能让管理员快速审核。

因为我这个敏感词模块涉及到的东西不是很多，所以做的可能比较简单，粗糙，第一次写博客，请谅解！有什么建议欢迎提出来！

下面说一下我的构建过程：

首先从第一步建表开始

项目需求是需要对敏感词有两种应用方式，一种是阻止，一种是替换。这两种方式不一定适用于所有模块，现在是针对留言、评论等，但是以后可能会涉及到别的模块。但是阻止的优先级是比替换高的。所以我当初的设想就是，表字段中有两个字段存该敏感词是阻止哪个模块，替换哪个模块，如果有需要自动代理，不需要人工审核的，只需要拿内容来，先进行检测，检测出敏感词，再拿敏感词去数据库取对象，判断该敏感词对于正在应用的模块是敏感还是替换，首先是要进行敏感词匹配。

附上我的SQL：

CREATE TABLE `base_sys_sensitive` (
  `ID` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `NAME` varchar(200) DEFAULT NULL COMMENT '敏感词',
  `REPLACENAME` varchar(200) DEFAULT NULL COMMENT '替换词',
  `PREVENTOBJ` varchar(100) DEFAULT NULL COMMENT '阻止对象（适用范围）',
  `REPLACEOBJ` varchar(100) DEFAULT NULL COMMENT '替换对象（适用范围）',
  `CREATEUSER` int(11) unsigned DEFAULT NULL,
  `CREATETIME` timestamp NULL DEFAULT NULL,
  `UPDATEUSER` int(11) unsigned DEFAULT NULL,
  `UPDATETIME` timestamp NULL DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,
  `DELFLAG` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `REMARK` varchar(200) DEFAULT NULL COMMENT '备注',
  PRIMARY KEY (`ID`)
) ENGINE=MyISAM AUTO_INCREMENT=250596 DEFAULT CHARSET=utf8;

然后就是POJO创建，这里不多说，接下来说敏感词树的构建问题：

根据我的大致计算，4万条敏感词加载到缓存其实占用的内存还是很小的，实测4万条敏感词树构建大概200ms以内，足够满足我的需求；

首先建立一个敏感词工具类：

这棵树因为是要在项目启动的时候进行初始化，在类中声明一个静态的map；

然后下一步就是用sensitiveService去数据库一次拿到所有的敏感词；

为防止数据库有脏数据，导致有重复敏感词（新增敏感词的时候，名称有唯一性检测，只是为了防止脏数据），这里先用set去重；

private static Set readSensitiveWordFile(){  
        Set set = null;  
        set = new HashSet();
        List sensitiveList = sensitiveService.queryAll();
        for(Sensitive sensitive : sensitiveList){
        	set.add(sensitive.getName());
        }
        return set;
    }

到这里的时候整个数据库中的敏感词都已经拿到了；

下一步就是初始化敏感词树；

 @SuppressWarnings({ "rawtypes"})  
    private static Map addSensitiveWordToHashMap(Set keyWordSet) {  
        Map sensitiveWordMap = new HashMap();
        String key = null;    
        // 迭代keySet  
        Iterator iterator = keyWordSet.iterator();  
        while(iterator.hasNext()){  
            key = iterator.next(); 
            addSensitiveWordToHashMap(sensitiveWordMap, key);
        }
        return sensitiveWordMap;
    }

这个方法主要是对敏感词set进行迭代，一条条的插入到树中；

下面看下addSensitiveWordToHashMap（）方法，这个方法是插入敏感词方法；

@SuppressWarnings({ "rawtypes", "unchecked" })  
    private static void addSensitiveWordToHashMap(Map map, String sensitive){
    	Map newWorMap = null;  
    	 for(int i = 0 ; i < sensitive.length() ; i++){  
         	// 转换成char型  
             char keyChar = sensitive.charAt(i); 
             Object wordMap = map.get(keyChar); 
             // 如果存在该key，直接赋值  
             if (wordMap != null) { 
            	 map = (Map) wordMap;  
             }else { 
             	// 不存在就构建一个map，同时将isEnd设置为0  
                 newWorMap = new HashMap();  
                 // 不是最后一个  
                 newWorMap.put("isEnd", "0"); 
                 map.put(keyChar, newWorMap);
                 map = newWorMap;
             }  
             if(i == sensitive.length() - 1){  
             	// 最后一个  
            	 map.put("isEnd", "1");
             }  
         }  
    }

这个我的敏感词树就一条条的构建成功了；

当插入一条敏感词的时候，比如“小明是狗”，那么会先去map中get小，不存在就构建一个map放这个小，标识该词还没有结束，如果存在，就去小对应的map中get明以此类推，当到狗的时候，标识该词已经结束了；添加isEend为1；

那么我这里为什么要分好几个方法写呢，主要是为了项目需求，因为我们敏感词是有个管理的页面，管理员可以对某个敏感词进行添加，修改，删除操作的，所以当管理员进行这些操作的时候，这个树肯定也是要随机应变的，我这里的做法就是对外提供两个公开方法，一个添加敏感词，一个重置敏感词树， 那么在新增敏感词的时候我只需要对树中进行添加一条就行了， 删除和修改，就重置一下敏感词树（反正咱们构建时间也不长—_—）......

先来看一下对外封装的添加敏感词方法：

public static void addSensitiveWordToHashMap(String sensitive){
    	if(sensitiveWordMap == null){
    		sensitiveWordMap = addSensitiveWordToHashMap(readSensitiveWordFile());
    	}
    	addSensitiveWordToHashMap(sensitiveWordMap, sensitive);
    }

再来看一下重新构建树的方法：

public static void resetSensitiveWordTree(){
    	sensitiveWordMap = addSensitiveWordToHashMap(readSensitiveWordFile());
    }

重新构建就是重新去数据库取一次，然后构建；

树构建好了，那么下一步就是检测了：

对外提供方法有：1、该字符串是否存在敏感，2、找出字符串中所有的敏感词，3、替换字符串中的所有敏感词

他们都是基于一个方法，就是敏感词检测方法：

 @SuppressWarnings({ "rawtypes"})  
    public static int checkSensitiveWord(String txt, int beginIndex){
    	if(StringUtils.isBlank(txt)){
    		return IConstant.ZERO;
    	}
    	if(sensitiveWordMap == null){
    		sensitiveWordMap = addSensitiveWordToHashMap(readSensitiveWordFile());
    	}
    	//防止敏感词只有1个  
        boolean flag = false;  
        int matchFlag = 0; 
        char word = 0;  
        Map nowMap = sensitiveWordMap;  
        for(int i = beginIndex; i < txt.length() ; i++){  
            word = txt.charAt(i);  
            // 获取指定key  
            nowMap = (Map) nowMap.get(word); 
            // 存在就判断是否是最后一个  
            if (nowMap != null) { 
            	// 找到相应key，匹配标识+1  
                matchFlag++; 
                // 如果为最后一个匹配规则,结束循环，返回匹配标识数  
                if ("1".equals(nowMap.get("isEnd"))) { 
                	// 结束标志位为true  
                    flag = true; 
                }  
            }else { 
            	// 不存在，直接返回  
                break;  
            }  
        }  
        // 长度必须大于等于1 
        if (matchFlag < 2 || !flag) { 
            matchFlag = 0;  
        }  
        return matchFlag;  
    }  

这个方法返回的是该字符串中出现敏感词的起始位置；

然后封装一层，判断字符串中是否有敏感词：

public static boolean isContaintSensitiveWord(String txt){  
    	if(StringUtils.isBlank(txt)){
    		return false;
    	}
        boolean flag = false;  
        for(int i = 0 ; i < txt.length() ; i++){  
        	// 判断是否包含敏感字符  
            int matchFlag = checkSensitiveWord(txt, i); 
            // 大于0存在，返回true  
            if (matchFlag > 0) { 
                flag = true;  
            }  
        }  
        return flag;  
    } 

还一个方法就是获取字符串中所有的敏感词：

 public static Set getSensitiveWord(String txt) { 
    	if(StringUtils.isBlank(txt)){
    		return null;
    	}
        Set sensitiveWordList = new HashSet();  
        for(int i = 0 ; i < txt.length() ; i++){  
       	    // 判断是否包含敏感字符  
            int length = checkSensitiveWord(txt, i); 
            // 存在就加入set中  
            if (length > 0) { 
                sensitiveWordList.add(txt.substring(i, i+length));  
                // 减1因为for会自增
                i = i + length - 1; 
            }  
        }  
        return sensitiveWordList;  
    }

这里的做法就是对字符串进行循环，找到一个敏感词就截掉，再循环，一直到没有敏感词，这里用set是防止检测到重复敏感词；

还有一个替换敏感词方法：

    public static String replaceSensitiveWord(String txt) { 
    	if(StringUtils.isBlank(txt)){
    		return null;
    	}
        String resultTxt = txt;  
        // 获取所有的敏感词  
        Set set = getSensitiveWord(txt); 
        Iterator iterator = set.iterator();  
        String word = null;  
        String replaceString = null;  
        while (iterator.hasNext()) {  
            word = iterator.next();  
            replaceString = getReplaceChars(word);
            resultTxt = resultTxt.replaceAll(word, replaceString);  
        }  
        return resultTxt;  
    }

这里会用到一个getReplaceChars（）方法，这个方法是获取敏感词对于的替换词，因为我的需求是要替换词准确到某个词，所有敏感词的替换词都对应的存在数据库；

下面也贴一下这个方法吧

public static String getReplaceChars (String name){
    	if(StringUtils.isBlank(name)){
    		return null;
    	}
    	Sensitive sensitive = new Sensitive();
    	sensitive.setName(name);
    	sensitive = sensitiveService.queryOne(sensitive);
    	if(sensitive != null){
    		String replaceTxt = sensitive.getReplacename();
    		if(StringUtils.isNotBlank(replaceTxt)){
    			return replaceTxt;
    		} 
    	}
    	return null;
    }

这里其实就是一个拿敏感词去数据库取替换词的过程；

到此整个工具类就算是能对外提供使用了，只需要在数据库插入敏感词就能用了；

做的比较粗糙，因为时间问题，也比较赶，可能以后需求还会改；

当然这个也是有缺陷的！

缺陷就是：1、空格也会列入检测范围，就是某个词可能最后加上空格也会被构建到树中，这样有好处，也有坏处

2、没有引入距离概念，比如;词是“小明是狗”， 那么“小明.是狗”、“小明 是 狗 ”。。。。。等等这样的都不会被检测出来，所以有很大的局限性，请根据自己的需求来判断！

3、。。。。。。。还有其他的我就不多说了。个人理解 嘿嘿~~~~~~~

新手第一次写博客~~~，如有什么技术的语言、或者代码纰漏，请指正！！！ 但是别喷我~~~喷我我会很伤心~