詳解Java中AC自動機的原理與實現
簡介
AC自動機是一個多模式匹配算法，在模式匹配領域被廣泛應用，舉一個經典的例子，違禁詞查找並替換為***。AC自動機其實是Trie樹和KMP 算法的結合,首先將多模式串建立一個Tire樹，然後結合KMP算法前綴與後綴匹配可以減少不必要比較的思想達到高效找到字符串中出現的匹配串。
如果不知道什麼是Tire樹，可以先查看：詳解Java中字典樹(Trie樹)的圖解與實現
如果不知道KMP算法，可以先查看：詳解Java中KMP算法的圖解與實現
工作過程
首先看一下AC自動機的結構，從造型上看，跟我們之前講Tire樹幾乎一樣，但是多瞭紅色線條（這裡因為畫完太亂，沒有畫完），這個紅色線條我們稱為失敗指針。其匹配規則與KMP一致，後綴和前綴的匹配，不一樣的是，KMP是同一個模式串的前綴和後綴進行匹配，而這裡是當前模式串的後綴，與另一個模式串的前綴進行匹配。如果能夠匹配上，因為這兩個模式串的前綴一定不同（相同的前綴已經聚合），將當前已匹配的後綴拿出來，比如abo，後綴為o，bo，abo，這時候我們再找另一個模式串的最長前綴與當前後綴匹配上（對應kmp中的最長前綴後綴子串），這時候我們可以找到out的o，則about中的o節點的失敗指針指向out的o節點，這麼做的意義就是主串可以一直往後比較，不用往前回溯（比如ab，之前匹配過能匹配上，但是到o是失敗瞭，其他匹配串不可能出現ab前綴，所以不必再匹配，一定失敗）。
構建過程：建立一棵Tire樹，結尾節點需要標志當前模式串的長度，構建失敗指針。
查找過程：從根節點出發，查找當前節點的孩子節點是否有與當前字符匹配的字符，匹配則判斷是否為尾節點，是則匹配成功，記錄。不是尾節點繼續匹配。如果孩子節點沒有與字符匹配的，則直接轉到失敗指針繼續操作。
數據結構
一個value記錄當前節點的值，childNode記錄當前節點的子節點（假設僅出現26個小寫字母，空間存在浪費，可使用hash表，有序二分，跳表進行優化），isTail標志當前節點是否為尾節點，failNode表示失敗指針，即當前節點的孩子節點與當前字符均不匹配的時候，轉到哪個節點接續進行匹配，tailLength，記錄模式串的長度，方便快速拿出模式串的值（根據長度以及匹配的index，從主串中拿）。
public static class Node{
//當前節點值
private char value;
//當前節點的孩子節點
private Node[] childNode;
//標志當前節點是否是某單詞結尾
private boolean isTail;
//失敗指針
private Node failNode;
//匹配串長度，當isTail==true時，表示從root當當前位置是一個完整的匹配串，記錄這個匹配串的長度，便於之後快速找到匹配串
private Integer tailLength;
public Node(char value) {
this.value = value;
}
}
初始化
初始化一棵僅存在root的根節點，root的失敗指針以及長度均為null。
Node root;
public void init() {
root = new Node('\0');
root.childNode = new Node[26];
}
構建字典樹
這個過程之前Tire樹中已經講過，不再贅述，唯一的區別是需要在結尾節點上標志當前模式串的長度。
public void insertStr(char[] chars) {
//首先判斷首字符是否已經在字典樹中，然後判斷第二字符，依次往下進行判斷，找到第一個不存在的字符進行插入孩節點
Node p = root;
//表明當前處理到瞭第幾個字符
int chIndex = 0;
while (chIndex < chars.length) {
while (chIndex < chars.length && null != p) {
Node[] children = p.childNode;
boolean find = false;
for (Node child : children) {
if (null == child) {continue;}
if (child.value == chars[chIndex]) {
//當前字符已經存在，不需要再進行存儲
//從當前節點出發，存儲下一個字符
p = child;
++ chIndex;
find = true;
break;
}
}
if (Boolean.TRUE.equals(find)) {
//在孩子中找到瞭 不用再次存儲
break;
}
//如果把孩子節點都找遍瞭，還沒有找到這個字符，直接將這個字符加入當前節點的孩子節點
Node node = new Node(chars[chIndex]);
node.childNode = new Node[26];
children[chars[chIndex] - 'a'] = node;
p = node;
++ chIndex;
}
}
//字符串中字符全部進入tire樹中後，將最後一個字符所在節點標志為結尾節點
p.isTail = true;
p.tailLength = chars.length;
}
構建失敗指針
從根節點開始層序遍歷樹結構，構建失敗指針。一個節點的子節點的失敗指針可以根據當前節點的失敗指針得到，因為我們是用後綴去與前綴匹配，所以如果我們采用層序遍歷，與當前後綴的前綴一定在上層，已經匹配出來瞭。那麼當前節點的子節點的失敗指針則可以根據當前節點的失敗指針，查找失敗指針指向的節點的子節點是否有與當前節點的子節點相等的，相等則這個子節點的失敗指針直接指向，不相等則繼續找，找不到直接指向root。根據上面的圖，我們來舉一個例子，我們已經找到about中o節點（o1）的失敗指針是out中的o節點（o2），接下來我們怎麼找u（u1）的失敗指針呢？首先根據o1的失敗指針我們找到瞭o2，o2的子節點為u（u2），恰好與我們u1的值相等，此時我們就可以將u1的失敗指針指向u2。以此類推，如果訪問到最後為空（root的失敗指針為空），則直接將失敗指針指向root。
public void madeFailNext() {
//層序遍歷，為瞭保證求解這個節點失敗指針的時候，它的父節點的失敗指針以及失敗指針的失敗指針。。。。已經求得，可以完全根據這個找
Deque<Node> nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
Node current = nodes.poll();
Node[] children = current.childNode;
for (Node child : children) {
if (null == child) {
continue;
}
Node failNode = current.failNode;
while (null != failNode) {
//找到當前節點的失敗指針，查看失敗指針子節點是否有==
Node[] failChildren = failNode.childNode;
Node node = failChildren[child.value - 'a'];
if (null == node) {
//找當前指針的下一個指針
failNode = failNode.failNode;
continue;
}
//已經找到匹配的
//將失敗指針指向node
child.failNode = node;
break;
}
//如果找完還沒有找到，指向root
if (null == failNode) {
child.failNode = root;
}
nodes.add(child);
}
}
}
匹配
從首字符，字典樹從root節點開始進行匹配，如果字符與節點值匹配，則判斷是否為尾字符，如果是匹配上一個違禁詞，記錄下來，如果不匹配則轉移到失敗指針繼續進行匹配。
/**
* 匹配出str中所有出現的關鍵詞
* @param str
* @return
*/
public List<String> match(String str) {
//遍歷當前子串串，從根節點出發，如果匹配就一直往下進行匹配，同時需要看匹配的節點是否為結尾節點，如果是，匹配上一個
//如果不匹配則通過失敗指針轉移到下一個節點
this.dfs(root, 0, str);
return machStr;
}
//abcdeasdabcebcd
List<String> machStr = new ArrayList<>();
private void dfs(Node node, int chIndex, String chars) {
if (chIndex >= chars.length()) {
return;
}
//從將當前字符與當前node的孩子節點進行匹配，如果當前字符與node的孩子節點.value匹配，判斷當前字符是否為尾節點，是，則記錄，匹配到瞭一個
//繼續匹配（子節點，與下一個元素進行匹配）
//如果不匹配，則轉到失敗指針
Node[] children = node.childNode;
Node child = children[chars.charAt(chIndex) - 'a'];
if (null == child) {
//不匹配，轉到失敗指針
//如果當前node==root，從root匹配，root的失敗指針是null
if (node == root) {
dfs(root, ++ chIndex, chars);
} else {
dfs(node.failNode, chIndex, chars);
}
} else {
//匹配到瞭
if (child.isTail) {
//並且是結尾節點，取從child.value到child.tailLength的字符
machStr.add(chars.substring(chIndex - child.tailLength + 1, chIndex + 1));
}
dfs(child, ++ chIndex, chars);
}
}
執行結果
public static void main(String[] args) {
ACAutomaton acAutomaton = new ACAutomaton();
//初始化一個僅有根節點的字典樹
acAutomaton.init();
//構建Tire樹
acAutomaton.insertStr("out".toCharArray());
acAutomaton.insertStr("about".toCharArray());
acAutomaton.insertStr("act".toCharArray());
//構建失敗指針
acAutomaton.madeFailNext();
System.out.println("ces");
//匹配
List<String> result = acAutomaton.match("abcdeasactdaboutcebcd");
}
到此這篇關於詳解Java中AC自動機的原理與實現的文章就介紹到這瞭,更多相關Java AC自動機內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- 詳解Java中字典樹(Trie樹)的圖解與實現
- java數據結構圖論霍夫曼樹及其編碼示例詳解
- Java數據結構之AC自動機算法的實現
- 詳解Java實現拓撲排序算法
- Java實現單鏈表SingleLinkedList增刪改查及反轉 逆序等