十年網(wǎng)站開發(fā)經(jīng)驗(yàn) + 多家企業(yè)客戶 + 靠譜的建站團(tuán)隊(duì)
量身定制 + 運(yùn)營維護(hù)+專業(yè)推廣+無憂售后,網(wǎng)站問題一站解決
這篇文章將為大家詳細(xì)講解有關(guān)java編程之AC自動機(jī)工作原理的示例分析,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
成都創(chuàng)新互聯(lián)是一家專注于網(wǎng)站建設(shè)、做網(wǎng)站與策劃設(shè)計(jì),合作網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:合作等地區(qū)。合作做網(wǎng)站價(jià)格咨詢:18980820575
1.應(yīng)用場景—多模字符串匹配
我們現(xiàn)在考慮這樣一個(gè)問題,在一個(gè)文本串text中,我們想找出多個(gè)目標(biāo)字符串target1,target2,……出現(xiàn)的次數(shù)和位置。例如:求出目標(biāo)字符串集合{"nihao","hao","hs","hsr"}在給定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出現(xiàn)的位置。解決這個(gè)問題,我們一般的辦法就是在文本串中對每個(gè)目標(biāo)字符串單獨(dú)查找,并記錄下每次出現(xiàn)的位置。顯然這樣的方式能夠解決問題,但是在文本串較大、目標(biāo)字符串眾多的時(shí)候效率比較低。為了提高效率,貝爾實(shí)驗(yàn)室于1975年發(fā)明著名的多模字符串匹配算法——AC自動機(jī)。AC自動機(jī)在實(shí)現(xiàn)上要依托于Trie樹(也稱字典樹)并借鑒了KMP模式匹配算法的核心思想。實(shí)際上你可以把KMP算法看成每個(gè)節(jié)點(diǎn)都僅有一個(gè)孩子節(jié)點(diǎn)的AC自動機(jī)。
AC自動機(jī)用于多模匹配,所謂多模匹配,就是給定一個(gè)帶匹配的字符串string,給定一個(gè)字典dictionary,dictionary中有多個(gè)字符串{ str1,str2, str3 … } 多模匹配就是要得到string字符串中出現(xiàn)了dictionary的哪些字符,且這些字符出現(xiàn)在了string中的哪個(gè)位置。
2.AC自動機(jī)及其運(yùn)行原理
2.1初識AC自動機(jī)
AC自動機(jī)的基礎(chǔ)是Trie樹。和Trie樹不同的是,樹中的每個(gè)結(jié)點(diǎn)除了有指向孩子的指針(或者說引用),還有一個(gè)fail指針,它表示輸入的字符與當(dāng)前結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)都不匹配時(shí)(注意,不是和該結(jié)點(diǎn)本身不匹配),自動機(jī)的狀態(tài)應(yīng)轉(zhuǎn)移到的狀態(tài)(或者說應(yīng)該轉(zhuǎn)移到的結(jié)點(diǎn))。fail指針的功能可以類比于KMP算法中next數(shù)組的功能。
我們現(xiàn)在來看一個(gè)用目標(biāo)字符串集合{abd,abdk,abchijn,chnit,ijabdf,ijaij}構(gòu)造出來的AC自動機(jī)

上圖是一個(gè)構(gòu)建好的AC自動機(jī),其中根結(jié)點(diǎn)不存儲任何字符,根結(jié)點(diǎn)的fail指針為null。虛線表示該結(jié)點(diǎn)的fail指針的指向,所有表示字符串的最后一個(gè)字符的結(jié)點(diǎn)外部都用紅圈表示,我們稱該結(jié)點(diǎn)為這個(gè)字符串的終結(jié)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)實(shí)際上都有fail指針,但為了表示方便,本文約定一個(gè)原則,即所有指向根結(jié)點(diǎn)的fail虛線都未畫出。
從上圖中的AC自動機(jī),我們可以看出一個(gè)重要的性質(zhì):每個(gè)結(jié)點(diǎn)的fail指針表示由根結(jié)點(diǎn)到該結(jié)點(diǎn)所組成的字符序列的所有后綴和整個(gè)目標(biāo)字符串集合(也就是整個(gè)Trie樹)中的所有前綴兩者中最長公共的部分。
比如圖中,由根結(jié)點(diǎn)到目標(biāo)字符串“ijabdf”中的‘d'組成的字符序列“ijabd”的所有后綴在整個(gè)目標(biāo)字符串集{abd,abdk,abchijn,chnit,ijabdf,ijaij}的所有前綴中最長公共的部分就是abd,而圖中d結(jié)點(diǎn)(字符串“ijabdf”中的這個(gè)d)的fail正是指向了字符序列abd的最后一個(gè)字符。
2.2AC自動機(jī)的運(yùn)行過程:
1)表示當(dāng)前結(jié)點(diǎn)的指針指向AC自動機(jī)的根結(jié)點(diǎn),即curr=root
2)從文本串中讀取(下)一個(gè)字符
3)從當(dāng)前結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)中尋找與該字符匹配的結(jié)點(diǎn),
若成功:判斷當(dāng)前結(jié)點(diǎn)以及當(dāng)前結(jié)點(diǎn)fail指向的結(jié)點(diǎn)是否表示一個(gè)字符串的結(jié)束,若是,則將文本串中索引起點(diǎn)記錄在對應(yīng)字符串保存結(jié)果集合中(索引起點(diǎn)=當(dāng)前索引-字符串長度+1)。curr指向該孩子結(jié)點(diǎn),繼續(xù)執(zhí)行第2步
若失?。簣?zhí)行第4步。
4)若fail==null(說明目標(biāo)字符串中沒有任何字符串是輸入字符串的前綴,相當(dāng)于重啟狀態(tài)機(jī))curr=root,執(zhí)行步驟2,
否則,將當(dāng)前結(jié)點(diǎn)的指針指向fail結(jié)點(diǎn),執(zhí)行步驟3)
現(xiàn)在,我們來一個(gè)具體的例子加深理解,初始時(shí)當(dāng)前結(jié)點(diǎn)為root結(jié)點(diǎn),我們現(xiàn)在假設(shè)文本串text=“abchnijabdfk”。

