文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

1 敏感詞過濾場景

在很多支持用戶發表內容的網站，都有敏感詞過濾替換的功能。例如將一些淫穢、反動內容過濾掉，或者替換為****。在一些社交類網站為了避免做廣告之嫌，會把手機號替換為*****。當然有些人為了躲避被替換會寫一三七一零六捌這樣的手機號。這是后話了。這篇文章我們先學習如何替換字符串類的敏感詞。我們可以維護一個敏感詞詞典，當用戶輸入評論之后，通過字符串匹配算法，查找是否包含敏感詞。如果有，需要找到起始位置和長度，替換為***。
　　前面講的幾種字符串匹配算法：BF、RK、BM、KMP、Trie樹都可以實現，但是效率不夠高。我們使用多模式串匹配算法來提高效率。

2 基于單模式串和Trie樹實現敏感詞過濾

BF、RK、BM、KMP都是單模式串匹配算法，是在一個模式串和一個主串之間進行匹配。多模式串匹配是多個模式串和一個主串進行匹配。為了解決敏感詞過濾問題，用單模式串匹配來做的話，每次匹配一個模式串和主串，匹配多次，也可以實現，只是這樣多次掃描主串效率會低。

多模式串匹配算法掃描一次主串實現匹配，這樣的效率就很高了。我們可以對敏感詞做預處理，構建一棵Trie樹。用戶輸入內容后，把用戶輸入的內容作為主串，從第一個字符C開始匹配。當匹配 到Trie樹的葉子節點或者中途有不匹配的字符的時候，我們將主串的開始位置偏移一位，也就是C字符的下一位，重新在Trie樹中匹配。

基于Trie樹的這種匹配方式很像單模式匹配的BF算法。我們知道KMP對BF算法的改進就是引入了next數組。當匹配失敗的時候，主串位置不動，模式串位置移動。基于這種思路，我們優化Trie樹查找的效率，這就是AC自動機算法。

3 AC自動機算法

AC自動機算法是一種經典的多模式串匹配算法，全稱是 Aho-Corasick 算法。AC=Trie樹+next數組。這里的next數組是基于樹的。

構建AC自動機包含兩個操作：1 構建Trie樹；2 在Trie樹上構建失效指針。

AC自動機每個節點的結構如下。

