字元串多模式精确比對

原文位址：http://www.cnblogs.com/sumtec/archive/2008/02/01/1061742.html

Do you raelly know Engilsh?

At laest in Egnlish, wehn pepole raed, tehy 

usaully wlil not noitce taht the charcatres bewteen

the frist ltteer and the lsat leettr are not in a

corrcet oredr. In fcat, hmuan brian does recongize

wrods by seeknig the fsirt ltteer and the lsat leettr,

and tehn fnidnig whcih charatcers are insdie of tehm.

See! All the wrods hree wtih mroe tahn 3 leettrs are

all wirtten in a worng way! Do you niotice taht?

确實，如果按照自動機理論，一個字一個字的去認真閱讀，那麼也還是很有可能能夠理順文法結構，搞清楚一句話的含義的（理論上如此吧，實際上還沒有任何一個機器能做到真人般的感覺能力）。但是如果每個字都認真讀，并查找文法表，一來速度會慢，二來需要海量的空間去做這個事情。而人腦比較聰明，經過若幹年的鍛煉之後，已經自動的學會了放棄細節，比如讀"cerroct"這個詞的時候，找到前面是c開頭，後面是t結尾，中間有eoc各一個，r兩個，一查表就知道肯定是“正确”這個詞而不管他正确與否——哦，不好意思，我又寫錯了，應該是correct！

嗯？這個跟我們這次的主題——字元串多模式精确比對，有什麼關系呢？

有啊！當然有啦。不過在我告訴大家這個關系之前，我們先來分析一下，字元串多模式精确比對的效率問題是什麼？寫之前我先給大家說一下，我下面的說明也許不會很嚴謹，因為有時候太嚴謹了，就不好了解了。例如什麼令X=Y……反正我最近為了這個事情找的一些資料，盡是這個，看着也覺得頭暈。

所謂字元串多模式精确比對是啥意思呢？字元串不多說了，實際上能用于搜尋字元串的，也能搜尋其他東西。多模式嘛：比如

string s="xxx"; 

string t="xx";

s.IndexOf(t)；

這個是在一個字元串s中，找出另外一個字元串t所在的位置（或者說是否存在），這種叫做單模式，隻有一個要被尋找的字元串t——唯一的一個搜尋模式；如果說是

string s="xxx";

string[] t= new string[]{"x1", "x2", "x3"...};

s.Scan(t);

這種呢，就叫做多模式比對了。因為我要在s裡面找出一組t中任意一個所在的位置，或者說是看看我們的文章裡面是否有髒字表裡面的敏感詞彙。

關于多模比對問題，有很多已有的算法，我沒有仔細的看，隻看了一個可能是WM的算法，實際上可能還有什麼grep/agrep等算法。不過需要提醒大家的是，還有不少的算法是讨論模糊比對的，比如說容許其中有一個字不正确，那些算法就不是我這個主題要讨論的内容了。我要讨論的是精确搜尋，即要找“地瓜”就找“地瓜”，不要“地鼠”。

多模式精确比對很難嗎？不難，很簡單：我們隻需要循環一下，先找s.IndexOf(t1)，再找s.IndexOf(t2)……但是如果你果然這麼做，效率就會很低了，因為你會需要掃描文本很多很多遍。可以想象，我們的目标是隻要掃描整個文章一遍就能夠找出這個文章裡面都有哪些敏感詞彙。不過，很明顯該目标并不容易達成，但至少我們可以盡量接近“隻掃描一次”這個目标。在進一步分析之前，建議先看另外一篇文章：

(重發).NET髒字過濾算法 

這篇文章的算法（比如叫做XDMP算法）其掃描速度已經是比較快的了，并且其思路也比較好了解，我們在這個文章的基礎上進行讨論會比較有意義。首先我們先整理一下這個算法的思路：

1、首先掃描文章裡面的每一個字元，隻有當某一個字元是髒字表中任意一個髒詞的第一個字元（稱為“起始符”），我們才試圖看看接下來是否是髒字（觸發檢索）。

2、但是我們也不是毫無頭緒的就開始循環髒字表的每一個詞條：

2.1、我們往後檢索一個字元，先看一下這個字元是否是髒字表裡面的任意一個字元，如果不是，就表明不可能是髒字表中的任何一個條目，就可以退出了。

2.2、如果是，我們就取從第一個被檢出字元到目前掃描到的字元之間的字元串，求哈希值，看看能否從哈希表中檢出一個髒詞。

如果檢出了，那就大功告成，否則繼續檢索後面一個字元（重複2.1、2.2），直至找不到，或者超出髒字表條目最大的長度。

2.3、如果都找不到，或者超長，那麼接下來就回到剛才的那個“起始符”後一個字元繼續掃描（重複1、2），直至整個文章結束。

我這裡先引入了三個重要概念：

1、掃描，指掃描文章，看看是否有需要和髒字表開始進行對比的情況；