圖中的實(shí)曲線表示了整個(gè)搜索過程中的當(dāng)前結(jié)點(diǎn)指針的轉(zhuǎn)移過程,結(jié)點(diǎn)旁的文字表示了當(dāng)前結(jié)點(diǎn)下讀取的文本串字符。比如初始時(shí),當(dāng)前指針指向根結(jié)點(diǎn)時(shí),輸入字符‘a(chǎn)',則當(dāng)前指針指向結(jié)點(diǎn)a,此時(shí)再輸入字符‘b',自動機(jī)狀態(tài)轉(zhuǎn)移到結(jié)點(diǎn)b,……,以此類推。圖中AC自動機(jī)的最后狀態(tài)只是恰好回到根結(jié)點(diǎn)。
需要說明的是,當(dāng)指針位于結(jié)點(diǎn)b(圖中曲線經(jīng)過了兩次b,這里指第二次的b,即目標(biāo)字符串“ijabdf”中的b),這時(shí)讀取文本串字符下標(biāo)為9的字符(即‘d')時(shí),由于b的所有孩子結(jié)點(diǎn)(這里恰好只有一個(gè)孩子結(jié)點(diǎn))中存在能夠匹配輸入字符d的結(jié)點(diǎn),那么當(dāng)前結(jié)點(diǎn)指針就指向了結(jié)點(diǎn)d,而此時(shí)該結(jié)點(diǎn)d的fail指針指向的結(jié)點(diǎn)又恰好表示了字符串“abc”的終結(jié)結(jié)點(diǎn)(用紅圈表示),所以我們找到了目標(biāo)字符串“abc”一次。這個(gè)過程我們在圖中用虛線表示,但狀態(tài)沒有轉(zhuǎn)移到“abd”中的d結(jié)點(diǎn)。
在輸入完所有文本串字符后,我們在文本串中找到了目標(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)先遍歷為每個(gè)結(jié)點(diǎn)的所有孩子節(jié)點(diǎn)的fail指針找到正確的指向。
確定fail指針指向的問題和KMP算法中構(gòu)造next數(shù)組的方式如出一轍。具體方法如下
1)將根結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)的fail指向根結(jié)點(diǎn),然后將根結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)依次入列。
2)若隊(duì)列不為空:
2.1)出列,我們將出列的結(jié)點(diǎn)記為curr,failTo表示curr的fail指向的結(jié)點(diǎn),即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)
若隊(duì)列為空:結(jié)束
3.2通過一個(gè)例子來理解構(gòu)造AC自動機(jī)的原理
每個(gè)結(jié)點(diǎn)fail指向的解決順序是按照廣度優(yōu)先遍歷的順序完成的,或者說層序遍歷的順序進(jìn)行的,也就是說我們是在解決當(dāng)前結(jié)點(diǎn)的孩子結(jié)點(diǎn)fail的指向時(shí),當(dāng)前結(jié)點(diǎn)的fail指針一定已指向了正確的位置。

