對于一個游戲，如果有聊天功能，那么我們就會希望我們的聊天系統能夠對玩家的輸入進行判斷，如果玩家的輸入中含有一些敏感詞匯，那么我們就禁止玩家發送聊天，或者把敏感詞轉換為 * 來替換。

為什么要使用 DFA 算法

設我們已經有了一個敏感詞詞庫(從相關部門獲取到的，或者網上找來的)，那么我們最容易想到的過濾敏感詞的方法就是：
遍歷整個敏感詞庫，拿到敏感詞，再判斷玩家輸入的字符串中是否有該敏感詞，如果有就把敏感詞字符替換為 *

但這樣的方法，我們需要遍歷整個敏感詞庫，并且對玩家輸入的字符串進行替換。而整個敏感詞庫中一般會有上千個字符串。而玩家聊天輸入的字符串一般也就 20~30 個字符。
因此，這種方法的效率是非常低的，無法應用到真實的開發中。

而使用 DFA 算法就可以實現高效的敏感詞過濾。使用 DFA 算法，我們只需要遍歷一遍玩家輸入的字符串即可將所有存在的敏感詞進行替換。

DFA 算法原理

DFA 算法是通過提前構造出一個 樹狀查找結構(實際上應該說是一個 森林)，之后根據輸入在該樹狀結構中就可以進行非常高效的查找。

設我們有一個敏感詞庫，詞酷中的詞匯為：
我愛你
我愛他
我愛她
我愛你呀
我愛他呀
我愛她呀
我愛她啊

那么就可以構造出這樣的樹狀結構：

設玩家輸入的字符串為：白菊我愛你呀哈哈哈

我們遍歷玩家輸入的字符串 str，并設指針 i 指向樹狀結構的根節點，即最左邊的空白節點：
str[0] = ‘白’ 時，此時 tree[i] 沒有指向值為 ‘白’ 的節點，所以不滿足匹配條件，繼續往下遍歷
str[1] = ‘菊’，同樣不滿足匹配條件，繼續遍歷
str[2] = ‘我’，此時 tree[i] 有一條路徑連接著 ‘我’ 這個節點，滿足匹配條件，i 指向 ‘我’ 這個節點，然后繼續遍歷
str[3] = ‘愛’，此時 tree[i] 有一條路徑連著 ‘愛’ 這個節點，滿足匹配條件，i 指向 ‘愛’，繼續遍歷
str[4] = ‘你’，同樣有路徑，i 指向 ‘你’，繼續遍歷
str[5] = ‘呀’，同樣有路徑，i 指向 ‘呀’
此時，我們的指針 i 已經指向了樹狀結構的末尾，即此時已經完成了一次敏感詞判斷。我們可以用變量來記錄下這次敏感詞匹配開始時玩家輸入字符串的下標，和匹配結束時的下標，然后再遍歷一次將字符替換為 * 即可。
結束一次匹配后，我們把指針 i 重新指向樹狀結構的根節點處。
此時我們玩家輸入的字符串還沒有遍歷到頭，所以繼續遍歷：
str[6] = ‘哈’，不滿足匹配條件，繼續遍歷
str[7] = ‘哈’ …
str[8] = ‘哈’ …

可以看出我們遍歷了一次玩家輸入的字符串，就找到了其中的敏感詞匯。

而在這一段標題的下面，我說 DFA 算法一開始構造的結構實際上算是一種森林，因為對于一個更完整的敏感詞庫而言，其構造出來的結構是這樣的：

如果不看該結構的根節點，即那個空白節點，那么就可以看作是由一個個樹結構組成的森林。

理解了 DFA 算法是如何匹配過濾詞的，接下來我們開始從代碼層面來探討如何根據敏感詞庫構造出這樣的森林結構。

DFA 算法 森林結構的構造

不論是樹，還是森林，都是由一個個節點構成的，因此我們來探討該結構中的節點應該存儲哪些信息。

按照正常的樹結構來說，節點結束存儲自身的值，和 與其連接的子節點的指針。

但對于 DFA 算法的結構，子節點的數量一開始我們是不確定的。所以，我們可以用一個 List 來存儲 所以子節點的指針，但是這樣子的話，我們在匹配時進行查找路徑就需要遍歷整個 List，這樣子效率是比較慢的。

為了達到 O(1) 的查找效率，我們可以使用哈希表來存儲子節點的指針。

我們還可以直接用 哈希表來作為森林的入口節點：

該哈希表中存放著 一系列 Key 為 不同的敏感詞開頭字符 Value 為 表示該字符的節點 的鍵值對

