需求背景

大家有沒有做過屏蔽敏感詞的需求呢，這個需求一般來說很常見了。比如，系統(tǒng)中有一段話：

我愛吃肯德基

要求【肯德基】三個詞被屏蔽掉，屏蔽后的語句顯示為：

我愛吃***

常規(guī)的做法可能是查詢敏感詞庫中的敏感詞，循環(huán)每一個敏感詞，然后去輸入的文本中從頭到尾搜索一遍，看是否存在此敏感詞。

但是如果敏感詞很多，對于匹配也是很耗性能的。

這里介紹使用DFA算法匹配敏感詞，并進行處理。性能要優(yōu)于常規(guī)處理方法。

什么是DFA算法

在計算理論中，確定有限狀態(tài)自動機或確定有限自動機（英語：deterministic finite automaton, DFA）是一個能實現(xiàn)狀態(tài)轉(zhuǎn)移的自動機。對于一個給定的屬于該自動機的狀態(tài)和一個屬于該自動機字母表E的字符，它都能根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個狀態(tài)（這個狀態(tài)可以是先前那個狀態(tài)）。

——來自維基百科

這里的確定意思為：狀態(tài)以及引起狀態(tài)轉(zhuǎn)換的事件都是可確定的，不存在"意外"。有限指的是：狀態(tài)以及事件的數(shù)量都是可窮舉的。

DFA算法在匹配關(guān)鍵字上面有廣泛的應(yīng)用。

比如上面的關(guān)鍵詞【肯德基】，【肯尼瑪】。我們可以抽取成上面的樹狀模型。橢圓表示狀態(tài)，狀態(tài)與狀態(tài)之間的連線叫事件。

當(dāng)然這里只是簡單地介紹DFA是什么，想深入的童鞋可以看看這篇文章：

常用的DFA最小化算法？ - 知乎
-https://www.zhihu.com/question/39767421

里面介紹了如何將正常數(shù)據(jù)構(gòu)造成DFA形式。

JAVA代碼實戰(zhàn)

現(xiàn)在我們開始做一個示例吧

現(xiàn)在我們指定了敏感詞【"二愣子"，"二蛋"，"狗娃"】，我們按照上面的方式重新構(gòu)造數(shù)據(jù)結(jié)構(gòu)：

如上圖，我們構(gòu)造了3組數(shù)據(jù)，每個節(jié)點有一個狀態(tài)標(biāo)記，1代表節(jié)點結(jié)束，也就是敏感詞結(jié)束，0代表還未結(jié)束。

數(shù)據(jù)結(jié)構(gòu)Json形式如下：

接下來就是如何實現(xiàn)代碼了。

首先我們將敏感詞匯添加進入set集合中：

private Set<String> readSensitivewordFile() {
   Set<String> set = Sets.newHashSet();
   set.add("二愣子");
   set.add("二蛋");
   set.add("狗娃");
   return set;
}

當(dāng)然，實際情況需要從數(shù)據(jù)庫中讀取，或者從文件中讀取，然后再加載進入set集合。接下來我們將set中的數(shù)據(jù)重新構(gòu)造成上面Json格式的，Java這里需要使用Map來存儲。

我們創(chuàng)建一個sensitiveWordMap來存儲敏感詞，這里實際就是map套map的過程，我們來調(diào)試看看map的結(jié)構(gòu)：

上面的數(shù)據(jù)結(jié)構(gòu)Map是不是看暈了，其實就是我之前提到Json格式。

在系統(tǒng)初始化時就將敏感詞構(gòu)造好。

我們將敏感詞的結(jié)構(gòu)構(gòu)造好后，就開始匹配句子了。

如上代碼，我們需要將句子中的字符一個一個的循環(huán)，如果(Map) nowMap.get(word) != null，說明匹配到了敏感詞，這里如果isEnd的結(jié)束符為1，代表敏感詞結(jié)束，即匹配到了一個敏感詞。

我們還會遇到上圖的情況，【二蛋】是一個敏感詞，【蛋疼】也是一敏感詞。在【蛋】這個節(jié)點中，是【二蛋】的結(jié)束節(jié)點，是【蛋疼】的開始節(jié)點。我們通過代碼：

SensitiveWordFilter.minMatchTYpe == matchType

判斷，如果為true，我們在【蛋】結(jié)束之后就不再往下匹配，并將匹配到的index返回。之后再進入下一個循環(huán)了。反之。

上面我們拿到匹配到的敏感詞的index，接下來就要將句子中的敏感詞顯示出來了。

我們將其存入set集合中：

Set<String> sensitiveWordList = new HashSet<>();

這里大家發(fā)現(xiàn)一個問題沒有：

獲取敏感詞index循環(huán)了一次txt句子，獲取敏感詞字符又循環(huán)了一次，大家有沒有辦法減少一次循環(huán)呢

這個問題大家闊以思考一下。

然后我們將句子中的敏感詞替換成指定的字符。

比如我們將敏感詞替換成 "*"。

測試代碼

我們來測試下代碼

我們選取了《凡人修仙傳》中的一段句子：

"韓立被村里人叫作“二愣子”，可人并不是真愣真傻，反而是村中首屈一指的聰明孩子，但就像其他村中的孩子一樣，除了家里人外，他就很少聽到有人正式叫他名字“韓立”，倒是“二愣子”“二愣子”的稱呼一直伴隨至今。而之所以被人起了個“二愣子”的綽號，也只不過是因為村里已有一個叫“愣子”的孩子了。這也沒啥，村里的其他孩子也是“狗娃”“二蛋”之類的被人一直稱呼著，這些名字也不見得比“二愣子”好聽了哪里去。"

測試的結(jié)果為：