早在1975年貝爾實驗室的兩位研究人員Alfred V. Aho 和Margaret J. Corasick就提出了以他們的名字命名的高效的比對算法—AC算法。該算法幾乎與《KMP算法》同時問世。與KMP算法相同,AC算法時至今日仍然在模式比對領域被廣泛應用。
AC算法是一個經典的多模式比對算法,可以保證對于給定的長度為n的文本,和模式集合P{p1,p2,…pm},在O(n)時間複雜度内,找到文本中的所有目标模式,而與模式集合的規模m無關。
正如KMP算法在單模式比對方面的突出貢獻一樣,AC算法對于多模式比對算法後續的發展也産生了深遠的影響,而且更為重要的是,兩者都是在對同一問題——模式串字首的自包含問題的研究中,産生出來的,AC算法從某種程度上可以說是KMP算法在多模式環境下的擴充。
如果要用KMP算法比對長度為n的文本中的m個模式,則需要為每一個模式維護一個next跳轉表,在執行對文本的比對過程中,我們需要關注所有這些next表的狀态轉移情況,這使得時間複雜度增長為O(mn),對于較大的模式集合來說,這樣的時間增長可能是無法接受的。AC算法解決了這一問題,通過對模式集合P的預處理,去除了模式集合的規模對比對算法速度的影響。
AC定義:
AC有限自動機 M 是1個6元組:M =(Q,∑,g,f,qo,F)其中:
1、Q是有限狀态集(模式樹上的所有節點).
2、∑是有限的輸入字元表(模式樹所有邊上的字元).
3、g是轉移函數.
4、f是失效函數,不比對時自動機的狀态轉移.
5、qo∈Q是初态(根節點);
6、F量Q是終态集(以模式為标簽的節點集).
AC算法思想
多模式比對AC算法的核心仍然是尋找模式串内部規律,達到在每次失配時的高效跳轉。這一點與單模式比對KMP算法和BM算法是一緻的。不同的是,AC算法尋找的是模式串之間的相同字首關系。
要了解AC算法,仍然需要對KMP算法的透徹了解。那麼字首自包含如何在AC算法中發揮作用?
在KMP算法中,對于模式串”abcabcacab”,我們知道非字首子串abc(abca)cab是模式串的一個字首(abca)bcacab,而非字首子串ab(cabca)cab不是模式串abcabcacab的字首,根據此點,我們構造了next結構,實作在比對失敗時的跳轉。
而在多模式環境中,這個情況會發生一定的變化。
對于模式集合P{he,she,his,hers},模式s(he)的非字首子串he,實際上卻是模式(he),(he)rs的字首。如果目标串target[i…i+2]與模式she比對,同時也意味着target[i+1…i+2]與he,hers這兩個模式的頭兩個字元比對,是以此時對于target[i+3],我們不需要回溯目标串的目前位置,而直接将其與he,hers兩個模式的第3個字元對齊,然後直接向後繼續執行比對操作
經典的AC算法由三部分構成,goto表,fail表和output表,共包含四種具體的算法,分别是計算三張查找表的算法以及AC算法本身。
goto表是由模式集合P中的所有模式構成的狀态轉移自動機。
failure表作用是在goto表中比對失敗後狀态跳轉的依據,這點與KMP中next表的作用相似。
output表示輸出,又稱:emits,即代表到達某個狀态後某個模式串比對成功
構造goto表
goto表是由模式集合P中的所有模式構成的狀态轉移自動機,本質上是一個有限狀态機,這裡稱作模式比對機(Pattern Matching Machine,PMM)。
對于給定的集合P{p1,p2,…pm},建構goto表的步驟是,對于P中的每一個模式pi[1…j](1 <= i < m+1)),按照其包含的字母從前到後依次輸入自動機,起始狀态D[0],如果自動機的目前狀态D[p],對于pi中的目前字母pi[k](1<=k<=j),沒有可用的轉移,則将狀态機的總狀态數smax+1,并将目前狀态輸入pi[k]後的轉移位置,置為D[p][pi[k]] = smax,如果存在可用的轉移方案D[p][pi[k]]=q,則轉移到狀态D[q],同時取出模式串的下一個字母pi[k+1],繼續進行上面的判斷過程。這裡我們所說的沒有可用的轉移方案,等同于轉移到狀态機D的初始狀态D[0],即對于自動機狀态D[p],輸入字元pi[k],有D[p][pi[k]]=0。
對于模式集合P{he,she,his,hers}, goto表的建構過程如下:
1、PMM初始狀态為0,然後向PMM中加入第一個模式串K[0] = “he”。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyM0ITO1cjMwETMyMDM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
2、繼續向PMM中添加第二個模式串K[1] = “she”,每次添加都是從狀态0開始掃描。
3、從狀态0開始繼續添加第三個模式串K[2] = “his”,這裡值得注意的是遇到相同字元跳轉時要重複利用以前已經生成的跳轉。如這裡的’h’在第一步中已經存在。
4、添加模式串K[3] = “hers”。至此,goto表已經構造完成。
對于第一和第二步而言,兩個模式沒有重疊的字首部分,是以每輸入一個字元,都對應一個新狀态。第三步時,我們發現,D[0][p3[1]]=D[0][‘h’]=1,是以對于新模式p3的首字母’h’,我們不需要新增加一個狀态,而隻需将D的目前狀态轉移到D[1]即可。而對于模式p4其前兩個字元he使狀态機轉移至狀态D[2],是以其第三字元對應的狀态D[8]就緊跟在D[2]之後。
構造failure表
failure表作用是在goto表中比對失敗後狀态跳轉的依據,這點與KMP中next表的作用相似。
首先說明什麼狀态,在上面goto表的圖裡,把圓圈裡的數字記為狀态。
再引入狀态深度的概念,狀态s的深度depth(s)定義為在goto表中從起始狀态0到狀态s的最短路徑長度。如goto表中狀态1和3的深度為1。
計算思路:先計算所有深度是1的狀态的失效函數值,然後計算所有深度為2的狀态,以此類推,直到所有狀态(除了狀态0,因為它的失效函數沒有定義)的失效函數值都被計算出。
計算方法:用于計算某個狀态失效函數值的算法在概念上是非常簡單的。首先,令所有深度為1的狀态s的函數值為f(s) = 0。假設所有深度小于d的狀态的f值都已經被算出了,那麼深度為d的狀态的失效函數值将根據深度小于d的狀态的失效函數值來計算。
具體步驟: 構造failure表利用到了遞歸的思想。
1、若depth(s) = 1,則f(s) = 0;即與狀态0距離為1(即深度為1)的所有狀态的fail值都為0
2、假設深度為d-1的所有狀态r, 即depth(r) < d,已經計算出了f(r);
3、那麼對于深度為d的狀态s:
(1) 若所有的字元a, 滿足g(r,a) = fail,則不動作;(注:g為狀态轉移函數);
(2) 否則,對每個使 g(r, a) = s成立的字元a,執行以下操作::
a、使state = f(r)
b、重複步驟state = f(state),直到g(state, a) != fail。(注意對于任意的a,狀态0的g(0,a) != fail)
c、使f(s) = g(state, a)。
例子: 求狀态4 的failure 狀态,已知其前一個(父節點)的f(1)= 0,且狀态0(根節點)有字元’h’的外向邊,該外向邊對應狀态1,則有f(4) = 1;類似字首規則:求已經比對字串”sh” 最大字尾,同時是某個模式串的字首;
根據以上算法,得到該例子的failure表為:
i 1 2 3 4 5 6 7 8 9
f(i) 0 0 0 1 2 0 3 0 3
将failure表用虛線表現,整合goto表,得到下圖:
構造output表
output表示輸出,即代表到達某個狀态後某個模式串比對成功。該表的構造過程融合在goto表和failure表的構造過程中。
1、在構造goto表時,每個模式串結束的狀态都加入到output表中,也就goto表中的黑色加粗圓圈。得到
i output(i)
2 {he}
5 {she}
7 {his}
9 {hers}
2、在構造failure表時,若f(s) = s’,則将s和s‘對應的output集合求并集。如f(5) = 2,則得到最終的output表為:
i output(i)
2 {he}
5 {she,he}
7 {his}
9 {hers}
AC算法比對過程
自動機從根節點0出發
1、首先嘗試按success表轉移(圖中實線)。按照文本的訓示轉移,也就是接收一個u。此時success表中并沒有相應路線,轉移失敗。
2、失敗了則按照failure表回去(圖中虛線)。按照文本訓示,這次接收一個s,轉移到狀态3。
3、成功了繼續按success表轉移,直到失敗跳轉步驟2,或者遇到output表中标明的“可輸出狀态”(圖中紅色狀态)。此時輸出比對到的模式串,然後将此狀态視作普通的狀态繼續轉移。
根據上面已經構造好的goto、failure和output表。以字元串”ushers”為例。狀态轉移如下:
u s h e r s
0 0 3 4 5 8 9
2
說明:在狀态5發生失配,查找failure表,轉到狀态2繼續比較。在狀态5和狀态9有輸出。
算法高效之處在于,當自動機接受了“ushe”之後,再接受一個r會導緻無法按照success表轉移,此時自動機會聰明地按照failure表轉移到2号狀态,并經過幾次轉移後輸出“hers”。來到2号狀态的路不止一條,從根節點一路往下,“h→e”也可以到達。而這個“he”恰好是“ushe”的結尾,狀态機就仿佛是壓根就沒失敗過(沒有接受r),也沒有接受過中間的字元“us”,直接就從初始狀态按照“he”的路徑走過來一樣(到達同一節點,狀态完全相同)。
AC算法具體實作:
robert-bor實作的ac算法(java):https://github.com/robert-bor/aho-corasick
hankcs改進robert-bor的ac算法(java):https://github.com/hankcs/aho-corasick。
簡單實作java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Hashtable;
import java.util.List;
public class ACTest {
static String Text = "ushers";
static String[] Pattens = {"he", "she", "his", "hers"};
// 根節點
static TreeNode root;
public static void main(String[] args) {
buildGotoTree(); // 建構goto表和output表
addFailure(); // 建構failure表
printTree(); // 列印tree的字元、深度、狀态,fail值
acSearch(); // 查找ushers, 并列印比對的位置和模式
}
/**
* 建構Goto表和output表
*/
public static void buildGotoTree(){
int i = ;
root = new TreeNode(null, ' ');
// 判斷節點是否存在, 存在轉移 ,不存在添加
for (String word : Pattens) {
TreeNode temp = root;
for (char ch : word.toCharArray()) {
TreeNode innerTem = temp.getSonNode(ch);
if(innerTem == null){
TreeNode newNode = new TreeNode(temp, ch);
newNode.setStatus(i++);
temp.addSonNode(newNode);
innerTem = newNode;
}
temp = innerTem;
}
temp.addResult(word);
}
}
/**
* 建構failure表
* 周遊所有節點, 設定失敗節點 原則: 節點的失敗指針在父節點的失敗指針的子節點中查找 最大字尾匹
*/
public static void addFailure(){
// 過程容器
ArrayList<TreeNode> mid = new ArrayList<TreeNode>();
// 首先,設定二層失敗指針為根節點 收集三層節點。 即令所有深度為1的狀态s的函數值為f(s) = 0。
for (TreeNode node : root.getSons()) {
node.setFailure(root);
for (TreeNode treeNode : node.getSons()) {
mid.add(treeNode);
}
}
// 廣度周遊所有節點設定失敗指針 1.存在失敗指針 2.不存在到root結束
while(mid.size() > ){
// 子節點收集器
ArrayList<TreeNode> temp = new ArrayList<TreeNode>();
for (TreeNode node : mid) {
TreeNode r = node.getParent().getFailure();
// 沒有找到,保證最大字尾 (最後一個節點字元相同)
while(r != null && r.getSonNode(node.getCh()) == null){
r = r.getFailure();
}
// 是根結節點
if(r == null){
node.setFailure(root);
}else{
node.setFailure(r.getSonNode(node.getCh()));
// 重疊字尾的包含
for (String result : node.getFailure().getResults()) {
node.addResult(result);
}
}
// 收集子節點
temp.addAll(node.getSons());
}
mid = temp;
}
}
/**
* 根據狀态順序列印樹資訊
*/
public static void printTree(){
// 收集所有節點
List<TreeNode> nodesList = new ArrayList<TreeNode>();
// 過程容器
List<TreeNode> nodes = Arrays.asList(root);
while(nodes.size() > ){
ArrayList<TreeNode> temp = new ArrayList<TreeNode>();
for(TreeNode node : nodes){
temp.addAll(node.getSons());
nodesList.add(node);
}
nodes = temp;
}
// 排序
Collections.sort(nodesList, (a, b) -> a.getStatus().compareTo(b.getStatus()));
for(TreeNode node : nodesList){
System.out.println(node.getCh() + " " + node.getDepth() + " " + node.getStatus() +
" " + (node.getFailure() != null ? node.getFailure().getStatus() : "0"));
}
}
// 查找全部的模式串
public static void acSearch(){
// 可以找到 轉移到下個節點 不能找到在失敗指針節點中查找直到為root節點
int index = ;
TreeNode mid = root;
while(index < Text.length()){
TreeNode temp = null;
while(temp ==null){
temp = mid.getSonNode(Text.charAt(index));
if(mid ==root){
break;
}
if(temp==null){
mid = mid.getFailure();
}
}
// mid為root 再次進入循環 不需要處理 或者 temp不為空找到節點 節點位移
if (temp != null) mid = temp;
for (String result : mid.getResults()) {
System.out.println((index - result.length() + ) + ":" + index + "=" + result);
}
index++;
}
}
}
class TreeNode{
// 父節點
private TreeNode parent;
// failuere
private TreeNode failure;
// 字元
private char ch;
// goto表
private List<TreeNode> sons;
// 擷取子節點
private Hashtable<Character, TreeNode> sonsHash;
// output
private List<String> results;
// 深度
private int depth = ;
// 狀态
private Integer status = ;
public TreeNode(TreeNode parent, char ch) {
this.parent = parent;
this.ch = ch;
results = new ArrayList<String>();
sonsHash = new Hashtable<Character, TreeNode>();
sons = new ArrayList<TreeNode>();
if(parent != null)
depth = parent.getDepth() + ;
}
// 添加一個結果到結果字元中, 狀态5量 output : he 和 she
public void addResult(String result){
if(!results.contains(result)) results.add(result);
}
// 添加子節點
public void addSonNode(TreeNode node){
sonsHash.put(node.ch, node);
sons.add(node);
}
// 設定失敗指針并且傳回
public TreeNode setFailure(TreeNode failure){
this.failure = failure;
return this.failure;
}
// 擷取子節點中指定字元節點
public TreeNode getSonNode(char ch){
return sonsHash.get(ch);
}
// 擷取父節點
public TreeNode getParent() {
return parent;
}
// 擷取字元
public char getCh() {
return ch;
}
// 擷取所有的孩子節點
public List<TreeNode> getSons() {
return sons;
}
// 擷取搜尋的字元串
public List<String> getResults() {
return results;
}
// 擷取深度
public int getDepth() {
return depth;
}
public Integer getStatus() {
return status;
}
public void setStatus(Integer status) {
this.status = status;
}
public TreeNode getFailure() {
return failure;
}
}
心得:
KMP算法依然是解讀AC算法的重要線索,字首,子串,字尾永遠和模式比對糾纏在一起。
AC狀态機實際上更适合用Trie結構來存儲。
可以将算法中使用到的goto,fail,output三張表以離線的方式計算出來儲存在一個檔案中,當AC算法啟動時,直接從檔案中讀取三個表的内容,這樣可以有效減少每次AC算法啟動時都需要建構三個表所花費的時間。
可以把同深度節點排序,後面查找某狀态的指定字元外向邊狀态,可以使用二分查找,加快速度;
值得注意的是在AC算法的以上實作中,對于輸入字元a的跳轉次數是不确定的。因為有可能在輸入a後發生失配,需要查找failure表重新跳轉。能不能在PMM的基礎上實作确定型的有限狀态機,即對于任意字元a,都隻用進行一次确定的狀态跳轉?答案是肯定的。在Aho和Corasick論文中給出了處理的方法:構造一個與KMP算法中相似的next表,實作确定性跳轉。