DFA算法實戰：高效敏感詞過濾系統設計與優化

背景：為什麼選擇DFA算法？

專案需對數千條敏感詞進行過濾。經方案對比：

• 方案a：String.indexOf() —— 數千敏感詞遍歷匹配，時間複雜度O(n×m)，性能不可接受
• 方案b：SQL Like查詢 —— 強依賴資料庫，擴展性差，高併發下瓶頸明顯
• 方案c：Lucene分詞索引 —— 需維護索引更新，引入重型依賴，違背輕量化原則
• 方案d：DFA確定性有限自動機 —— 構建狀態機一次掃描，時間複雜度O(n)，無外部依賴，最終選型

DFA算法核心原理

DFA（Deterministic Finite Automaton）：有限狀態集合、狀態轉移邊（邊標記符號）、唯一初態、若干終態。關鍵特性：同一狀態不會有兩條相同符號的出邊，即「確定性」。

簡化理解：Event + CurrentState = NextState。系統包含有限節點，輸入字符決定路由跳轉至下一節點。

敏感詞庫構建：以「王八蛋」「王八羔子」為例

Trie樹（字典樹）結構

共用前綴「王八」，分支於「蛋」「羔子」。終態節點標記isEnd=true。

HashMap嵌套實現（工程落地）

// 結構示例
Map<Character, Map> root = new HashMap<>();
// 「王」→「八」→{"蛋":{isEnd:true}, "羔"→"子":{isEnd:true}}

檢索流程：輸入「王八不好」

1. 讀『王』→ 根節點存在，移動到『王』節點
2. 讀『八』→ 存在，移動到『八』節點，檢查isEnd=false
3. 讀『不』→ 『八』節點無『不』子節點 → 匹配失敗，重置狀態
4. 重新從『不』開始匹配……

核心邏輯：指針不回退，狀態機單向流動，保證O(n)掃描。

核心代碼實現

1. 敏感詞庫構建

public void addSensitiveWord(String word) {
    Map nowMap = sensitiveWordMap;
    for (int i = 0; i < word.length(); i++) {
        char key = word.charAt(i);
        Map nextMap = (Map) nowMap.get(key);
        if (nextMap == null) {
            nextMap = new HashMap();
            nextMap.put("isEnd", "0");
            nowMap.put(key, nextMap);
        }
        nowMap = nextMap;
        if (i == word.length() - 1) nowMap.put("isEnd", "1");
    }
}

2. 敏感詞檢測

public Set<String> getSensitiveWords(String text) {
    Set<String> result = new HashSet<>();
    for (int i = 0; i < text.length(); i++) {
        int matchLen = checkSensitiveWord(text, i);
        if (matchLen > 0) {
            result.add(text.substring(i, i + matchLen));
            i += matchLen - 1; // 跳過已匹配部分
        }
    }
    return result;
}

工程優化方向

5.1 無意義字符干擾（如「王*八&&蛋」）

檢測循環中維護停用詞集合（標點、特殊符號、零寬字符等），遇停用詞跳過不推進狀態機，僅移動文本指針，保持當前節點不變。

5.2 拼音/同音字繞過（如「wang2ba8dan4」）

兩條路徑：

1. 擴充詞庫：收集常見變體入庫，見效快但治標不治本
2. 拼音映射檢測：輸入文本轉拼音（含聲調/無聲調），同步在拼音詞庫匹配。需解決多音字、同音歧義

現階段雙方案並行，長期需引入NLP語義分析徹底解決。

總結

DFA算法以空間換時間，構建Trie狀態機實現單次掃描多模式匹配，是敏感詞過濾的經典選型。工程落地需關注：內存佔用優化（雙數組Trie/AC自動機）、干擾字符處理、變體識別擴展。代碼結構清晰，易於維護與水平擴展。