敏感詞、文字過濾是一個網(wǎng)站必不可少的功能，如何設(shè)計一個好的、高效的過濾算法是非常有必要的。前段時間我一個朋友（馬上畢業(yè)，接觸編程不久）要我?guī)退匆粋€文字過濾的東西，它說檢索效率非常慢。我把它程序拿過來一看，整個過程如下：讀取敏感詞庫、如果HashSet集合中，獲取頁面上傳文字，然后進(jìn)行匹配。我就想這個過程肯定是非常慢的。對于他這個沒有接觸的人來說我想也只能想到這個，更高級點就是正則表達(dá)式。但是非常遺憾，這兩種方法都是不可行的。當(dāng)然，在我意識里沒有我也沒有認(rèn)知到那個算法可以解決問題，但是Google知道！
DFA簡介
在實現(xiàn)文字過濾的算法中，DFA是唯一比較好的實現(xiàn)算法。DFA即Deterministic Finite Automaton，也就是確定有窮自動機(jī)，它是是通過event和當(dāng)前的state得到下一個state，即event+state=nextstate。下圖展示了其狀態(tài)的轉(zhuǎn)換
在這幅圖中大寫字母（S、U、V、Q）都是狀態(tài)，小寫字母a、b為動作。通過上圖我們可以看到如下關(guān)系
a b b
S -----> U S -----> V U -----> V
在實現(xiàn)敏感詞過濾的算法中，我們必須要減少運算，而DFA在DFA算法中幾乎沒有什么計算，有的只是狀態(tài)的轉(zhuǎn)換。
Java實現(xiàn)DFA算法實現(xiàn)敏感詞過濾
在Java中實現(xiàn)敏感詞過濾的關(guān)鍵就是DFA算法的實現(xiàn)。首先我們對上圖進(jìn)行剖析。在這過程中我們認(rèn)為下面這種結(jié)構(gòu)會更加清晰明了。
同時這里沒有狀態(tài)轉(zhuǎn)換，沒有動作，有的只是Query（查找）。我們可以認(rèn)為，通過S query U、V，通過U query V、P，通過V query U P。通過這樣的轉(zhuǎn)變我們可以將狀態(tài)的轉(zhuǎn)換轉(zhuǎn)變?yōu)槭褂肑ava集合的查找。
誠然，加入在我們的敏感詞庫中存在如下幾個敏感詞：日本人、日本鬼子、毛.澤.東。那么我需要構(gòu)建成一個什么樣的結(jié)構(gòu)呢？
首先：query 日 ---> {本}、query 本 --->{人、鬼子}、query 人 --->{null}、query 鬼 ---> {子}。形如下結(jié)構(gòu)：
下面我們在對這圖進(jìn)行擴(kuò)展：
這樣我們就將我們的敏感詞庫構(gòu)建成了一個類似與一顆一顆的樹，這樣我們判斷一個詞是否為敏感詞時就大大減少了檢索的匹配范圍。比如我們要判斷日本人，根據(jù)第一個字我們就可以確認(rèn)需要檢索的是那棵樹，然后再在這棵樹中進(jìn)行檢索。
但是如何來判斷一個敏感詞已經(jīng)結(jié)束了呢？利用標(biāo)識位來判斷。
所以對于這個關(guān)鍵是如何來構(gòu)建一棵棵這樣的敏感詞樹。下面我已Java中的HashMap為例來實現(xiàn)DFA算法。具體過程如下：
日本人，日本鬼子為例
1、在hashMap中查詢“日”看其是否在hashMap中存在，如果不存在，則證明已“日”開頭的敏感詞還不存在，則我們直接構(gòu)建這樣的一棵樹。跳至3。
2、如果在hashMap中查找到了，表明存在以“日”開頭的敏感詞，設(shè)置hashMap = hashMap.get("日")，跳至1，依次匹配“本”、“人”。
3、判斷該字是否為該詞中的最后一個字。若是表示敏感詞結(jié)束，設(shè)置標(biāo)志位isEnd = 1，否則設(shè)置標(biāo)志位isEnd = 0；
程序?qū)崿F(xiàn)如下：
/** * 讀取敏感詞庫，將敏感詞放入HashSet中，構(gòu)建一個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()); //初始化敏感詞容器，減少擴(kuò)容操作 String key = null; Map nowMap = null; Map<String, String> newWorMap = null; //迭代keyWordSet Iterator<String> iterator = keyWordSetiterator(); while(iteratorhasNext()){ key = iteratornext(); //關(guān)鍵字 nowMap = sensitiveWordMap; for(int i = 0 ; i < keylength() ; i++){ char keyChar = keycharAt(i); //轉(zhuǎn)換成char型 Object wordMap = nowMapget(keyChar); //獲取 if(wordMap != null){ //如果存在該key，直接賦值 nowMap = (Map) wordMap; } else{ //不存在則，則構(gòu)建一個map，同時將isEnd設(shè)置為0，因為他不是最后一個 newWorMap = new HashMap<String,String>(); newWorMapput("isEnd", "0"); //不是最后一個 nowMapput(keyChar, newWorMap); nowMap = newWorMap; } if(i == keylength() - 1){ nowMapput("isEnd", "1"); //最后一個 } } } } 運行得到的hashMap結(jié)構(gòu)如下：
{五={星={紅={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。
通過這個步驟我們可以判斷“中國人民”為敏感詞，但是如果我們輸入“中國女人”則不是敏感詞了。
/** * 檢查文字中是否包含敏感字符，檢查規(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; //敏感詞結(jié)束標(biāo)識位：用于敏感詞只有1位的情況 int matchFlag = 0; //匹配標(biāo)識數(shù)默認(rèn)為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++; //找到相應(yīng)key，匹配標(biāo)識+1 if("1"equals(nowMapget("isEnd"))){ //如果為最后一個匹配規(guī)則,結(jié)束循環(huán)，返回匹配標(biāo)識數(shù) flag = true; //結(jié)束標(biāo)志位為true if(SensitivewordFilterminMatchTYpe == matchType){ //最小規(guī)則，直接返回,最大規(guī)則還需繼續(xù)查找 break; } } } else{ //不存在，直接返回 break; } } if(matchFlag < 2 && !flag){ matchFlag = 0; } return matchFlag; } 在文章末尾我提供了利用Java實現(xiàn)敏感詞過濾的文件下載。下面是一個測試類來證明這個算法的效率和可靠性。
public static void main(String[] args) { SensitivewordFilter filter = new SensitivewordFilter(); Systemoutprintln("敏感詞的數(shù)量：" + filtersensitiveWordMapsize()); String string = "太多的傷感情懷也許只局限于飼養(yǎng)基地 熒幕中的情節(jié)，主人公嘗試著去用某種方式漸漸的很瀟灑地釋自殺指南懷那些自己經(jīng)歷的傷感。" + "然后法輪功 我們的扮演的角色就是跟隨著主人公的喜紅客聯(lián)盟 怒哀樂而過于牽強(qiáng)的把自己的情感也附加于銀幕情節(jié)中，然后感動就流淚，" + "難過就躺在某一個人的懷里盡情的闡述心扉或者手機(jī)卡復(fù)制器一個人一杯紅酒一部電影在夜三級片 深人靜的晚上，關(guān)上電話靜靜的發(fā)呆著。"; Systemoutprintln("待檢測語句字?jǐn)?shù)：" + stringlength()); long beginTime = SystemcurrentTimeMillis(); Set<String> set = filtergetSensitiveWord(string, 1); long endTime = SystemcurrentTimeMillis(); Systemoutprintln("語句中包含敏感詞的個數(shù)為：" + setsize() + "。包含：" + set); Systemoutprintln("總共消耗時間為：" + (endTime - beginTime)); } 運行結(jié)果：
從上面的結(jié)果可以看出，敏感詞庫有771個，檢測語句長度為184個字符，查出6個敏感詞。總共耗時1毫秒。可見速度還是非常可觀的。
下面提供兩個文檔下載：
Desktop.rar（http://xiazai.VeVB.COm/201611/yuanma/Desktop_jb51.rar）里面包含兩個Java文件，一個是讀取敏感詞庫（SensitiveWordInit），一個是敏感詞工具類（SensitivewordFilter），里面包含了判斷是否存在敏感詞（isContaintSensitiveWord(String txt,int matchType)）、獲取敏感詞（getSensitiveWord(String txt , int matchType)）、敏感詞替代（replaceSensitiveWord(String txt,int matchType,String replaceChar)）三個方法。
敏感詞庫：點擊下載
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點
疑難解答
圖片精選
