什么是TTMP算法？不好意思，我發布這篇文章之前，估摸是沒有其他地方能找著該算法的，因為那是俺生造的。?
TTMP是啥意思呢？是Terminator Triggered Multi-Pattern 的意思，也就是結束符觸發多模式算法。?
-_-! 有點難理解，沒關系，看完了也許就理解了。?

不過這個自造的算法有點復雜，為了保證大家能夠順利閱讀，請大家配合做一個測試：?
拿出你的手表，或者其他計時器，看看你能用多塊的時間閱讀完下面這篇文章。?
判斷標準如下：?
如果你的時間少于15秒，就可以不用讀我的文章了，完全有能力造一個更強的算法；?
如果你的時間少于30秒，我們可以溝通交流一下；?
如果你的時間少于45秒，你可以仔細閱讀一下，說不定可能也許有點啟發作用；?
如果你的時間少于60秒，你一定能夠在這里挖到寶礦；?
如果你不屬于上述情況，我建議您啊，還是不要費力氣閱讀了，有點面為其難了。?

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)]?

轉載于:https://www.cnblogs.com/chenwenbiao/archive/2012/06/10/2544212.html

總結

以上是生活随笔為你收集整理的字符串多模式精确匹配（脏字/敏感词汇搜索算法）——TTMP算法 之理论（转）...的全部內容，希望文章能夠幫你解決所遇到的問題。

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