一、DFA 算法簡介
在實作文字過濾的算法中，DFA是唯一比較好的實作算法。
DFA 全稱為：Deterministic Finite Automaton，即确定有窮自動機。其特征為：有一個有限狀态集合和一些從一個狀态通向另一個狀态的邊，每條邊上标記有一個符号，其中一個狀态是初态，某些狀态是終态。但不同于不确定的有限自動機，DFA 中不會有從同一狀态出發的兩條邊标志有相同的符号。
簡單點說就是，它是是通過 event 和目前的 state 得到下一個 state，即 event + state= nextstate。了解為系統中有多個節點，通過傳遞進入的 event，來确定走哪個路由至另一個節點，而節點是有限的。
二、DEA 算法實踐敏感詞過濾
1. 敏感詞庫構造
以王八蛋和王八羔子兩個敏感詞來進行描述，首先建構敏感詞庫，該詞庫名稱為SensitiveMap，這兩個詞的二叉樹構造為：
用 hash 表構造為：
{
"王":{
"isEnd":"0",
"八":{
"羔":{
"子":{
"isEnd":"1"
},
"isEnd":"0"
},
"isEnd":"0",
"蛋":{
"isEnd":"1"
}
}
}
}
怎麼用代碼實作這種資料結構呢？
/**
* 讀取敏感詞庫，将敏感詞放入HashSet中，建構一個DFA算法模型
*
* @param keyWordSet 敏感詞庫
*/
public Map<String, Object> addSensitiveWordToHashMap(Set<String> keyWordSet) {
//初始化敏感詞容器，減少擴容操作
Map<String, Object> map = new HashMap(Math.max((int) (keyWordSet.size() / .75f) + 1, 16));
//疊代keyWordSet
for (String aKeyWordSet : keyWordSet) {
Map nowMap = map;
for (int i = 0; i < aKeyWordSet.length(); i++) {
//轉換成char型
char keyChar = aKeyWordSet.charAt(i);
//擷取
Object wordMap = nowMap.get(keyChar);
//如果存在該key，直接指派
if (wordMap != null) {
nowMap = (Map) wordMap;
} else { //不存在則，則建構一個map，同時将isEnd設定為0
Map<String, String> newWorMap = new HashMap<>(3);
newWorMap.put("isEnd", "0");
nowMap.put(keyChar, newWorMap);
nowMap = newWorMap;
}
//判斷最後一個
if (i == aKeyWordSet.length() - 1) {
nowMap.put("isEnd", "1");
}
}
}
return map;
}
2. 敏感詞過濾
以上面例子構造出來的 SensitiveMap 為敏感詞庫進行示意，假設這裡輸入的關鍵字為：王八不好，流程圖如下：
怎麼用代碼實作這個流程圖邏輯呢？
/**
* 查找字元串中是否包含敏感字元
*
* @param txt 輸入的字元串
* @return 如果存在，則傳回敏感字元串；不存在，則傳回空字元串
*/
public static String findSensitiveWord(String txt) {
SensitiveWordInit sensitiveWordInit = SpringContextHolder.getBean(SensitiveWordInit.class);
Map<String, Object> sensitiveWordMap = sensitiveWordInit.getSensitiveWordMap();
StringBuilder sensitiveWord = new StringBuilder();
// 敏感詞結束标志位，表示比對到了最後一位
boolean flag = false;
for (int i = 0; i < txt.length(); i++) {
char word = txt.charAt(i);
// 擷取指定 key
sensitiveWordMap = (Map) sensitiveWordMap.get(word);
// 不存在，直接傳回沒有敏感詞
if (sensitiveWordMap == null) {
break;
}
//存在，存儲該敏感詞，并判斷是否為最後一個
sensitiveWord.append(word);
//如果為最後一個比對規則，結束循環
if ("1".equals(sensitiveWordMap.get("isEnd"))) {
flag = true;
break;
}
}
// 表示比對到了完整敏感詞
if (flag == true) {
return sensitiveWord.toString();
}
return "";
}
三、優化思路
對于“王*八&&蛋”這樣的詞，中間填充了無意義的字元來混淆，在我們做敏感詞搜尋時，同樣應該做一個無意義詞的過濾，當循環到這類無意義的字元時進行跳過，避免幹擾。