36|AC自動機:如何用多模式串匹配實現(xiàn)敏感詞過濾功能?
很多支持用戶發(fā)表文本內(nèi)容的網(wǎng)站，比如BBS，大都會有敏感詞過濾功能，用來過濾掉用戶輸入的 一些淫穢、反動、謾罵等內(nèi)容。你有沒有想過，這個功能是怎么實現(xiàn)的呢? 實際上，這些功能最基本的原理就是字符串匹配算法，也就是通過維護一個敏感詞的字典，當(dāng)用戶 輸入一段文字內(nèi)容之后，通過字符串匹配算法，來查找用戶輸入的這段文字，是否包含敏感詞。如 果有，就用“***”把它替代掉。 我們前面講過好幾種字符串匹配算法了，它們都可以處理這個問題。但是，對于訪問量巨大的網(wǎng)站 來說，比如淘寶，用戶每天的評論數(shù)有幾億、甚至幾十億。這時候，我們對敏感詞過濾系統(tǒng)的性能 要求就要很高。畢竟，我們也不想，用戶輸入內(nèi)容之后，要等幾秒才能發(fā)送出去吧?我們也不想， 為了這個功能耗費過多的機器吧?那如何才能實現(xiàn)一個高性能的敏感詞過濾系統(tǒng)呢?這就要用到今 天的多模式串匹配算法。
基于單模式串和Trie樹實現(xiàn)的敏感詞過濾
假設(shè)我們沿Trie樹走到p節(jié)點，也就是下圖中的紫色節(jié)點，那p的失敗指針就是從root走到紫色節(jié)點 形成的字符串a(chǎn)bc，跟所有模式串前綴匹配的最?可匹配后綴子串，就是箭頭指的bc模式串。 這里的最?可匹配后綴子串，我稍微解釋一下。字符串a(chǎn)bc的后綴子串有兩個bc，c，我們拿它們與 其他模式串匹配，如果某個后綴子串可以匹配某個模式串的前綴，那我們就把這個后綴子串叫作 可匹配后綴子串。
課后思考
到此為止，字符串匹配算法我們?nèi)贾v完了，你能試著分析總結(jié)一下，各個字符串匹配算法的特點和比較適合的應(yīng)用場景嗎？
一、單模式串匹配：
- BF： 簡單場景，主串和模式串都不太長, O(m*n)
- RK：字符集范圍不要太大且模式串不要太長， 否則hash值可能沖突，O(n)
- naive-BM：模式串最好不要太長（因為預(yù)處理較重），比如IDE編輯器里的查找場景； 預(yù)處理O(m*m), 匹配O(n)， 實現(xiàn)較復(fù)雜，需要較多額外空間.
- KMP：適合所有場景，整體實現(xiàn)起來也比BM簡單，O(n+m)，僅需一個next數(shù)組的O(m)額外空間；但統(tǒng)計意義下似乎BM更快，原因不明.
- 另外查資料的時候還看到一種比BM/KMP更快，且實現(xiàn)+理解起來都更容易的的Sunday算法，有興趣的可以看這里:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
http://www.itdecent.cn/p/2e6eb7386cd3
二、多模式串匹配：
- naive-Trie: 適合多模式串公共前綴較多的匹配(O(n*k)) 或者 根據(jù)公共前綴進行查找(O(k))的場景，比如搜索框的自動補全提示.
- AC自動機: 適合大量文本中多模式串的精確匹配查找, 可以到O(n).
