在閱讀本文之前，大家可以先參考下《多模字符串匹配算法原理及java實現(xiàn)代碼》
簡介：
本文是博主自身對ac自動機(jī)的原理的一些理解和看法，主要以舉例的方式講解，同時又配以相應(yīng)的圖片。代碼實現(xiàn)部分也予以明確的注釋，希望給大家不一樣的感受。ac自動機(jī)主要用于多模式字符串的匹配，本質(zhì)上是kmp算法的樹形擴(kuò)展。這篇文章主要介紹ac自動機(jī)的工作原理，并在此基礎(chǔ)上用java代碼實現(xiàn)一個簡易的ac自動機(jī)。
1.應(yīng)用場景—多模字符串匹配
我們現(xiàn)在考慮這樣一個問題，在一個文本串text中，我們想找出多個目標(biāo)字符串target1,target2,……出現(xiàn)的次數(shù)和位置。例如：求出目標(biāo)字符串集合{"nihao","hao","hs","hsr"}在給定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出現(xiàn)的位置。解決這個問題，我們一般的辦法就是在文本串中對每個目標(biāo)字符串單獨查找，并記錄下每次出現(xiàn)的位置。顯然這樣的方式能夠解決問題，但是在文本串較大、目標(biāo)字符串眾多的時候效率比較低。為了提高效率，貝爾實驗室于1975年發(fā)明著名的多模字符串匹配算法——ac自動機(jī)。ac自動機(jī)在實現(xiàn)上要依托于trie樹（也稱字典樹）并借鑒了kmp模式匹配算法的核心思想。實際上你可以把kmp算法看成每個節(jié)點都僅有一個孩子節(jié)點的ac自動機(jī)。
ac自動機(jī)用于多模匹配，所謂多模匹配，就是給定一個帶匹配的字符串string，給定一個字典dictionary，dictionary中有多個字符串{ str1,str2, str3 … } 多模匹配就是要得到string字符串中出現(xiàn)了dictionary的哪些字符，且這些字符出現(xiàn)在了string中的哪個位置。
2.ac自動機(jī)及其運行原理
2.1初識ac自動機(jī)
ac自動機(jī)的基礎(chǔ)是trie樹。和trie樹不同的是，樹中的每個結(jié)點除了有指向孩子的指針（或者說引用），還有一個fail指針，它表示輸入的字符與當(dāng)前結(jié)點的所有孩子結(jié)點都不匹配時(注意，不是和該結(jié)點本身不匹配)，自動機(jī)的狀態(tài)應(yīng)轉(zhuǎn)移到的狀態(tài)（或者說應(yīng)該轉(zhuǎn)移到的結(jié)點）。fail指針的功能可以類比于kmp算法中next數(shù)組的功能。
我們現(xiàn)在來看一個用目標(biāo)字符串集合{abd,abdk,abchijn,chnit,ijabdf,ijaij}構(gòu)造出來的ac自動機(jī)
上圖是一個構(gòu)建好的ac自動機(jī)，其中根結(jié)點不存儲任何字符，根結(jié)點的fail指針為null。虛線表示該結(jié)點的fail指針的指向，所有表示字符串的最后一個字符的結(jié)點外部都用紅圈表示，我們稱該結(jié)點為這個字符串的終結(jié)結(jié)點。每個結(jié)點實際上都有fail指針，但為了表示方便，本文約定一個原則，即所有指向根結(jié)點的fail虛線都未畫出。
從上圖中的ac自動機(jī)，我們可以看出一個重要的性質(zhì)：每個結(jié)點的fail指針表示由根結(jié)點到該結(jié)點所組成的字符序列的所有后綴和整個目標(biāo)字符串集合（也就是整個trie樹）中的所有前綴兩者中最長公共的部分。
比如圖中，由根結(jié)點到目標(biāo)字符串“ijabdf”中的‘d'組成的字符序列“ijabd”的所有后綴在整個目標(biāo)字符串集{abd,abdk,abchijn,chnit,ijabdf,ijaij}的所有前綴中最長公共的部分就是abd，而圖中d結(jié)點（字符串“ijabdf”中的這個d）的fail正是指向了字符序列abd的最后一個字符。
2.2ac自動機(jī)的運行過程：
1）表示當(dāng)前結(jié)點的指針指向ac自動機(jī)的根結(jié)點，即curr=root
2）從文本串中讀取（下）一個字符
3）從當(dāng)前結(jié)點的所有孩子結(jié)點中尋找與該字符匹配的結(jié)點，
若成功：判斷當(dāng)前結(jié)點以及當(dāng)前結(jié)點fail指向的結(jié)點是否表示一個字符串的結(jié)束，若是，則將文本串中索引起點記錄在對應(yīng)字符串保存結(jié)果集合中（索引起點=當(dāng)前索引-字符串長度+1）。curr指向該孩子結(jié)點，繼續(xù)執(zhí)行第2步
若失敗：執(zhí)行第4步。
4）若fail==null（說明目標(biāo)字符串中沒有任何字符串是輸入字符串的前綴，相當(dāng)于重啟狀態(tài)機(jī)）curr=root,執(zhí)行步驟2，
否則，將當(dāng)前結(jié)點的指針指向fail結(jié)點，執(zhí)行步驟3)
現(xiàn)在，我們來一個具體的例子加深理解，初始時當(dāng)前結(jié)點為root結(jié)點，我們現(xiàn)在假設(shè)文本串text=“abchnijabdfk”。
圖中的實曲線表示了整個搜索過程中的當(dāng)前結(jié)點指針的轉(zhuǎn)移過程，結(jié)點旁的文字表示了當(dāng)前結(jié)點下讀取的文本串字符。比如初始時，當(dāng)前指針指向根結(jié)點時，輸入字符‘a',則當(dāng)前指針指向結(jié)點a，此時再輸入字符‘b',自動機(jī)狀態(tài)轉(zhuǎn)移到結(jié)點b,……，以此類推。圖中ac自動機(jī)的最后狀態(tài)只是恰好回到根結(jié)點。
需要說明的是，當(dāng)指針位于結(jié)點b（圖中曲線經(jīng)過了兩次b,這里指第二次的b，即目標(biāo)字符串“ijabdf”中的b）,這時讀取文本串字符下標(biāo)為9的字符（即‘d'）時，由于b的所有孩子結(jié)點（這里恰好只有一個孩子結(jié)點）中存在能夠匹配輸入字符d的結(jié)點,那么當(dāng)前結(jié)點指針就指向了結(jié)點d，而此時該結(jié)點d的fail指針指向的結(jié)點又恰好表示了字符串“abc”的終結(jié)結(jié)點（用紅圈表示），所以我們找到了目標(biāo)字符串“abc”一次。這個過程我們在圖中用虛線表示，但狀態(tài)沒有轉(zhuǎn)移到“abd”中的d結(jié)點。
在輸入完所有文本串字符后，我們在文本串中找到了目標(biāo)字符串集合中的abd一次，位于文本串中下標(biāo)為7的位置；目標(biāo)字符串ijabdf一次，位于文本串中下標(biāo)為5的位置。
3.構(gòu)造ac自動機(jī)的方法與原理
3.1構(gòu)造的基本方法
首先我們將所有的目標(biāo)字符串插入到trie樹中，然后通過廣度優(yōu)先遍歷為每個結(jié)點的所有孩子節(jié)點的fail指針找到正確的指向。
確定fail指針指向的問題和kmp算法中構(gòu)造next數(shù)組的方式如出一轍。具體方法如下
1）將根結(jié)點的所有孩子結(jié)點的fail指向根結(jié)點，然后將根結(jié)點的所有孩子結(jié)點依次入列。
2）若隊列不為空：
2.1）出列，我們將出列的結(jié)點記為curr,failto表示curr的fail指向的結(jié)點，即failto=curr.fail
2.2)a.判斷curr.child[i]==failto.child[i]是否成立，
成立：curr.child[i].fail=failto.child[i]，
不成立：判斷failto==null是否成立
成立：curr.child[i].fail==root
不成立：執(zhí)行failto=failto.fail，繼續(xù)執(zhí)行2.2）
b.curr.child[i]入列，再次執(zhí)行再次執(zhí)行步驟2)
若隊列為空:結(jié)束
3.2通過一個例子來理解構(gòu)造ac自動機(jī)的原理
每個結(jié)點fail指向的解決順序是按照廣度優(yōu)先遍歷的順序完成的，或者說層序遍歷的順序進(jìn)行的，也就是說我們是在解決當(dāng)前結(jié)點的孩子結(jié)點fail的指向時，當(dāng)前結(jié)點的fail指針一定已指向了正確的位置。
為了說明問題，我們再次強(qiáng)調(diào)“每個結(jié)點的fail指針表示：由根結(jié)點到該結(jié)點所組成的字符序列的所有后綴和整個目標(biāo)字符串集合（也就是整個trie樹）中的所有前綴兩者中最長公共的部分”。
以上圖所示為例，我們要解決結(jié)點x1的某個孩子結(jié)點y的fail的指向問題。已知x1.fail指向x2，依據(jù)x1結(jié)點的fail指針的含義，我們可知紅色實線橢圓框內(nèi)的字符序列必然相等，且表示了最長公共部分。依據(jù)y.fail的含義，如果x2的某個孩子結(jié)點和結(jié)點y表示的字符相等，那么y.fail就該指向它。
如果x2的孩子結(jié)點中不存在結(jié)點y表示的字符，這個時候該怎么辦？由于x2.fail指向x3，根據(jù)x2.fail的含義，我們可知綠色方框內(nèi)的字符序列必然相等。顯然，如果x3的某個孩子結(jié)點和結(jié)點y表示的字符相等，那么y.fail就該指向它。
如果x3的孩子結(jié)點中不存在結(jié)點y表示的字符，我們可以依次重復(fù)這個步驟，直到xi結(jié)點的fail指向null，這時說明我們已經(jīng)到了最頂層的根結(jié)點，這時，我們只需要讓ｙ.fail=root即可。
構(gòu)造的過程的核心本質(zhì)就是，已知當(dāng)前結(jié)點的最長公共前綴的前提下，去確定孩子結(jié)點的最長公共前綴。這完全可以類比于kmp算法的next數(shù)組的求解過程。
3.2.1確定圖中h結(jié)點fail指向的過程
現(xiàn)在我們假設(shè)我們要確定圖中結(jié)點c的孩子結(jié)點h的fail指向。圖中每個結(jié)點都應(yīng)該有表示fail的虛線，但為了表示方便，按照本文約定的原則，所有指向根結(jié)點的fail虛線均未畫出。
左圖表示h.fail確定之前， 右圖表示h.fail確定之后
左圖中，藍(lán)色實線框住的結(jié)點的fail都已確定。現(xiàn)在我們應(yīng)該怎樣找到h.fail的正確指向？由于且結(jié)點c的fail已知（c結(jié)點為h結(jié)點的父結(jié)點），且指向了trie樹中所有前綴與字符序列‘a'‘b'‘c'的所有后綴（“bc”和“c”）的最長公共部分。現(xiàn)在我們要解決的問題是目標(biāo)字符串集合的所有前綴中與字符序列‘a'‘b'‘c'‘h'的所有后綴的最長公共部分。顯然c.fail指向的結(jié)點的孩子結(jié)點中存在結(jié)點h，那么h.fail就應(yīng)該指向c.fail的孩子結(jié)點h，所以右圖表示了h.fail確定后的情況。
3.2.2確定圖中i.fail指向的過程
左圖表示i.fail確定之前， 右圖表示i.fail確定之后
確定i.fail的指向時，顯然h.fail(h指圖中i的父結(jié)點的那個h)已指向了正確的位置。也就是說我們現(xiàn)在知道了目標(biāo)字符串集合所有前綴中與字符序列‘a'‘b'‘c'‘h'的所有后綴在trie樹中的最長前綴是‘c'‘h'。顯然從圖中可知h.fail的孩子結(jié)點是沒有i結(jié)點（這里h.fail只有一個孩子結(jié)點n）。字符序列‘c'‘h'的所有后綴在trie樹中的最長前綴可由h.fail的fail得到，而h.fail的fail指向root（依據(jù)本博客中畫圖的原則，這條fail虛線并未畫出）,root的孩子結(jié)點中存在表示字符i的結(jié)點,所以結(jié)果如右圖所示。
在知道i.fail的情況下，大家可以嘗試在紙上畫出j.fail的指向，以加深ac自動機(jī)構(gòu)造過程的理解。
4.ac自動機(jī)的java代碼實現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
package datastruct;import java.util.arraylist;import java.util.hashmap;import java.util.linkedlist;import java.util.list;import java.util.map.entry;public class ahocorasickautomation { /*本示例中的ac自動機(jī)只處理英文類型的字符串，所以數(shù)組的長度是128*/ private static final int ascii = 128; /*ac自動機(jī)的根結(jié)點，根結(jié)點不存儲任何字符信息*/ private node root; /*待查找的目標(biāo)字符串集合*/ private list<string> target; /*表示在文本字符串中查找的結(jié)果，key表示目標(biāo)字符串， value表示目標(biāo)字符串在文本串出現(xiàn)的位置*/ private hashmap<string, list<integer>> result; /*內(nèi)部靜態(tài)類，用于表示ac自動機(jī)的每個結(jié)點，在每個結(jié)點中我們并沒有存儲該結(jié)點對應(yīng)的字符*/ private static class node{ /*如果該結(jié)點是一個終點，即，從根結(jié)點到此結(jié)點表示了一個目標(biāo)字符串，則str != null, 且str就表示該字符串*/ string str; /*ascii == 128, 所以這里相當(dāng)于128叉樹*/ node[] table = new node[ascii]; /*當(dāng)前結(jié)點的孩子結(jié)點不能匹配文本串中的某個字符時，下一個應(yīng)該查找的結(jié)點*/ node fail; public boolean isword(){ return str != null; } } /*target表示待查找的目標(biāo)字符串集合*/ public ahocorasickautomation(list<string> target){ root = new node(); this.target = target; buildtrietree(); build_ac_fromtrie(); } /*由目標(biāo)字符串構(gòu)建trie樹*/ private void buildtrietree(){ for (string targetstr : target){ node curr = root; for (int i = 0; i < targetstr.length(); i++){ char ch = targetstr.charat(i); if(curr.table[ch] == null){ curr.table[ch] = new node(); } curr = curr.table[ch]; } /*將每個目標(biāo)字符串的最后一個字符對應(yīng)的結(jié)點變成終點*/ curr.str = targetstr; } } /*由trie樹構(gòu)建ac自動機(jī)，本質(zhì)是一個自動機(jī)，相當(dāng)于構(gòu)建kmp算法的next數(shù)組*/ private void build_ac_fromtrie(){ /*廣度優(yōu)先遍歷所使用的隊列*/ linkedlist<node> queue = new linkedlist<node>(); /*單獨處理根結(jié)點的所有孩子結(jié)點*/ for (node x : root.table){ if(x != null){ /*根結(jié)點的所有孩子結(jié)點的fail都指向根結(jié)點*/ x.fail = root; queue.addlast(x); /*所有根結(jié)點的孩子結(jié)點入列*/ } } while(!queue.isempty()){ /*確定出列結(jié)點的所有孩子結(jié)點的fail的指向*/ node p = queue.removefirst(); for (int i = 0; i < p.table.length; i++){ if(p.table[i] != null){ /*孩子結(jié)點入列*/ queue.addlast(p.table[i]); /*從p.fail開始找起*/ node failto = p.fail; while(true){ /*說明找到了根結(jié)點還沒有找到*/ if(failto == null){ p.table[i].fail = root; break; } /*說明有公共前綴*/ if(failto.table[i] != null){ p.table[i].fail = failto.table[i]; break; } else{ /*繼續(xù)向上尋找*/ failto = failto.fail; } } } } } } /*在文本串中查找所有的目標(biāo)字符串*/ public hashmap<string, list<integer>> find(string text){ /*創(chuàng)建一個表示存儲結(jié)果的對象*/ result = new hashmap<string, list<integer>>(); for (string s : target){ result.put(s, new linkedlist<integer>()); } node curr = root; int i = 0; while(i < text.length()){ /*文本串中的字符*/ char ch = text.charat(i); /*文本串中的字符和ac自動機(jī)中的字符進(jìn)行比較*/ if(curr.table[ch] != null){ /*若相等，自動機(jī)進(jìn)入下一狀態(tài)*/ curr = curr.table[ch]; if(curr.isword()){ result.get(curr.str).add(i - curr.str.length()+1); } /*這里很容易被忽視，因為一個目標(biāo)串的中間某部分字符串可能正好包含另一個目標(biāo)字符串， * 即使當(dāng)前結(jié)點不表示一個目標(biāo)字符串的終點，但到當(dāng)前結(jié)點為止可能恰好包含了一個字符串*/ if(curr.fail != null && curr.fail.isword()){ result.get(curr.fail.str).add(i - curr.fail.str.length()+1); } /*索引自增，指向下一個文本串中的字符*/ i++; } else{ /*若不等，找到下一個應(yīng)該比較的狀態(tài)*/ curr = curr.fail; /*到根結(jié)點還未找到，說明文本串中以ch作為結(jié)束的字符片段不是任何目標(biāo)字符串的前綴， * 狀態(tài)機(jī)重置，比較下一個字符*/ if(curr == null){ curr = root; i++; } } } return result; } public static void main(string[] args){ list<string> target = new arraylist<string>(); target.add("abcdef"); target.add("abhab"); target.add("bcd"); target.add("cde"); target.add("cdfkcdf"); string text = "bcabcdebcedfabcdefababkabhabk"; ahocorasickautomation aca = new ahocorasickautomation(target); hashmap<string, list<integer>> result = aca.find(text); system.out.println(text); for (entry<string, list<integer>> entry : result.entryset()){ system.out.println(entry.getkey()+" : " + entry.getvalue()); } }} |
運行結(jié)果如下，從結(jié)果中我們可以看出文本串中bcd出現(xiàn)了二次，分別是文本串下標(biāo)為3和下標(biāo)為13的位置，……。
|
1
2
3
4
5
6
|
bcabcdebcedfabcdefababkabhabkbcd : [3, 13]cdfkcdf : []cde : [4, 14]abcdef : [12]abhab : [23] |
總結(jié)
以上就是本文關(guān)于java編程之a(chǎn)c自動機(jī)工作原理與實現(xiàn)代碼的全部內(nèi)容，希望對大家有所幫助。如有不足之處，歡迎留言指出。
原文鏈接：http://www.cnblogs.com/nullzx/p/7499397.html
