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);
} - ==有更好方式 或者 優化的小夥伴可以評論==
- 個人部落格： http://blog.yanxiaolong.cn/ .