并且因為哈希表可以存放不同類型對象的特點(只要繼承自 object)，我們還可以存放可一個 Key 為 ‘IsEnd’ Value 為 0 的鍵值對。 Value 為 0 表示當前節點不為結構的末尾， Value 為 1 表示當前節點為結構的末尾。

那么對于結構中的其它節點，同樣可以用哈希表來構造。 對于該節點表示的字符，我們在其父節點中包含的鍵值對中已經存儲了(因為我們的結構最終有一個空白根節點，其里面的鍵值對，Key 存儲了敏感詞匯的開頭字符， Value 就又是一個哈希表 即其子節點)

并且每個節點，也就是哈希表，里面也存儲一個 Kye 為 “isEnd” Value 為 0/1 的鍵值對。 然后也存儲了一系列的 Key 為其子節點表示的字符， Value 為其子節點(哈希表) 的鍵值對。

我們再來舉個具體例子表述：

設有這樣的結構：

該結構最開始就是其空白根節點，即哈希表，我們設其為 map

那么，對于 “我愛你呀” 這個敏感詞，其查找過程就為：
map[‘我’][‘愛’][‘你’][‘呀’][‘IsEnd’] == 1

經過以上分析，我們就可以得出大概地代碼構造該結構的過程：

1、創建一個哈希表，作為該結構的空白根節點

2、遍歷敏感詞詞庫，得到一個敏感詞字符串

3、遍歷敏感詞字符串，得到一個當前遍歷字符

4、在樹結構中查找是否已經包含了當前遍歷字符，如果包含則直接走到樹結構中已經存在的這個節點，然后繼續向下遍歷字符。

查找過程為：

對于敏感詞的第一個字符串而言：

indexMap = map // 相當于指向樹結構節點的指針

if(indexMap.ContainsKey(‘c’)) indexMap = indexMap[‘c’]

這樣，我們的 indexMap 相當于一個指針，就指向了樹結構中已經存在了的相同節點

對于后面的字符也是同樣的：

if(indexMap.ContainsKye(‘c’)) indexMap = indexMap[‘c’]

如果樹結構中不存在，或者是當前指針指向的節點，其所有子節點都沒有表示當遍歷到的字符，則我們就需要創建一個子節點，即添加一個鍵值對，其 Key 為當前遍歷到的字符， Value 為新建一個哈希表。

5、判斷當前遍歷的字符，是否是當前字符串的最后一個。如果是 則添加鍵值對 Key 為 “IsEnd” Value 為 1。 如果不是，則添加鍵值對 Key 為 “IsEnd” Value 為 0。

對于 DFA 算法的結構構造論述到此完畢，接下來給出構造代碼java版本。

private Hashtable map;private void initFilter(List<String> words) {map = new Hashtable(words.size());for (int i = 0; i < words.size(); i++) {String word = words.get(i);Hashtable indexMap = map;for (int j = 0; j < word.length(); j++) {char c = word.toCharArray()[j];if (indexMap.containsKey(c)) {indexMap = (Hashtable)indexMap.get(c);} else {Hashtable newMap = new Hashtable();newMap.put("IsEnd", 0);indexMap.put(c, newMap);indexMap = newMap;}if (j == word.length() - 1) {if (indexMap.containsKey("IsEnd")){indexMap.put("IsEnd", 1);} else {indexMap.put("IsEnd", 1);}}}}System.out.println(map); // {我={IsEnd=0, 挺={IsEnd=0, 好={IsEnd=1}}}, 你={IsEnd=0, 好={IsEnd=0, 好={啊={IsEnd=1}, 呀={IsEnd=1}, IsEnd=0}}}}}private int CheckFilterWord(String txt, int beginIndex) {boolean flag = false;int len = 0;Hashtable curMap = map;for (int i = beginIndex; i < txt.length(); i++) {char c = txt.toCharArray()[i];Hashtable temp = (Hashtable)curMap.get(c);if (temp != null) {if ((int)temp.get("IsEnd") == 1) flag = true;else curMap = temp;len++;}else{break;}}if (!flag) len = 0;return len;}public String SerachFilterWordAndReplace(String txt) {int i = 0;StringBuilder sb = new StringBuilder(txt);while (i < txt.length()) {int len = CheckFilterWord(txt, i);if (len > 0) {for (int j = 0; j < len; j++) {sb.replace(i + j,i + j+1,"*");}i += len;} else{++i;}}return sb.toString();}@Testpublic void testSxt() {initFilter(Arrays.asList("你好好啊","你好好呀","我挺好"));String ret=SerachFilterWordAndReplace("是是你好好呀試試我挺好試試");System.out.println(ret);//是是****試試***試試}

總結

以上是生活随笔為你收集整理的DFA 敏感词过滤的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。