本篇內容主要講解“Java數據結構之AC自動機算法如何實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java數據結構之AC自動機算法如何實現”吧!
一般的字符串匹配算法都是匹配一個子串，例如KMP、Trie，那么如果同時匹配多個子串呢？此時就需要用到AC自動機了。
AC自動機算法是一個多模式字符串匹配算法，在模式匹配領域被廣泛應用，例如違禁詞查找替換、搜索關鍵詞查找等等。
關于Trie樹和KMP算法，我們此前已經講解過了：
前綴樹Trie的實現原理以及Java代碼的實現
KMP算法詳解以及Java代碼實現
AC自動機算法常被認為是Trie樹+KMP算法的結合體，為什么呢？我們先看看它的構建步驟：
對所有的關鍵詞構建Trie前綴樹。
為Trie樹上的所有節點構建fail失配指針。
第一步，對所有的關鍵詞構建Trie前綴樹。這一步利用Trie的特點構建快速前綴查找結構，trie樹的特點是可以從字符串頭部開始匹配，并且相同前綴的詞共用前面的節點，因此它可以避免相同前綴pattern的重復匹配，但是對于相同的后綴無能為力。
第二步，為Trie樹上的所有節點構建fail失配指針，即匹配失敗后應該跳到哪個節點。所謂節點的失配指針，就是指向當前字符串最長真后綴位置的指針節點。這里需要理解KMP的next數組的概念，這一步就是利用KMP前后綴匹配的思想實現關鍵詞前綴失配時利用相同的后綴信息快速跳轉到另一個關鍵詞繼續前綴匹配。他們的區別是：
在KMP算法中，是針對單個關鍵詞匹配，求出的最長匹配長度的前綴和后綴都位于同一個關鍵詞內。例如關鍵詞abcdabc，最長匹配前后綴，為abc，他們屬于該關鍵詞。
在AC自動機算法中，是針對多個關鍵詞匹配，求出的最長匹配長度的前綴和后綴分別屬于不同的關鍵詞的前綴和后綴。
例如兩個關鍵詞dabab，ababd，那么關鍵詞dabab中第二個b位置的失敗指針應該指向關鍵詞ababd中的第二個b。即dabab的后綴與ababd的前綴能夠匹配的最長子串為abab。
在這里，我們給出一個比較簡單的節點的定義。
next，表示經過該節點的模式串的下層節點，這是Trie樹結構的保證，存儲著子節點的值到對應的節點的映射關系。
depth，表示以當前即誒單結尾的模式串的長度，也是節點的深度，默認為0。
failure，失配指針，其指向表示另一個關鍵詞前綴的最長后綴節點，如果當前節點沒有匹配到，則跳轉到此節點繼續匹配。如果當前節點匹配到了，那么可以通過此指針找到該節點的模式串包含的最長后綴模式串。
class AcNode {
/**
* 經過該節點的模式串的下層節點
*/
Map<Character, AcNode> next = new HashMap<>();
/**
* 模式串的長度，也是節點的深度
*/
int depth;
/**
* 失配指針，如果沒有匹配到，則跳轉到此狀態。
*/
AcNode failure;
public boolean hashNext(char nextKey) {
return next.containsKey(nextKey);
}
public AcNode getNext(char nextKey) {
return next.get(nextKey);
}
}構建Ac自動機的Trie的方法和構建普通Trie的方法幾乎一致。在添加每個模式串成功后，會為最后一個節點的depth賦值為當前模式串的長度。
/**
* trie根節點
*/
private AcNode root;
/**
* 加入模式串，構建Trie
*
* @param word 模式串，非空
*/
public void insert(String word) {
AcNode cur = root;
for (char c : word.toCharArray()) {
if (!cur.next.containsKey(c)) {
cur.next.put(c, new AcNode());
}
cur = cur.next.get(c);
}
cur.depth = word.length();
}構建fail失配指針的一種常見的方法如下，實際上是一個BFS層序遍歷的算法：
1.Trie的root節點沒有失配指針，或者說失配指針為null，其他節點都有失配指針，或者說不為null。
2.遍歷root節點的所有下一層直接子節點，將它們的失配指針設置為root。因為這些節點代表著所有模式串的第一個字符，基于KMP的next數組定義，單個字符沒有最長真后綴，此時直接指向root。
3.繼續循環向下遍歷每一層的子節點，由于bfs的遍歷，那么上一層父節點的失配指針肯定都已經確定了?；趎ext數組的構建思想，子節點的失配指針可以通過父節點的是失配指針快速推導出來。設當前遍歷的節點為c，它的父節點為p，父節點的失配指針為pf。
如果pf節點的子節點對應的字符中，包含了當前節點的所表示的字符。那么基于求最長后綴的原理，此時c節點的失配指針可以直接指向pf節點下的相同字符對應的子節點。
如果pf節點的子節點對應的字符中，沒有包含了當前節點的所表示的字符。那么繼續獲取pf節點的失配指針節點，繼續重復判斷。直到滿足第一種情況，或者pf指向了根節點，并且根節點的子節點也沒有匹配，那么此時直接將c節點的失配指針指向根節點。
/**
* 為所有節點構建失配指針，一個bfs層序遍歷
*/
public void buildFailurePointer() {
ArrayDeque<AcNode> queue = new ArrayDeque<AcNode>();
//將所有root的直接子節點的failure設置為root，并且加入queue
for (AcNode acNode : root.next.values()) {
acNode.failure = root;
queue.addLast(acNode);
}
//bfs構建失配指針
while (!queue.isEmpty()) {
//父節點出隊列
AcNode parent = queue.pollFirst();
//遍歷父節點的下層子節點，基于父節點求子節點的失配指針
for (Map.Entry<Character, AcNode> characterAcNodeEntry : parent.next.entrySet()) {
//獲取父節點的失配指針
AcNode pf = parent.failure;
//獲取子節點
AcNode child = characterAcNodeEntry.getValue();
//獲取子節點對應的字符
Character nextKey = characterAcNodeEntry.getKey();
//如果pf節點不為null，并且pf節點的子節點對應的字符中，沒有包含了當前節點的所表示的字符
while (pf != null && !pf.hashNext(nextKey)) {
//繼續獲取pf節點的失配指針節點，繼續重復判斷
pf = pf.failure;
}
//pf為null，表示找到了根節點，并且根節點的子節點也沒有匹配
if (pf == null) {
//此時直接將節點的失配指針指向根節點
child.failure = root;
}
//pf節點的子節點對應的字符中，包含了當前節點的所表示的字符
else {
//節點的失配指針可以直接指向pf節點下的相同字符對應的子節點
child.failure = pf.getNext(nextKey);
}
//最后不要忘了，將當前節點加入隊列
queue.addLast(child);
}
}
}構建完AC自動機之后，下面我們需要進行文本的匹配，匹配的方式實際上比較簡單。
1.遍歷文本的每個字符，依次匹配，從Trie的根節點作為cur節點開始匹配：
2.將當前字符作為nextKey，如果cur節點不為null且節點的next映射中不包含nextKey，那么當前cur節點指向自己的failure失配指針。
3.如果cur節點為null，說明當前字符匹配到了root根節點且失敗，那么cur設置為root繼續從根節點開始進行下一輪匹配。
4.否則表示匹配成功的節點，cur指向匹配節點，獲取該節點繼續判斷：
如果該節點是某個關鍵詞的結尾，那么取出來，也就是depth不為0，那么表示匹配到了一個關鍵詞。
繼續判斷該節點的失配指針節點表示的模式串。因為失配指針節點表示的模式串是當前匹配的模式串的在這些關鍵詞中的最長后綴，且由于當前節點的路徑包括了失配指針的全部路徑，并且失配指針路徑也是一個完整的關鍵詞，需要找出來。
/**
* 匹配文本
*
* @param text 文本字符串
*/
public List<ParseResult> parseText(String text) {
List<ParseResult> parseResults = new ArrayList<>();
char[] chars = text.toCharArray();
//從根節點開始匹配
AcNode cur = root;
//遍歷字符串的每個字符
for (int i = 0; i < chars.length; i++) {
//當前字符
char nextKey = chars[i];
//如果cur不為null，并且當前節點的的子節點不包括當前字符，即不匹配
while (cur != null && !cur.hashNext(nextKey)) {
//那么通過失配指針轉移到下一個節點繼續匹配
cur = cur.failure;
}
//如果節點為null，說明當前字符匹配到了根節點且失敗
//那么繼續從根節點開始進行下一輪匹配
if (cur == null) {
cur = root;
} else {
//匹配成功的節點
cur = cur.getNext(nextKey);
//繼續判斷
AcNode temp = cur;
while (temp != null) {
//如果當前節點是某個關鍵詞的結尾，那么取出來
if (temp.depth != 0) {
int start = i - temp.depth + 1, end = i;
parseResults.add(new ParseResult(start, end, new String(chars, start, temp.depth)));
//System.out.println(start + " " + end + " " + new String(chars, start, temp.depth));
}
//繼續判斷該節點的失配指針節點
//因為失配指針節點表示的模式串是當前匹配的模式串的在這些關鍵詞中的最長后綴，且由于當前節點的路徑包括了失配指針的全部路徑
//并且失配指針路徑也是一個完整的關鍵詞，需要找出來。
temp = temp.failure;
}
}
}
return parseResults;
}
class ParseResult {
int startIndex;
int endIndex;
String key;
public ParseResult(int startIndex, int endIndex, String key) {
this.startIndex = startIndex;
this.endIndex = endIndex;
this.key = key;
}
@Override
public String toString() {
return "{" +
"startIndex=" + startIndex +
", endIndex=" + endIndex +
", key='" + key + '\'' +
'}';
}
}基于上面的方法，假如關鍵詞為：he、shes、shers、hes、h、e，那么最終構建的AC自動機的結構如下（紅色圈表示某個關鍵詞的結束位置）。
假如我們的文本為sheshe，那么我們來看看AC自動機匹配的過程：
遍歷文本，cur首先指向root。
nextKey=s，cur.next包含s，表示這是一個匹配成功的節點，那么獲取到該節點s，cur=s，s不是某個關鍵詞的結尾，failure節點也不包含模式串，那么查找完畢進行下一輪。
nextKey=h，cur=s，cur.next包含h，表示這是一個匹配成功的節點，那么獲取到該節點h，cur=h，h節點不是某個關鍵詞的結尾，但是它的failure節點包含模式串h，因此找到了第1個匹配的關鍵詞h，查找完畢后進行下一輪。
nextKey=e，cur=h，cur.next包含e，表示這是一個匹配成功的節點，那么獲取到該節點e，cur=e，e節點不是某個關鍵詞的結尾，但是它的failure節點包含模式串he，因此找到了第2個匹配的關鍵詞he。
而fuilure節點e又包含另一個模式串e，因此找到了第3個匹配的關鍵詞e，查找完畢后進行下一輪。
nextKey=s，cur=e，cur.next包含s，表示這是一個匹配成功的節點，那么獲取到該節點e，cur=e，s節點是關鍵詞shes的結尾，因此找到了第4個匹配的關鍵詞shes。
繼續判斷s的failure，它的failure節點包含模式串hes，因此找到了第5個匹配的關鍵詞hes，查找完畢后進行下一輪。
nextKey=h，cur=s，cur.next不包含h，表示這是一個匹配失敗的節點，那么繼續匹配它的failure節點，經過s-s-s的匹配，最終匹配到子節點h。
該節點h并不是關鍵詞的結尾，但是h的failure，它的failure節點包含模式串h，因此找到了第6個匹配的關鍵詞h，查找完畢后進行下一輪。
nextKey=e，cur=h，cur.next包含e，表示這是一個匹配成功的節點，那么獲取到該節點e，cur=e，e節點不是某個關鍵詞的結尾，但是它的failure節點包含模式串he，因此找到了第7個匹配的關鍵詞he。
而fuilure節點e又包含另一個模式串e，因此找到了第8個匹配的關鍵詞e。
到此字符串遍歷完畢，查找完畢！
最終文本sheshe，匹配到關鍵詞如下：
[{startIndex=1, endIndex=1, key='h'}, {startIndex=1, endIndex=2, key='he'},
{startIndex=2, endIndex=2, key='e'}, {startIndex=0, endIndex=3, key='shes'},
{startIndex=1, endIndex=3, key='hes'}, {startIndex=4, endIndex=4, key='h'},
{startIndex=4, endIndex=5, key='he'}, {startIndex=5, endIndex=5, key='e'}]
到此，相信大家對“Java數據結構之AC自動機算法如何實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
