多模式匹配

　　多模式匹配就是有多個模式串P1,P2,P3…，Pm，求出所有這些模式串在連續文本T1….n中的所有可能出現的位置。
　　例如：求出模式集合{“nihao”,”hao”,”hs”,”hsr”}在給定文本”sdmfhsgnshejfgnihaofhsrnihao”中所有可能出現的位置。

AC 自動機算法

在計算機科學中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 發明的字符串搜索算法，[1]用于在輸入的一串字符串中匹配有限組“字典”中的子串。它與普通字符串匹配的不同點在于同時與所有字典串進行匹配。算法均攤情況下具有近似于線性的時間復雜度，約為字符串的長度加所有匹配的數量。然而由于需要找到所有匹配數，如果每個子串互相匹配（如字典為a，aa，aaa，aaaa，輸入的字符串為aaaa），算法的時間復雜度會近似于匹配的二次函數。

該算法主要依靠構造一個有限狀態機（類似于在一個trie樹中添加失配指針）來實現。這些額外的失配指針允許在查找字符串失敗時進行回退（例如設Trie樹的單詞cat匹配失敗，但是在Trie樹中存在另一個單詞cart，失配指針就會指向前綴ca），轉向某前綴的其他分支，免于重復匹配前綴，提高算法效率。
當一個字典串集合是已知的(例如一個計算機病毒庫), 就可以以離線方式先將自動機求出并儲存以供日后使用，在這種情況下，算法的時間復雜度為輸入字符串長度和匹配數量之和。
UNIX系統中的一個命令fgrep就是以AC自動機算法作為基礎實現的。

具體實現

在ac自動機算法中，以下3步尤為重要：

1. 構造前綴樹
2. 設置每個節點的失配跳轉并收集每個節點的所有匹配模式串
3. 對目標字符串進行搜索匹配

這里我們考慮模式集合P={“he”,”she”,”his”,”hers”}

步驟1：構造前綴數組

其中的數字和字母分別表示狀態和條件。

步驟2：設置每個節點的失配跳轉

h,s這個條件的失敗轉移值為0，也就是fail(1)=0, fail(3)=0也就是如果查找一個字符串從最開始查，即不是s,h就直接跳轉到0節點
在深度為2的情況下，有2，6，4三個節點:
計算fail（2），也就是求he的失敗轉移狀態，由于父節點1的失敗轉移狀態0,0下面也沒有e的條件可以跳轉，所以fail(2)=0
計算fail（6），也就是求hi的失敗轉移狀態，由于父節點1的失敗轉移狀態0,0下面也沒有i的條件可以跳轉，所以fail(6)=0
計算fail（4），也就是求sh的失敗轉移狀態，由于父節點3的失敗轉移狀態0,0下面有h的條件可以跳轉到狀態1，所以fail(3)=1

在深度為3的情況下，有8,7,5三個節點:
計算fail（8），也就是求her的失敗轉移狀態，由于父節點2的失敗轉移狀態0,0下面也沒有r的條件可以跳轉，所以fail(8)=0
計算fail（7），也就是求his的失敗轉移狀態，由于父節點6的失敗轉移狀態0,0下面有s的條件可以跳轉到狀態3，所以fail(7)=3
計算fail（5），也就是求she的失敗轉移狀態，由于父節點4的失敗轉移狀態1,1下面有e的條件可以跳轉到狀態2，所以fail(5)=2

在深度為4的情況下，有節點9
計算fail（9），也就是求hers的失敗轉移狀態，由于父節點8的失敗轉移狀態0,1下面有s的條件可以跳轉到狀態3，所以fail(5)=3
這樣一來我們構造的fail表如下：

步驟3：對目標字符串進行搜索匹配

上面兩個步驟都完成了之后就可以開始對目標串進行搜索了，只需對目標串從頭到尾線性掃描，且沒有回溯。搜索之前先記錄樹的當前節點node，初始時，樹的當前節點node為根節點Root。從目標串的第一個字符開始，和Root的孩子節點進行匹配，如果不匹配，則目標字符串往后挪一個字符，繼續在Root的孩子節點中查找匹配。如果找到匹配的孩子，則目標字符串往后挪一個字符，node變為匹配上的孩子節點。在接下來的匹配過程中，如果失配將跳轉到node節點的fail值處繼續進行匹配。在樹上每次往孩子節點方向走一步都要檢查該孩子節點的匹配模式串信息，如果有匹配的模式串信息，則應記錄找到了哪些能夠匹配的模式串。

未完待續

參考文檔

https://tech.meituan.com/ac.html
https://my.oschina.net/u/3132973/blog/812141

總結

以上是生活随笔為你收集整理的Aho-Corasick 多模式匹配算法(AC自动机) 的算法详解及具体实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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