敏感詞、文字過濾是一個網(wǎng)站必不可少的功能，如何設計一個好的、高效的過濾算法是非常有必要的。前段時間我一個朋友（馬上畢業(yè)，接觸編程不久）要我?guī)退匆粋€文字過濾的東西，它說檢索效率非常慢。我把它程序拿過來一看，整個過程如下：讀取敏感詞庫、如果HashSet集合中，獲取頁面上傳文字，然后進行匹配。我就想這個過程肯定是非常慢的。對于他這個沒有接觸的人來說我想也只能想到這個，更高級點就是正則表達式。但是非常遺憾，這兩種方法都是不可行的。當然，在我意識里沒有我也沒有認知到那個算法可以解決問題，但是Google知道！
DFA簡介
在實現(xiàn)文字過濾的算法中，DFA是唯一比較好的實現(xiàn)算法。DFA即Deterministic Finite Automaton，也就是確定有窮自動機，它是是通過event和當前的state得到下一個state，即event+state=nextstate。下圖展示了其狀態(tài)的轉換
在這幅圖中大寫字母（S、U、V、Q）都是狀態(tài)，小寫字母a、b為動作。通過上圖我們可以看到如下關系
a b b
S -----> U S -----> V U -----> V
在實現(xiàn)敏感詞過濾的算法中，我們必須要減少運算，而DFA在DFA算法中幾乎沒有什么計算，有的只是狀態(tài)的轉換。
Java實現(xiàn)DFA算法實現(xiàn)敏感詞過濾
在Java中實現(xiàn)敏感詞過濾的關鍵就是DFA算法的實現(xiàn)。首先我們對上圖進行剖析。在這過程中我們認為下面這種結構會更加清晰明了。
同時這里沒有狀態(tài)轉換，沒有動作，有的只是Query（查找）。我們可以認為，通過S query U、V，通過U query V、P，通過V query U P。通過這樣的轉變我們可以將狀態(tài)的轉換轉變?yōu)槭褂肑ava集合的查找。
誠然，加入在我們的敏感詞庫中存在如下幾個敏感詞：日本人、日本鬼子、毛.澤.東。那么我需要構建成一個什么樣的結構呢？
首先：query 日 ---> {本}、query 本 --->{人、鬼子}、query 人 --->{null}、query 鬼 ---> {子}。形如下結構：
下面我們在對這圖進行擴展：
這樣我們就將我們的敏感詞庫構建成了一個類似與一顆一顆的樹，這樣我們判斷一個詞是否為敏感詞時就大大減少了檢索的匹配范圍。比如我們要判斷日本人，根據(jù)第一個字我們就可以確認需要檢索的是那棵樹，然后再在這棵樹中進行檢索。
但是如何來判斷一個敏感詞已經(jīng)結束了呢？利用標識位來判斷。
所以對于這個關鍵是如何來構建一棵棵這樣的敏感詞樹。下面我已Java中的HashMap為例來實現(xiàn)DFA算法。具體過程如下：
日本人，日本鬼子為例
1、在hashMap中查詢“日”看其是否在hashMap中存在，如果不存在，則證明已“日”開頭的敏感詞還不存在，則我們直接構建這樣的一棵樹。跳至3。
2、如果在hashMap中查找到了，表明存在以“日”開頭的敏感詞，設置hashMap = hashMap.get("日")，跳至1，依次匹配“本”、“人”。
3、判斷該字是否為該詞中的最后一個字。若是表示敏感詞結束，設置標志位isEnd = 1，否則設置標志位isEnd = 0；
程序實現(xiàn)如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
/** * 讀取敏感詞庫，將敏感詞放入HashSet中，構建一個DFA算法模型：<br> * 中 = { * isEnd = 0 * 國 = {<br> * isEnd = 1 * 人 = {isEnd = 0 * 民 = {isEnd = 1} * } * 男 = { * isEnd = 0 * 人 = { * isEnd = 1 * } * } [ 0-9] * } * } * 五 = { * isEnd = 0 * 星 = { * isEnd = 0 * 紅 = { * isEnd = 0 * 旗 = { * isEnd = 1 * } * } * } * } * @author chenming * @date 2014年4月20日 下午3:04:20 * @param keyWordSet 敏感詞庫 * @version 0 */@SuppressWarnings({ "rawtypes", "unchecked" }) private void addSensitiveWordToHashMap(Set<String> keyWordSet) { sensitiveWordMap = new HashMap(keyWordSetsize()); //初始化敏感詞容器，減少擴容操作 String key = null; Map nowMap = null; Map<String, String> newWorMap = null; //迭代keyWordSet Iterator<String> iterator = keyWordSetiterator(); while(iteratorhasNext()){ key = iteratornext(); //關鍵字 nowMap = sensitiveWordMap; for(int i = 0 ; i < keylength() ; i++){ char keyChar = keycharAt(i); //轉換成char型 Object wordMap = nowMapget(keyChar); //獲取 if(wordMap != null){ //如果存在該key，直接賦值 nowMap = (Map) wordMap; } else{ //不存在則，則構建一個map，同時將isEnd設置為0，因為他不是最后一個 newWorMap = new HashMap<String,String>(); newWorMapput("isEnd", "0"); //不是最后一個 nowMapput(keyChar, newWorMap); nowMap = newWorMap; } if(i == keylength() - 1){ nowMapput("isEnd", "1"); //最后一個 } } } } |
運行得到的hashMap結構如下：
{五={星={紅={isEnd=0, 旗={isEnd=1}}, isEnd=0}, isEnd=0}, 中={isEnd=0, 國={isEnd=0, 人={isEnd=1}, 男={isEnd=0, 人={isEnd=1}}}}}
敏感詞庫我們一個簡單的方法給實現(xiàn)了，那么如何實現(xiàn)檢索呢？檢索過程無非就是hashMap的get實現(xiàn)，找到就證明該詞為敏感詞，否則不為敏感詞。過程如下：假如我們匹配“中國人民萬歲”。
1、第一個字“中”，我們在hashMap中可以找到。得到一個新的map = hashMap.get("")。
2、如果map == null，則不是敏感詞。否則跳至3
3、獲取map中的isEnd，通過isEnd是否等于1來判斷該詞是否為最后一個。如果isEnd == 1表示該詞為敏感詞，否則跳至1。
通過這個步驟我們可以判斷“中國人民”為敏感詞，但是如果我們輸入“中國女人”則不是敏感詞了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
/** * 檢查文字中是否包含敏感字符，檢查規(guī)則如下：<br> * @author chenming * @date 2014年4月20日 下午4:31:03 * @param txt * @param beginIndex * @param matchType * @return，如果存在，則返回敏感詞字符的長度，不存在返回0 * @version 0 */ @SuppressWarnings({ "rawtypes"}) public int CheckSensitiveWord(String txt,int beginIndex,int matchType){ boolean flag = false; //敏感詞結束標識位：用于敏感詞只有1位的情況 int matchFlag = 0; //匹配標識數(shù)默認為0 char word = 0; Map nowMap = sensitiveWordMap; for(int i = beginIndex; i < txtlength() ; i++){ word = txtcharAt(i); nowMap = (Map) nowMapget(word); //獲取指定key if(nowMap != null){ //存在，則判斷是否為最后一個 matchFlag++; //找到相應key，匹配標識+1 if("1"equals(nowMapget("isEnd"))){ //如果為最后一個匹配規(guī)則,結束循環(huán)，返回匹配標識數(shù) flag = true; //結束標志位為true if(SensitivewordFilterminMatchTYpe == matchType){ //最小規(guī)則，直接返回,最大規(guī)則還需繼續(xù)查找 break; } } } else{ //不存在，直接返回 break; } } if(matchFlag < 2 && !flag){ matchFlag = 0; } return matchFlag; } |
在文章末尾我提供了利用Java實現(xiàn)敏感詞過濾的文件下載。下面是一個測試類來證明這個算法的效率和可靠性。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static void main(String[] args) { SensitivewordFilter filter = new SensitivewordFilter(); Systemoutprintln("敏感詞的數(shù)量：" + filtersensitiveWordMapsize()); String string = "太多的傷感情懷也許只局限于飼養(yǎng)基地 熒幕中的情節(jié)，主人公嘗試著去用某種方式漸漸的很瀟灑地釋自殺指南懷那些自己經(jīng)歷的傷感。" + "然后法輪功 我們的扮演的角色就是跟隨著主人公的喜紅客聯(lián)盟 怒哀樂而過于牽強的把自己的情感也附加于銀幕情節(jié)中，然后感動就流淚，" + "難過就躺在某一個人的懷里盡情的闡述心扉或者手機卡復制器一個人一杯紅酒一部電影在夜三級片 深人靜的晚上，關上電話靜靜的發(fā)呆著。"; Systemoutprintln("待檢測語句字數(shù)：" + stringlength()); long beginTime = SystemcurrentTimeMillis(); Set<String> set = filtergetSensitiveWord(string, 1); long endTime = SystemcurrentTimeMillis(); Systemoutprintln("語句中包含敏感詞的個數(shù)為：" + setsize() + "。包含：" + set); Systemoutprintln("總共消耗時間為：" + (endTime - beginTime)); } |
運行結果：
從上面的結果可以看出，敏感詞庫有771個，檢測語句長度為184個字符，查出6個敏感詞。總共耗時1毫秒。可見速度還是非常可觀的。
下面提供兩個文檔下載：
Desktop.rar（Desktop.rar）里面包含兩個Java文件，一個是讀取敏感詞庫（SensitiveWordInit），一個是敏感詞工具類（SensitivewordFilter），里面包含了判斷是否存在敏感詞（isContaintSensitiveWord(String txt,int matchType)）、獲取敏感詞（getSensitiveWord(String txt , int matchType)）、敏感詞替代（replaceSensitiveWord(String txt,int matchType,String replaceChar)）三個方法。
敏感詞庫：點擊下載
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/chenssy/article/details/26961957