為了說明問題,我們再次強(qiáng)調(diào)“每個(gè)結(jié)點(diǎn)的fail指針表示:由根結(jié)點(diǎn)到該結(jié)點(diǎn)所組成的字符序列的所有后綴和整個(gè)目標(biāo)字符串集合(也就是整個(gè)Trie樹)中的所有前綴兩者中最長公共的部分”。
以上圖所示為例,我們要解決結(jié)點(diǎn)x1的某個(gè)孩子結(jié)點(diǎn)y的fail的指向問題。已知x1.fail指向x2,依據(jù)x1結(jié)點(diǎn)的fail指針的含義,我們可知紅色實(shí)線橢圓框內(nèi)的字符序列必然相等,且表示了最長公共部分。依據(jù)y.fail的含義,如果x2的某個(gè)孩子結(jié)點(diǎn)和結(jié)點(diǎn)y表示的字符相等,那么y.fail就該指向它。
如果x2的孩子結(jié)點(diǎn)中不存在結(jié)點(diǎn)y表示的字符,這個(gè)時(shí)候該怎么辦?由于x2.fail指向x3,根據(jù)x2.fail的含義,我們可知綠色方框內(nèi)的字符序列必然相等。顯然,如果x3的某個(gè)孩子結(jié)點(diǎn)和結(jié)點(diǎn)y表示的字符相等,那么y.fail就該指向它。
如果x3的孩子結(jié)點(diǎn)中不存在結(jié)點(diǎn)y表示的字符,我們可以依次重復(fù)這個(gè)步驟,直到xi結(jié)點(diǎn)的fail指向null,這時(shí)說明我們已經(jīng)到了最頂層的根結(jié)點(diǎn),這時(shí),我們只需要讓y.fail=root即可。
構(gòu)造的過程的核心本質(zhì)就是,已知當(dāng)前結(jié)點(diǎn)的最長公共前綴的前提下,去確定孩子結(jié)點(diǎn)的最長公共前綴。這完全可以類比于KMP算法的next數(shù)組的求解過程。
3.2.1確定圖中h結(jié)點(diǎn)fail指向的過程
現(xiàn)在我們假設(shè)我們要確定圖中結(jié)點(diǎn)c的孩子結(jié)點(diǎn)h的fail指向。圖中每個(gè)結(jié)點(diǎn)都應(yīng)該有表示fail的虛線,但為了表示方便,按照本文約定的原則,所有指向根結(jié)點(diǎn)的fail虛線均未畫出。


左圖表示h.fail確定之前, 右圖表示h.fail確定之后
左圖中,藍(lán)色實(shí)線框住的結(jié)點(diǎn)的fail都已確定?,F(xiàn)在我們應(yīng)該怎樣找到h.fail的正確指向?由于且結(jié)點(diǎn)c的fail已知(c結(jié)點(diǎn)為h結(jié)點(diǎn)的父結(jié)點(diǎn)),且指向了Trie樹中所有前綴與字符序列‘a(chǎn)'‘b'‘c'的所有后綴(“bc”和“c”)的最長公共部分?,F(xiàn)在我們要解決的問題是目標(biāo)字符串集合的所有前綴中與字符序列‘a(chǎn)'‘b'‘c'‘h'的所有后綴的最長公共部分。顯然c.fail指向的結(jié)點(diǎn)的孩子結(jié)點(diǎn)中存在結(jié)點(diǎn)h,那么h.fail就應(yīng)該指向c.fail的孩子結(jié)點(diǎn)h,所以右圖表示了h.fail確定后的情況。
3.2.2確定圖中i.fail指向的過程


