spring boot 使用DFA算法实现敏感词过滤
敏感词、文字过滤是一个网站必不可少的功能，如何设计一个好的、高效的过滤算法是非常有必要的。
DFA算法简介
DFA全称为：Deterministic Finite Automaton,即确定有穷自动机。其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。
- 确定：状态以及引起状态转换的事件都是可确定的，不存在“意外”。
- 有穷：状态以及事件的数量都是可穷举的。
计算机操作系统中的进程状态与切换可以作为 DFA 算法的一种近似理解。如下图所示，其中椭圆表示状态，状态之间的连线表示事件，进程的状态以及事件都是可确定的，且都可以穷举。
数据结构
state_event_dict = {
"匹": {
"配": {
"算": {
"法": {
"is_end": True
},
"is_end": False
},
"关": {
"键": {
"词": {
"is_end": True
},
"is_end": False
},
"is_end": False
},
"is_end": False
},
"is_end": False
},
"信": {
"息": {
"抽": {
"取": {
"is_end": True
},
"is_end": False
},
"is_end": False
},
"is_end": False
}
}
Java实现DFA算法实现敏感词过滤
- 定义敏感词词库 让SpringBoot加载到
- 这里用到了 @Bean 以及 @Autowired 注入到算法map里面
@Configuration
public class CheckConfig {
@Autowired
private DFAUtil dfaUtil;
@Bean
public void init(){
Set<String> set=new HashSet<>();
set.add("你好");
set.add("你好吗");
set.add("他好");
set.add("她不好");
set.add("子");
//将集合放到算法里，这里可以优化，写词库文件等等，
dfaUtil.createDFAHashMap(set);
}
}- 创建AOP切面 前置通知
package com.yxl.aspect;
@Component
@Aspect
@Slf4j
public class CheckInputParameterAspect {
private static final Log Logger = LogFactory.getLog(com.yxzapp.aspect.CheckInputParameterAspect.class);
@Autowired
private DFAUtil dfaUtil ;
/**
* 定义切入点:拦截controller层所有方法
*/
@Pointcut("execution(public * com.yxl.modules.*..*Controller.*(..))")
public void params() {
}
/**
* 前置通知
*
* @param
* @throws Throwable
*/
@Before("params()")
public Object before(JoinPoint point) throws Throwable {
ServletRequestAttributes attributes = (ServletRequestAttributes) RequestContextHolder.getRequestAttributes();
HttpServletRequest request = Objects.requireNonNull(attributes).getRequest();
//获取请求参数
Object[] args = point.getArgs();
// 数组转 String
Set<String> sensitiveWordByDFAMap = dfaUtil.getSensitiveWordByDFAMap(StringUtils.join(args,","), 1);
Logger.info("敏感词有"+sensitiveWordByDFAMap.size()+"个");
if(sensitiveWordByDFAMap.size()>=1){
//自定义的异常
throw new BizException("500","您输入的内容有敏感词");
}
Logger.info("当前调用接口-[" + request.getRequestURL() + "]");
return args;
}
}
- DFA算法 工具类
package com.yxzapp.utils;
import org.springframework.stereotype.Component;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
@Component
public class DFAUtil {
HashMap<String, Object> dfaMap;
public static final int minMatchType=1;
public static final int maxMatchType=2;
/*{日=
* {本=
* {人={isEnd=1},
* 鬼=
* {子={isEnd=1},
* isEnd=0},
* isEnd=0},
* isEnd=0},
*
* 大=
* {汉=
* {民={isEnd=0,
* 族={isEnd=1}},
* isEnd=0},
* isEnd=0,
* 中={isEnd=0,
* 华={isEnd=1,
* 帝={isEnd=0,
* 国={isEnd=1}}}}}}*/
/**set作为敏感词，创建出对应的dfa的Map，以供检验敏感词
* @param set
*/
public void createDFAHashMap(Set<String> set){
HashMap<String, Object> nowMap;
//根据set的大小，创建map的大小
dfaMap=new HashMap<>(set.size());
//对set里的字符串进行循环
for(String key:set){
//对每个字符串最初，nowMap就是dfaMap
nowMap=dfaMap;
for(int i=0;i<key.length();i++){
//一个个字符循环
String nowChar=String.valueOf(key.charAt(i));
//根据nowChar得到nowMap里面对应的value
HashMap<String, Object> map=(HashMap<String, Object>)nowMap.get(nowChar);
//如果map为空，则说明nowMap里面没有以nowChar开头的东西，则创建一个新的hashmap，
//以nowChar为key，新的map为value，放入nowMap
if(map==null){
map=new HashMap<String,Object>();
nowMap.put(nowChar, map);
}
//nowMap=map，就是nowChar对应的对象
nowMap=map;
//最后在nowMap里设置isEnd
//如果nowMap里面已经有isEnd，并且为1，说明以前已经有关键字了，就不再设置isEnd
//因为如果没有这一步，大中华和大中华帝国，先设置大中华
//在大中华帝国设置的时候，华对应的map有isEnd=1，如果这时对它覆盖，就会isEnd=0，导致大中华这个关键字失效
if(nowMap.containsKey("isEnd")&&nowMap.get("isEnd").equals("1")){
continue;
}
if(i!=key.length()-1){
nowMap.put("isEnd", "0");
}
else{
nowMap.put("isEnd", "1");
}
}
}
System.out.println(dfaMap);
}
/** 用创建的dfaMap，根据matchType检验字符串string是否包含敏感词，返回包含所有对于敏感词的set
* @param string 要检查是否有敏感词在内的字符串
* @param matchType 检查类型，如大中华帝国牛逼对应大中华和大中华帝国两个关键字，1为最小检查，会检查出大中华，2位最大，会检查出大中华帝国
* @return
*/
public Set<String> getSensitiveWordByDFAMap(String string,int matchType){
Set<String> set=new HashSet<>();
for(int i=0;i<string.length();i++){
//matchType是针对同一个begin的后面，在同一个begin匹配最长的还是最短的敏感词
int length=getSensitiveLengthByDFAMap(string,i,matchType);
if(length>0){
set.add(string.substring(i,i+length));
//这个对应的是一个敏感词内部的关键字（不包括首部），如果加上，大中华帝国，对应大中华和中华两个敏感词，只会对应大中华而不是两个
//i=i+length-1;//减1的原因，是因为for会自增
}
}
return set;
}
/**如果存在，则返回敏感词字符的长度，不存在返回0
* @param string
* @param beginIndex
* @param matchType 1：最小匹配规则，2：最大匹配规则
* @return
*/
public int getSensitiveLengthByDFAMap(String string,int beginIndex,int matchType){
//当前匹配的长度
int nowLength=0;
//最终匹配敏感词的长度，因为匹配规则2，如果大中华帝，对应大中华，大中华帝国，在华的时候，nowLength=3，因为是最后一个字，将nowLenth赋给resultLength
//然后在帝的时候，now=4，result=3，然后不匹配，resultLength就是上一次最大匹配的敏感词的长度
int resultLength=0;
HashMap<String, Object> nowMap=dfaMap;
for(int i=beginIndex;i<string.length();i++){
String nowChar=String.valueOf(string.charAt(i));
//根据nowChar得到对应的map，并赋值给nowMap
nowMap=(HashMap<String, Object>)nowMap.get(nowChar);
//nowMap里面没有这个char，说明不匹配，直接返回
if(nowMap==null){
break;
}
else{
nowLength++;
//如果现在是最后一个，更新resultLength
if("1".equals(nowMap.get("isEnd"))){
resultLength=nowLength;
//如果匹配模式是最小，直接匹配到，退出
//匹配模式是最大，则继续匹配，resultLength保留上一次匹配到的length
if(matchType==minMatchType){
break;
}
}
}
}
return resultLength;
}
}- 测试
@ApiOperation(value = "测试", notes = "测试")
@PostMapping("gettest")
public ResultBody gettest(@RequestParam String aa,
@RequestParam String bb){
return ResultBody.success(aa+bb);
}
- ==有更好方式 或者 优化的小伙伴可以评论==