public class AcNode {public char data; public AcNode[] children = new AcNode[26]; // 字符集只包含 a~z 這 26 個字符public boolean isEndingChar = false; // 結尾字符為 truepublic int length = -1; // 當 isEndingChar=true 時，記錄模式串長度public AcNode fail; // 失敗指針public AcNode(char data) {this.data = data;} }

關于Trie樹的構建看上一篇文章。這里重點描述構建失效指針。

3.1 構建失效指針

假設這里有 4 個模式串，分別是 c，bc，bcd，abcd；主串是 abcd。

我們沿著Trie樹走到p節點（下圖中的紫色節點），那p的失效指針就是指從根節點到p節點形成的字符串abc，跟所有模式串前綴匹配的最長可匹配后綴子串，就是箭頭指向的bc子串。

　　

這里解釋一下最長可匹配后綴子串。abc的后綴子串有c、bc。我們拿它們與其他模式串的前綴子串去匹配。如果某個后綴子串和其他模式串的某個前綴子串可匹配，就成為可匹配后綴子串。

從可匹配后綴子串中找到最長的那個就是最長可匹配后綴子串。我們將p節點的失效指針指向那個最長可匹配后綴子串對應的前綴子串的最后一個位置。就是上圖中箭頭所指位置。

計算每個節點的失效指針看似復雜，是不是可以類似KMP，利用已經求得的、深度更小的節點的失效指針來推到呢。如果這樣的話，我們可以逐層解決，這就是樹的層次遍歷的過程。

根節點的失效指針指向自己。如果已知節點p的失效指針指向q，如何推到p的子節點pc的失效指針指向什么位置。

如果q有一個子節點的字符等于pc節點的字符，那么pc的失效指針指向該節點。

如果q的所有子節點的字符都不等于pc節點的字符，那么q=q.失效指針。再繼續判斷。

代碼如下。

public void buildFailurePointer() {Queue<AcNode> queue = new LinkedList<>();root.fail = null;queue.add(root);while (!queue.isEmpty()) {AcNode p = queue.remove();for (int i = 0; i < 26; ++i) {AcNode pc = p.children[i];if (pc == null) continue;if (p == root) {pc.fail = root;} else {AcNode q = p.fail;while (q != null) {AcNode qc = q.children[pc.data - 'a'];if (qc != null) {pc.fail = qc;break;}q = q.fail;}if (q == null) {pc.fail = root;}}queue.add(pc);}}}

最終,通過按層級計算每個節點的失效指針，最后構建完成的AC自動機如下圖。

3.2 在AC自動機上匹配主串

如何在AC自動機上匹配主串呢？例如主串是a，從i=0開始，AC自動機從p=root開始。

如果p指向的子節點x的字符串等于a[i]，則把p=x。這個時候我們判斷一下以目前匹配的字符串來說，有哪些是匹配到的字符串（這也是失效指針的含義）。實現方式就是檢測p.失效指針是否是一個模式串的結尾。如果是可以得到匹配的字符串的長度和結尾位置。繼續檢測p.失效指針.失效指針。結合代碼看最好理解。處理完成i++。

如果p指向的子節點的字符串都不等于a[i]。則p=p.失效指針。

public void match(char[] text) { // text 是主串int n = text.length;AcNode p = root;for (int i = 0; i < n; ++i) {int idx = text[i] - 'a';while (p.children[idx] == null && p != root) {p = p.fail; // 失敗指針發揮作用的地方}p = p.children[idx];if (p == null) p = root; // 如果沒有匹配的，從 root 開始重新匹配AcNode tmp = p;//字符串已經匹配了一部分了，模式串中就到tmp節點。那就判斷tmp是不是個字符串，如果是，那就是匹配到了。如果tmp不是個字符串，那已經匹配的這部分如果在下一位發生不匹配的時候，指針應該回退到tmp.fail。那繼續看tmp.fail是不是個字符串。//如果是，那就是說已經匹配的部分包含某個字符串。while (tmp != root) { // 打印出可以匹配的模式串if (tmp.isEndingChar == true) {int pos = i-tmp.length+1;System.out.println(" 匹配起始下標 " + pos + "; 長度 " + tmp.length);}tmp = tmp.fail;}}}

3.3 AC自動機的時間復雜度

Trie 樹構建的時間復雜度是 O(m*len)，其中 len 表示敏感詞的平均長度，m 表示敏感詞的個數。

構建失效指針的時間復雜度。這里給一個不太精確的上界。假設 Trie 樹中總的節點個數是 k，每個節點構建失效指針的時候，（你可以看下代碼）最耗時的環節是 while 循環中的 q=q->fail，每運行一次這個語句，q 指向節點的深度都會減少 1，而樹的高度最高也不會超過 len，所以每個節點構建失敗指針的時間復雜度是 O(len)。整個失敗指針的構建過程就是 O(k*len)。

在AC自動機上查詢的時間復雜度。與構建失效指針的分析類似。最外層for循環的長度是主串的長度。循環內部耗時的操作是兩個while循環，每個while循環的次數最多是len。所以時間復雜度不超過O(n*len)。一般來講敏感詞的長度不會很長，近似O(n)，近似主串的長度。

從時間復雜度來講，AC自動機和Trie樹的查找性能是一樣的。實際上，因為失效指針大部分指向root節點，所以絕大多數情況下，AC自動機做匹配的效率要遠遠高于給出的估算。只有在極端情況下才會退化為何Trie樹一樣的效率。

總結

以上是生活随笔為你收集整理的AC自动机：多模式串匹配实现敏感词过滤的全部內容，希望文章能夠幫你解決所遇到的問題。

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