java編程之AC自動機工作原理與實現(xiàn)代碼
在閱讀本文之前，大家可以先參考下《多模字符串匹配算法原理及Java實現(xiàn)代碼》
簡介：
本文是博主自身對AC自動機的原理的一些理解和看法，主要以舉例的方式講解，同時又配以相應的圖片。代碼實現(xiàn)部分也予以明確的注釋，希望給大家不一樣的感受。AC自動機主要用于多模式字符串的匹配，本質上是KMP算法的樹形擴展。這篇文章主要介紹AC自動機的工作原理，并在此基礎上用Java代碼實現(xiàn)一個簡易的AC自動機。
1.應用場景—多模字符串匹配
我們現(xiàn)在考慮這樣一個問題，在一個文本串text中，我們想找出多個目標字符串target1,target2,……出現(xiàn)的次數(shù)和位置。例如：求出目標字符串集合{"nihao","hao","hs","hsr"}在給定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出現(xiàn)的位置。解決這個問題，我們一般的辦法就是在文本串中對每個目標字符串單獨查找，并記錄下每次出現(xiàn)的位置。顯然這樣的方式能夠解決問題，但是在文本串較大、目標字符串眾多的時候效率比較低。為了提高效率，貝爾實驗室于1975年發(fā)明著名的多模字符串匹配算法——AC自動機。AC自動機在實現(xiàn)上要依托于Trie樹（也稱字典樹）并借鑒了KMP模式匹配算法的核心思想。實際上你可以把KMP算法看成每個節(jié)點都僅有一個孩子節(jié)點的AC自動機。
AC自動機用于多模匹配，所謂多模匹配，就是給定一個帶匹配的字符串string，給定一個字典dictionary，dictionary中有多個字符串{ str1,str2, str3 … } 多模匹配就是要得到string字符串中出現(xiàn)了dictionary的哪些字符，且這些字符出現(xiàn)在了string中的哪個位置。
2.AC自動機及其運行原理
2.1初識AC自動機
AC自動機的基礎是Trie樹。和Trie樹不同的是，樹中的每個結點除了有指向孩子的指針（或者說引用），還有一個fail指針，它表示輸入的字符與當前結點的所有孩子結點都不匹配時(注意，不是和該結點本身不匹配)，自動機的狀態(tài)應轉移到的狀態(tài)（或者說應該轉移到的結點）。fail指針的功能可以類比于KMP算法中next數(shù)組的功能。
我們現(xiàn)在來看一個用目標字符串集合{abd,abdk,abchijn,chnit,ijabdf,ijaij}構造出來的AC自動機
上圖是一個構建好的AC自動機，其中根結點不存儲任何字符，根結點的fail指針為null。虛線表示該結點的fail指針的指向，所有表示字符串的最后一個字符的結點外部都用紅圈表示，我們稱該結點為這個字符串的終結結點。每個結點實際上都有fail指針，但為了表示方便，本文約定一個原則，即所有指向根結點的fail虛線都未畫出。
從上圖中的AC自動機，我們可以看出一個重要的性質：每個結點的fail指針表示由根結點到該結點所組成的字符序列的所有后綴和整個目標字符串集合（也就是整個Trie樹）中的所有前綴兩者中最長公共的部分。
比如圖中，由根結點到目標字符串“ijabdf”中的‘d'組成的字符序列“ijabd”的所有后綴在整個目標字符串集{abd,abdk,abchijn,chnit,ijabdf,ijaij}的所有前綴中最長公共的部分就是abd，而圖中d結點（字符串“ijabdf”中的這個d）的fail正是指向了字符序列abd的最后一個字符。
2.2AC自動機的運行過程：
1）表示當前結點的指針指向AC自動機的根結點，即curr=root
2）從文本串中讀?。ㄏ拢┮粋€字符
3）從當前結點的所有孩子結點中尋找與該字符匹配的結點，
若成功：判斷當前結點以及當前結點fail指向的結點是否表示一個字符串的結束，若是，則將文本串中索引起點記錄在對應字符串保存結果集合中（索引起點=當前索引-字符串長度+1）。curr指向該孩子結點，繼續(xù)執(zhí)行第2步
若失?。簣?zhí)行第4步。
4）若fail==null（說明目標字符串中沒有任何字符串是輸入字符串的前綴，相當于重啟狀態(tài)機）curr=root,執(zhí)行步驟2，
否則，將當前結點的指針指向fail結點，執(zhí)行步驟3)
現(xiàn)在，我們來一個具體的例子加深理解，初始時當前結點為root結點，我們現(xiàn)在假設文本串text=“abchnijabdfk”。
圖中的實曲線表示了整個搜索過程中的當前結點指針的轉移過程，結點旁的文字表示了當前結點下讀取的文本串字符。比如初始時，當前指針指向根結點時，輸入字符‘a(chǎn)',則當前指針指向結點a，此時再輸入字符‘b',自動機狀態(tài)轉移到結點b,……，以此類推。圖中AC自動機的最后狀態(tài)只是恰好回到根結點。
需要說明的是，當指針位于結點b（圖中曲線經(jīng)過了兩次b,這里指第二次的b，即目標字符串“ijabdf”中的b）,這時讀取文本串字符下標為9的字符（即‘d'）時，由于b的所有孩子結點（這里恰好只有一個孩子結點）中存在能夠匹配輸入字符d的結點,那么當前結點指針就指向了結點d，而此時該結點d的fail指針指向的結點又恰好表示了字符串“abc”的終結結點（用紅圈表示），所以我們找到了目標字符串“abc”一次。這個過程我們在圖中用虛線表示，但狀態(tài)沒有轉移到“abd”中的d結點。
在輸入完所有文本串字符后，我們在文本串中找到了目標字符串集合中的abd一次，位于文本串中下標為7的位置；目標字符串ijabdf一次，位于文本串中下標為5的位置。
3.構造AC自動機的方法與原理
3.1構造的基本方法
首先我們將所有的目標字符串插入到Trie樹中，然后通過廣度優(yōu)先遍歷為每個結點的所有孩子節(jié)點的fail指針找到正確的指向。
確定fail指針指向的問題和KMP算法中構造next數(shù)組的方式如出一轍。具體方法如下
1）將根結點的所有孩子結點的fail指向根結點，然后將根結點的所有孩子結點依次入列。
2）若隊列不為空：
2.1）出列，我們將出列的結點記為curr,failTo表示curr的fail指向的結點，即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)
若隊列為空:結束
3.2通過一個例子來理解構造AC自動機的原理
每個結點fail指向的解決順序是按照廣度優(yōu)先遍歷的順序完成的，或者說層序遍歷的順序進行的，也就是說我們是在解決當前結點的孩子結點fail的指向時，當前結點的fail指針一定已指向了正確的位置。
為了說明問題，我們再次強調“每個結點的fail指針表示：由根結點到該結點所組成的字符序列的所有后綴和整個目標字符串集合（也就是整個Trie樹）中的所有前綴兩者中最長公共的部分”。
以上圖所示為例，我們要解決結點x1的某個孩子結點y的fail的指向問題。已知x1.fail指向x2，依據(jù)x1結點的fail指針的含義，我們可知紅色實線橢圓框內的字符序列必然相等，且表示了最長公共部分。依據(jù)y.fail的含義，如果x2的某個孩子結點和結點y表示的字符相等，那么y.fail就該指向它。
如果x2的孩子結點中不存在結點y表示的字符，這個時候該怎么辦？由于x2.fail指向x3，根據(jù)x2.fail的含義，我們可知綠色方框內的字符序列必然相等。顯然，如果x3的某個孩子結點和結點y表示的字符相等，那么y.fail就該指向它。
如果x3的孩子結點中不存在結點y表示的字符，我們可以依次重復這個步驟，直到xi結點的fail指向null，這時說明我們已經(jīng)到了最頂層的根結點，這時，我們只需要讓ｙ.fail=root即可。
構造的過程的核心本質就是，已知當前結點的最長公共前綴的前提下，去確定孩子結點的最長公共前綴。這完全可以類比于KMP算法的next數(shù)組的求解過程。
3.2.1確定圖中h結點fail指向的過程
現(xiàn)在我們假設我們要確定圖中結點c的孩子結點h的fail指向。圖中每個結點都應該有表示fail的虛線，但為了表示方便，按照本文約定的原則，所有指向根結點的fail虛線均未畫出。
左圖表示h.fail確定之前， 右圖表示h.fail確定之后
左圖中，藍色實線框住的結點的fail都已確定。現(xiàn)在我們應該怎樣找到h.fail的正確指向？由于且結點c的fail已知（c結點為h結點的父結點），且指向了Trie樹中所有前綴與字符序列‘a(chǎn)'‘b'‘c'的所有后綴（“bc”和“c”）的最長公共部分。現(xiàn)在我們要解決的問題是目標字符串集合的所有前綴中與字符序列‘a(chǎn)'‘b'‘c'‘h'的所有后綴的最長公共部分。顯然c.fail指向的結點的孩子結點中存在結點h，那么h.fail就應該指向c.fail的孩子結點h，所以右圖表示了h.fail確定后的情況。
3.2.2確定圖中i.fail指向的過程
左圖表示i.fail確定之前， 右圖表示i.fail確定之后
確定i.fail的指向時，顯然h.fail(h指圖中i的父結點的那個h)已指向了正確的位置。也就是說我們現(xiàn)在知道了目標字符串集合所有前綴中與字符序列‘a(chǎn)'‘b'‘c'‘h'的所有后綴在Trie樹中的最長前綴是‘c'‘h'。顯然從圖中可知h.fail的孩子結點是沒有i結點（這里h.fail只有一個孩子結點n）。字符序列‘c'‘h'的所有后綴在Trie樹中的最長前綴可由h.fail的fail得到，而h.fail的fail指向root（依據(jù)本博客中畫圖的原則，這條fail虛線并未畫出）,root的孩子結點中存在表示字符i的結點,所以結果如右圖所示。
在知道i.fail的情況下，大家可以嘗試在紙上畫出j.fail的指向，以加深AC自動機構造過程的理解。
4.AC自動機的java代碼實現(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自動機只處理英文類型的字符串，所以數(shù)組的長度是128*/
private static final int ASCII = 128;
/*AC自動機的根結點，根結點不存儲任何字符信息*/
private Node root;
/*待查找的目標字符串集合*/
private List<String> target;
/*表示在文本字符串中查找的結果，key表示目標字符串， value表示目標字符串在文本串出現(xiàn)的位置*/
private HashMap<String, List<Integer>> result;
/*內部靜態(tài)類，用于表示AC自動機的每個結點，在每個結點中我們并沒有存儲該結點對應的字符*/
private static class Node{
/*如果該結點是一個終點，即，從根結點到此結點表示了一個目標字符串，則str != null, 且str就表示該字符串*/
String str;
/*ASCII == 128, 所以這里相當于128叉樹*/
Node[] table = new Node[ASCII];
/*當前結點的孩子結點不能匹配文本串中的某個字符時，下一個應該查找的結點*/
Node fail;
public Boolean isWord(){
return str != null;
}
}
/*target表示待查找的目標字符串集合*/
public AhoCorasickAutomation(List<String> target){
root = new Node();
this.target = target;
buildTrieTree();
build_AC_FromTrie();
}
/*由目標字符串構建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];
}
/*將每個目標字符串的最后一個字符對應的結點變成終點*/
curr.str = targetStr;
}
}
/*由Trie樹構建AC自動機，本質是一個自動機，相當于構建KMP算法的next數(shù)組*/
private void build_AC_FromTrie(){
/*廣度優(yōu)先遍歷所使用的隊列*/
LinkedList<Node> queue = new LinkedList<Node>();
/*單獨處理根結點的所有孩子結點*/
for (Node x : root.table){
if(x != null){
/*根結點的所有孩子結點的fail都指向根結點*/
x.fail = root;
queue.addLast(x);
/*所有根結點的孩子結點入列*/
}
}
while(!queue.isEmpty()){
/*確定出列結點的所有孩子結點的fail的指向*/
Node p = queue.removeFirst();
for (int i = 0; i < p.table.length; i++){
if(p.table[i] != null){
/*孩子結點入列*/
queue.addLast(p.table[i]);
/*從p.fail開始找起*/
Node failTo = p.fail;
while(true){
/*說明找到了根結點還沒有找到*/
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;
}
}
}
}
}
}
/*在文本串中查找所有的目標字符串*/
public HashMap<String, List<Integer>> find(String text){
/*創(chuàng)建一個表示存儲結果的對象*/
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自動機中的字符進行比較*/
if(curr.table[ch] != null){
/*若相等，自動機進入下一狀態(tài)*/
curr = curr.table[ch];
if(curr.isWord()){
result.get(curr.str).add(i - curr.str.length()+1);
}
/*這里很容易被忽視，因為一個目標串的中間某部分字符串可能正好包含另一個目標字符串，
* 即使當前結點不表示一個目標字符串的終點，但到當前結點為止可能恰好包含了一個字符串*/
if(curr.fail != null && curr.fail.isWord()){
result.get(curr.fail.str).add(i - curr.fail.str.length()+1);
}
/*索引自增，指向下一個文本串中的字符*/
i++;
} else{
/*若不等，找到下一個應該比較的狀態(tài)*/
curr = curr.fail;
/*到根結點還未找到，說明文本串中以ch作為結束的字符片段不是任何目標字符串的前綴，
* 狀態(tài)機重置，比較下一個字符*/
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());
}
}
}
運行結果如下，從結果中我們可以看出文本串中bcd出現(xiàn)了二次，分別是文本串下標為3和下標為13的位置，……。
bcabcdebcedfabcdefababkabhabk bcd : [3, 13] cdfkcdf : [] cde : [4, 14] abcdef : [12] abhab : [23]
總結
以上就是本文關于java編程之AC自動機工作原理與實現(xiàn)代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：
如有不足之處，歡迎留言指出。
相關文章
這篇文章主要介紹了IDEA 必要配置設置方式,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-04-04
我們都知道java語言與C語言最大的區(qū)別就是內存自動回收，那么JVM是怎么控制內存回收的，這篇文章將介紹JVM垃圾回收的幾種算法，從而了解內存回收的基本原理2021-06-06
關于SpringSecurity?Context?中獲取和更改當前用戶信息的問題
SpringSecurityContext在異步線程中無法獲取用戶信息,因其與請求線程綁定；此外,用戶信息更新后跳轉頁面時,身份會被降級為匿名,導致信息無法及時同步,本文給大家介紹SpringSecurity?Context?中獲取和更改當前用戶信息的問題,感興趣的朋友一起看看吧2024-09-09
Kafka多節(jié)點分布式集群搭建實現(xiàn)過程詳解
這篇文章主要介紹了Kafka多節(jié)點分布式集群搭建實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
Arrays類中有一個sort()方法，該方法是Arrays類的靜態(tài)方法，在需要對數(shù)組進行排序時，非常的好用。但是sort()的參數(shù)有好幾種，下面我就為大家一一介紹，這幾種形式的用法2022-08-08
詳解Java并發(fā)工具類之CountDownLatch和CyclicBarrier
在JDK的并發(fā)包中，有幾個非常有用的并發(fā)工具類，它們分別是：CountDownLatch、CyclicBarrier、Semaphore和Exchanger,本文主要來講講其中CountDownLatch和CyclicBarrier的使用，感興趣的可以了解一下2023-06-06
解決子線程無法訪問父線程中通過ThreadLocal設置的變量問題
這篇文章主要介紹了解決子線程無法訪問父線程中通過ThreadLocal設置的變量問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07
本文主要介紹Java中Mybatis的二級緩存，緩存就是一塊內存空間，保存臨時數(shù)據(jù)，它是SqlSessionFactory的緩存，對Mybaits感興趣的小伙伴可以參考閱讀2023-03-03
淺談 java中ArrayList、Vector、LinkedList的區(qū)別聯(lián)系
ArrayList,Vector底層是由數(shù)組實現(xiàn)，LinkedList底層是由雙線鏈表實現(xiàn)，從底層的實現(xiàn)可以得出性能問題ArrayList,Vector插入速度較慢，查詢速度較快，而LinkedList插入速度較快,而查詢速度較慢。再者由于Vevtor使用了線程安全鎖，所以ArrayList的運行效率高于Vector2015-11-11
這篇文章主要為大家分享了如何利用Java語言實現(xiàn)PDF文件的分割與加密以及封面圖的生成，文中的示例代碼簡潔易懂，感興趣的可以了解一下2022-04-04