左圖表示i.fail確定之前, 右圖表示i.fail確定之后
確定i.fail的指向時(shí),顯然h.fail(h指圖中i的父結(jié)點(diǎn)的那個(gè)h)已指向了正確的位置。也就是說我們現(xiàn)在知道了目標(biāo)字符串集合所有前綴中與字符序列‘a(chǎn)'‘b'‘c'‘h'的所有后綴在Trie樹中的最長前綴是‘c'‘h'。顯然從圖中可知h.fail的孩子結(jié)點(diǎn)是沒有i結(jié)點(diǎn)(這里h.fail只有一個(gè)孩子結(jié)點(diǎn)n)。字符序列‘c'‘h'的所有后綴在Trie樹中的最長前綴可由h.fail的fail得到,而h.fail的fail指向root(依據(jù)本博客中畫圖的原則,這條fail虛線并未畫出),root的孩子結(jié)點(diǎn)中存在表示字符i的結(jié)點(diǎn),所以結(jié)果如右圖所示。
在知道i.fail的情況下,大家可以嘗試在紙上畫出j.fail的指向,以加深A(yù)C自動機(jī)構(gòu)造過程的理解。
4.AC自動機(jī)的java代碼實(shí)現(xiàn)
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é)點(diǎn),根結(jié)點(diǎn)不存儲任何字符信息*/
private Node root;
/*待查找的目標(biāo)字符串集合*/
private List target;
/*表示在文本字符串中查找的結(jié)果,key表示目標(biāo)字符串, value表示目標(biāo)字符串在文本串出現(xiàn)的位置*/
private HashMap> result;
/*內(nèi)部靜態(tài)類,用于表示AC自動機(jī)的每個(gè)結(jié)點(diǎn),在每個(gè)結(jié)點(diǎn)中我們并沒有存儲該結(jié)點(diǎn)對應(yīng)的字符*/
private static class Node{
/*如果該結(jié)點(diǎn)是一個(gè)終點(diǎn),即,從根結(jié)點(diǎn)到此結(jié)點(diǎn)表示了一個(gè)目標(biāo)字符串,則str != null, 且str就表示該字符串*/
String str;
/*ASCII == 128, 所以這里相當(dāng)于128叉樹*/
Node[] table = new Node[ASCII];
/*當(dāng)前結(jié)點(diǎn)的孩子結(jié)點(diǎn)不能匹配文本串中的某個(gè)字符時(shí),下一個(gè)應(yīng)該查找的結(jié)點(diǎn)*/
Node fail;
public Boolean isWord(){
return str != null;
}
}
/*target表示待查找的目標(biāo)字符串集合*/
public AhoCorasickAutomation(List 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];
}
/*將每個(gè)目標(biāo)字符串的最后一個(gè)字符對應(yīng)的結(jié)點(diǎn)變成終點(diǎn)*/
curr.str = targetStr;
}
}
/*由Trie樹構(gòu)建AC自動機(jī),本質(zhì)是一個(gè)自動機(jī),相當(dāng)于構(gòu)建KMP算法的next數(shù)組*/
private void build_AC_FromTrie(){
/*廣度優(yōu)先遍歷所使用的隊(duì)列*/
LinkedList queue = new LinkedList();
/*單獨(dú)處理根結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)*/
for (Node x : root.table){
if(x != null){
/*根結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)的fail都指向根結(jié)點(diǎn)*/
x.fail = root;
queue.addLast(x);
/*所有根結(jié)點(diǎn)的孩子結(jié)點(diǎn)入列*/
}
}
while(!queue.isEmpty()){
/*確定出列結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)的fail的指向*/
Node p = queue.removeFirst();
for (int i = 0; i < p.table.length; i++){
if(p.table[i] != null){
/*孩子結(jié)點(diǎn)入列*/
queue.addLast(p.table[i]);
/*從p.fail開始找起*/
Node failTo = p.fail;
while(true){
/*說明找到了根結(jié)點(diǎn)還沒有找到*/
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> find(String text){
/*創(chuàng)建一個(gè)表示存儲結(jié)果的對象*/
result = new HashMap>();
for (String s : target){
result.put(s, new LinkedList());
}
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);
}
/*這里很容易被忽視,因?yàn)橐粋€(gè)目標(biāo)串的中間某部分字符串可能正好包含另一個(gè)目標(biāo)字符串,
* 即使當(dāng)前結(jié)點(diǎn)不表示一個(gè)目標(biāo)字符串的終點(diǎn),但到當(dāng)前結(jié)點(diǎn)為止可能恰好包含了一個(gè)字符串*/
if(curr.fail != null && curr.fail.isWord()){
result.get(curr.fail.str).add(i - curr.fail.str.length()+1);
}
/*索引自增,指向下一個(gè)文本串中的字符*/
i++;
} else{
/*若不等,找到下一個(gè)應(yīng)該比較的狀態(tài)*/
curr = curr.fail;
/*到根結(jié)點(diǎn)還未找到,說明文本串中以ch作為結(jié)束的字符片段不是任何目標(biāo)字符串的前綴,
* 狀態(tài)機(jī)重置,比較下一個(gè)字符*/
if(curr == null){
curr = root;
i++;
}
}
}
return result;
}
public static void main(String[] args){
List target = new ArrayList();
target.add("abcdef");
target.add("abhab");
target.add("bcd");
target.add("cde");
target.add("cdfkcdf");
String text = "bcabcdebcedfabcdefababkabhabk";
AhoCorasickAutomation aca = new AhoCorasickAutomation(target);
HashMap> result = aca.find(text);
System.out.println(text);
for (Entry> entry : result.entrySet()){
System.out.println(entry.getKey()+" : " + entry.getValue());
}
}
} 運(yùn)行結(jié)果如下,從結(jié)果中我們可以看出文本串中bcd出現(xiàn)了二次,分別是文本串下標(biāo)為3和下標(biāo)為13的位置,……。
bcabcdebcedfabcdefababkabhabk bcd : [3, 13] cdfkcdf : [] cde : [4, 14] abcdef : [12] abhab : [23]
關(guān)于“java編程之AC自動機(jī)工作原理的示例分析”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯(cuò),請把它分享出去讓更多的人看到。