你應該知道的算法1-敏感詞過濾算法
=敏感詞過濾在各互聯網是比較常見的操作，也有很多算法來處理這個問題，個人看了些資料后覺得“字符串多模式精確匹配”（臟字/敏感詞匯搜索算法）——TTMP算法是一種比較實用的方法，每個做web的人都應該有所了解
在這片文章中對這個算法有較詳盡的解釋了，推薦大家去看原文：http://www.cnblogs.com/sumtec/archive/2008/02/01/1061742.html
下面是我從原文中摘抄的比較重要的內容：
關于多模匹配問題，有很多已有的算法，我沒有仔細的看，只看了一個可能是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算法，也還有不少可以挖掘潛力的地方，比如現在是前向檢索的，以及預先計算哈希值的。如果改成后向檢索，檢索時計算哈希值，性能應該會更好一點。不過暫時不打算繼續挖掘了，準備把他先放到實戰里面應用再說。