2、檢索，指已經發現可能存在情況了，在将文本和髒字表進行對比的過程；

3、起始符，指髒字表中條目中的第一個字元。

如果我們隻要掃描，不需要檢索就可以完成任務，那一定是最快的，不過目前我比較孤陋寡聞，沒有找到這樣的算法。

又或者，如果我們掃描一遍，而檢索全中，那也很不錯，很不幸，還是沒見過。

很明顯，掃描不應該多于1遍，否則肯定效率不可能高。那麼檢索就是算法的關鍵了！拆開來，提高檢索品質有下列幾個方式：

1、盡可能不觸發檢索；

2、如果确實需要觸發檢索了，那麼每次觸發檢索的時候，要盡可能減少檢索所需要周遊的字元數量；

3、每次對比髒字表的時候，減少運算量。

回過頭分析上面的XDMP算法，是：

1、一次掃描；（很好，沒啥好說的）

2、隻要發現“起始符”就觸發檢索；

3、檢索的時候，需要周遊的字元數是 1+2+3+...+n，這裡的n是被命中的髒詞的長度，或者最接近的長度；

4、每次檢索，需要重複計算HashCode，不要忘了，計算HashCode，也是需要掃描字元串的，也就是又要周遊1+2+3+..+n個字元。

于是，我就有了一下問題：

1、難道每次遇到“起始符”了，就一定要觸發檢索嗎？哎呀媽呀，這個也要檢索（因為髒字表裡面可能有MB）？！

2、難道每次觸發檢索，都非得要檢索長度為1的，長度為2的，長度為3的……直到檢索成功，或者出現非髒字表字元的時候嗎？

3、難道每次檢索，我們都需要把特定長度的待檢文本截取出來嗎？

4、難道每次檢索，都需要從頭開始計算哈希值嗎？不能利用同一次觸發檢索後，上一次檢索的哈希值，來減少本次計算的不必要運算量嗎？

這四個問題，基本上是我想要解決的問題。其中前兩個是一類問題，後兩個是另一類問題。首先我們檢查第一類問題：

好，我們回顧一下最開始的那篇英文，我們是否有點什麼啟發？對！我們觸發檢索的條件太簡單了！

如果一個單詞我們都沒有看完呢，為什麼要開始想這個事一個什麼詞呢？

另外，我們觸發檢索之後，也作了很多不必要的檢索，因為當我們遇到"cao"這個字元的時候，很可能髒字表裡面隻有"caoT媽"，"caoN媽"這兩種情況。如果有文章裡面是"操作"，髒字表裡面正好又有"作LOVE"，上述XDMP算法還是會乖乖的搜尋兩個字元的情況，而實際上又是沒有必要的。

那麼我們如何減少這些不必要的運算呢？首先，我們改一下，不要每次遇到“起始符”就觸發檢索。我們掃描到起始符怎麼辦？記錄下來他的位置等資訊，然後繼續掃描下去。當我們遇到了“結束符”，也就是髒字表每一個詞條中，最後一個字元中的任意一個時，我們才考慮是否要開始觸發掃描。而掃描的時候呢，也不一定非得要髒字長度為1、2、3……的情況。因為之前記錄了各種起始位置，我們可能隻需要掃描1、3兩種情況，或者5這種情況。

接下來是第二類問題：

上述算法裡面，為了加快檢索某串字元是否在髒字表裡面，使用了哈希表。為了能夠查表，是以就必須把這個哈希值給截取出來。可是這就引發了兩個性能損耗點：

1、每一次截取，都要重新計算哈細值；

2、每一次都需要截取出一個字元串。

要避免這個問題，首先我們需要了解哈希表大緻是怎麼工作的：

哈希表實際上是根據目前的字元串内容，得出一個機率相對比較平均的散列值（這樣哈希效表才不會容易出現沖突，即内容不同數值卻一樣），然後找出表中哈希值相等的第一個結果，然後對内容進行比較，如果相同就是找到了。否則就找下一個，直到沒有相等哈希值的條目為止。

于是，我們可以這麼來解決上述問題：

1、首先，我們造一個哈希值的計算方法，使得我們可以利用上一次的計算結果，接着計算下一個結果。

比如說，我們可以一個位元組一個位元組的進行異或（好處是方向性不敏感），或者也可以規定從字元串後方往前開始計算。

為什麼規定從尾部進行計算？因為TTMP是結束符觸發掃描的，比如說有文本：

ABCDE

如果E是結束符，那麼就會檢索ABCDE、BCDE、CDE、DE、E（還要看是否掃描到這些起始符）。如果我們是從後方往前計算，那就可以利用E的哈希值以及字元D，就可以計算DE的哈希值，而不需要再次對E字元進行計算了。

2、其次，我們可以構造這樣的哈希表：

Dictionary<int, List<string>> hash;

其key就是我們剛才算出來的哈希值，根據算出來的哈希值，我們就可以得到一個該哈希值下的髒字清單，然後我們一個個的和待檢文本進行字元對字元的比較。這裡看起來很奇怪，為什麼有了哈希值，還不能夠通過哈希值直接找到對應的字元呢？

不要忘了，哈希值本來就是會沖突的，我現在隻不過把沖突的情況單獨取出來自行處理，這樣實際上的檢索次數并沒有增加（放在哈希表裡面，也必須一個個的進行字元對字元的比較，才能夠确定Key值是否完全相等，而不是Key的哈希值相等但Key值不等）。而好處是，我們不需要非得取出一個字元串，好讓哈希表去擷取這個字元串的哈希值（需要從頭周遊每一個字元）。

通過以上的措施，我們就可以讓每一次對n長度待檢文本觸發檢索，隻需要最多周遊n個字元，就可以得到最多n次周遊的所有哈希值了，而原XDMP算法則需要周遊Sum(n)個字元。

當然了，上述這幾個措施，其效果并不會非常明顯，原因有三個：

1、通常我們的文本都是很正常的文本，頂多偶爾有點敏感詞彙，是以并不會經常挑戰前面說到的性能損耗點；

2、通常我們的髒字表數量不會極其巨大，起始符和結束符也應該集中在有限的那些字元裡面，是以絕大多數時候首字元表，以及結束符表就已經能夠極大地提高性能了；

3、即使我們真的需要觸發檢索了，我們的髒字通常長度會比較短，或者大多數會比較短，是以上面的改進所帶來的性能提升會比較有限。比如說兩個字元的情況下，原算法計算哈希值需要周遊3個字元，而TTMP則隻需要周遊2個字元……汗

而如果是5個字元，原算法需要周遊15個字元，而TTMP則隻需要周遊5個字元，開始有差距感了。

可惜的是，5個字元的敏感詞畢竟還是比較少的，而一篇文章正好中這個5字敏感詞的地方也是很少的。

目前我這個TTMP算法還沒有優化，已經能夠做到和XDMP算法消耗時間比為1：1.5-2.5，算是很不錯了。當然了XingD後來又做了一個新的算法，測試速度很快，可是當時我測的時候還不穩定，有漏檢的情況，是以暫時不做評論了。

至于我的TTMP算法，也還有不少可以挖掘潛力的地方，比如現在是前向檢索的，以及預先計算哈希值的。如果改成後向檢索，檢索時計算哈希值，性能應該會更好一點。不過暫時不打算繼續挖掘了，準備把他先放到實戰裡面應用再說。

呃，其實本文開頭說的還是沒錯的，本文還是有點難度，而本人描述能力也不是特别好，不知道各位看官有沒有看懂了？

源碼？嘿嘿，私貨，先收藏一段時間再說。當然了，如果你有一段源碼，能夠合法制造讓制造者合法擁有的人民币真币，能夠用VS2005編譯通過，部署過程隻需要點一下滑鼠，運作過程無需看管，并且你願意和我交換的話，我會考慮一下的……真實的情況是，我現在還要繼續讓算法更穩定，不能放出一個問題多多的代碼出來吧？

私下說一下，這個程式比XDMS算法複雜不少，如果将來放出來，并且各位想要整明白的話，還需要自己花點心思。

哦，順預先給某人回複一下：

KMP算法是單模比對算法，BM據說也是單模式的算法。

WM算法是多模比對的，我找了一個據說是WM的算法看了看：

http://blog.chinaunix.net/u/21158/showart_228430.html

不知道你說的是不是這個。

我發現思路其實和KMP/BM類似，主要是通過“跳躍”技術來提升性能的。但是該文裡面也提到了這麼一段話：

假設其中一個模式非常的短，長度僅為2，那我們移動的距離就不可能超過2，是以短模式會使算法的效率降低。

可問題就在于，一般髒字表的長度都是1到2個的居多，是以絕大多數跳躍的作用并不強。即使是5個字元，再TTMP裡面，也很可能因為超出長度沒有遇到“結束符”而不會觸發掃描。而WM需要有一個Shift表，為了節省空間還需要壓縮，這就意味着需要對每一個掃描單元進行一個壓縮計算。綜上所述，TTMP和WM進行搜尋髒字任務的PK，誰勝誰負還不一定呢。順便說一下，即使是WM，也不是一次掃描的，因為如果不跳躍的話，就會要多掃描一下某些字元。

TTMP效率描述：

Ot = Ot(文本長度) + Ot[ 起始符與結束符在出現在掃描視窗中的次數*Avg(同一個結束符中哈希值相等的詞條數目) ]

=Ot(N) + Ot[f*Avg(h)]

Om = Om(字元類型表) + Om(結束符表) + Om{ 詞條總數*[哈希表内部變量消耗記憶體+清單消耗記憶體數量+Avg(詞條長度) ] }

=256K + 256K + Om{n * [12+12+Avg(k) ] }

=512K + Om[n*(c+k)]