快捷導(dǎo)航

詳解Java中AC自動機的原理與實現(xiàn)

更新時間：2022年05月14日 09:16:03 作者：Carol

AC自動機是一個多模式匹配算法，在模式匹配領(lǐng)域被廣泛應(yīng)用。本文將詳細為大家介紹AC自動機的原理與實現(xiàn)方法，感興趣的可以了解一下

簡介

AC自動機是一個多模式匹配算法，在模式匹配領(lǐng)域被廣泛應(yīng)用，舉一個經(jīng)典的例子，違禁詞查找并替換為***。AC自動機其實是Trie樹和KMP 算法的結(jié)合,首先將多模式串建立一個Tire樹，然后結(jié)合KMP算法前綴與后綴匹配可以減少不必要比較的思想達到高效找到字符串中出現(xiàn)的匹配串。

如果不知道什么是Tire樹，可以先查看：詳解Java中字典樹(Trie樹)的圖解與實現(xiàn)

如果不知道KMP算法，可以先查看：詳解Java中KMP算法的圖解與實現(xiàn)

工作過程

首先看一下AC自動機的結(jié)構(gòu)，從造型上看，跟我們之前講Tire樹幾乎一樣，但是多了紅色線條（這里因為畫完太亂，沒有畫完），這個紅色線條我們稱為失敗指針。其匹配規(guī)則與KMP一致，后綴和前綴的匹配，不一樣的是，KMP是同一個模式串的前綴和后綴進行匹配，而這里是當(dāng)前模式串的后綴，與另一個模式串的前綴進行匹配。如果能夠匹配上，因為這兩個模式串的前綴一定不同（相同的前綴已經(jīng)聚合），將當(dāng)前已匹配的后綴拿出來，比如abo，后綴為o，bo，abo，這時候我們再找另一個模式串的最長前綴與當(dāng)前后綴匹配上（對應(yīng)kmp中的最長前綴后綴子串），這時候我們可以找到out的o，則about中的o節(jié)點的失敗指針指向out的o節(jié)點，這么做的意義就是主串可以一直往后比較，不用往前回溯（比如ab，之前匹配過能匹配上，但是到o是失敗了，其他匹配串不可能出現(xiàn)ab前綴，所以不必再匹配，一定失?。?。

構(gòu)建過程：建立一棵Tire樹，結(jié)尾節(jié)點需要標志當(dāng)前模式串的長度，構(gòu)建失敗指針。

查找過程：從根節(jié)點出發(fā)，查找當(dāng)前節(jié)點的孩子節(jié)點是否有與當(dāng)前字符匹配的字符，匹配則判斷是否為尾節(jié)點，是則匹配成功，記錄。不是尾節(jié)點繼續(xù)匹配。如果孩子節(jié)點沒有與字符匹配的，則直接轉(zhuǎn)到失敗指針繼續(xù)操作。

數(shù)據(jù)結(jié)構(gòu)

一個value記錄當(dāng)前節(jié)點的值，childNode記錄當(dāng)前節(jié)點的子節(jié)點（假設(shè)僅出現(xiàn)26個小寫字母，空間存在浪費，可使用hash表，有序二分，跳表進行優(yōu)化），isTail標志當(dāng)前節(jié)點是否為尾節(jié)點，failNode表示失敗指針，即當(dāng)前節(jié)點的孩子節(jié)點與當(dāng)前字符均不匹配的時候，轉(zhuǎn)到哪個節(jié)點接續(xù)進行匹配，tailLength，記錄模式串的長度，方便快速拿出模式串的值（根據(jù)長度以及匹配的index，從主串中拿）。

public?static?class?Node{
? ? ? ?//當(dāng)前節(jié)點值
? ? ? ?private?char?value;
? ? ? ?//當(dāng)前節(jié)點的孩子節(jié)點
? ? ? ?private?Node[]?childNode;
? ? ? ?//標志當(dāng)前節(jié)點是否是某單詞結(jié)尾
? ? ? ?private?boolean?isTail;
? ? ? ?//失敗指針
? ? ? ?private?Node?failNode;
? ? ? ?//匹配串長度，當(dāng)isTail==true時，表示從root當(dāng)當(dāng)前位置是一個完整的匹配串，記錄這個匹配串的長度，便于之后快速找到匹配串
? ? ? ?private?Integer?tailLength;
? ? ? ?public?Node(char?value) {
? ? ? ? ? ?this.value?=?value;
? ? ? }
? }

初始化

初始化一棵僅存在root的根節(jié)點，root的失敗指針以及長度均為null。

Node?root;
? ?public?void?init() {
? ? ? ?root?=?new?Node('\0');
? ? ? ?root.childNode?=?new?Node[26];
? }

構(gòu)建字典樹

這個過程之前Tire樹中已經(jīng)講過，不再贅述，唯一的區(qū)別是需要在結(jié)尾節(jié)點上標志當(dāng)前模式串的長度。

public?void?insertStr(char[]?chars) {
? ? ? ?//首先判斷首字符是否已經(jīng)在字典樹中，然后判斷第二字符，依次往下進行判斷，找到第一個不存在的字符進行插入孩節(jié)點
? ? ? ?Node?p?=?root;
? ? ? ?//表明當(dāng)前處理到了第幾個字符
? ? ? ?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]) {
? ? ? ? ? ? ? ? ? ? ? ?//當(dāng)前字符已經(jīng)存在，不需要再進行存儲
? ? ? ? ? ? ? ? ? ? ? ?//從當(dāng)前節(jié)點出發(fā)，存儲下一個字符
? ? ? ? ? ? ? ? ? ? ? ?p?=?child;
? ? ? ? ? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? ? ? ? ? ? ? ?find?=?true;
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?if?(Boolean.TRUE.equals(find)) {
? ? ? ? ? ? ? ? ? ?//在孩子中找到了 不用再次存儲
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果把孩子節(jié)點都找遍了，還沒有找到這個字符，直接將這個字符加入當(dāng)前節(jié)點的孩子節(jié)點
? ? ? ? ? ? ? ?Node?node?=?new?Node(chars[chIndex]);
? ? ? ? ? ? ? ?node.childNode?=?new?Node[26];
? ? ? ? ? ? ? ?children[chars[chIndex]?-?'a']?=?node;
? ? ? ? ? ? ? ?p?=?node;
? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? }
? ? ? }
? ? ? ?//字符串中字符全部進入tire樹中后，將最后一個字符所在節(jié)點標志為結(jié)尾節(jié)點
? ? ? ?p.isTail?=?true;
? ? ? ?p.tailLength?=?chars.length;
? }

構(gòu)建失敗指針

從根節(jié)點開始層序遍歷樹結(jié)構(gòu)，構(gòu)建失敗指針。一個節(jié)點的子節(jié)點的失敗指針可以根據(jù)當(dāng)前節(jié)點的失敗指針得到，因為我們是用后綴去與前綴匹配，所以如果我們采用層序遍歷，與當(dāng)前后綴的前綴一定在上層，已經(jīng)匹配出來了。那么當(dāng)前節(jié)點的子節(jié)點的失敗指針則可以根據(jù)當(dāng)前節(jié)點的失敗指針，查找失敗指針指向的節(jié)點的子節(jié)點是否有與當(dāng)前節(jié)點的子節(jié)點相等的，相等則這個子節(jié)點的失敗指針直接指向，不相等則繼續(xù)找，找不到直接指向root。根據(jù)上面的圖，我們來舉一個例子，我們已經(jīng)找到about中o節(jié)點（o1）的失敗指針是out中的o節(jié)點（o2），接下來我們怎么找u（u1）的失敗指針呢？首先根據(jù)o1的失敗指針我們找到了o2，o2的子節(jié)點為u（u2），恰好與我們u1的值相等，此時我們就可以將u1的失敗指針指向u2。以此類推，如果訪問到最后為空（root的失敗指針為空），則直接將失敗指針指向root。

public?void?madeFailNext() {
? ? ? ?//層序遍歷，為了保證求解這個節(jié)點失敗指針的時候，它的父節(jié)點的失敗指針以及失敗指針的失敗指針。。。。已經(jīng)求得，可以完全根據(jù)這個找
? ? ? ?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) {
? ? ? ? ? ? ? ? ? ?//找到當(dāng)前節(jié)點的失敗指針，查看失敗指針子節(jié)點是否有==
? ? ? ? ? ? ? ? ? ?Node[]?failChildren?=?failNode.childNode;
? ? ? ? ? ? ? ? ? ?Node?node?=?failChildren[child.value?-?'a'];
? ? ? ? ? ? ? ? ? ?if?(null?==?node) {
? ? ? ? ? ? ? ? ? ? ? ?//找當(dāng)前指針的下一個指針
? ? ? ? ? ? ? ? ? ? ? ?failNode?=?failNode.failNode;
? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?//已經(jīng)找到匹配的
? ? ? ? ? ? ? ? ? ?//將失敗指針指向node
? ? ? ? ? ? ? ? ? ?child.failNode?=?node;
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果找完還沒有找到，指向root
? ? ? ? ? ? ? ?if?(null?==?failNode) {
? ? ? ? ? ? ? ? ? ?child.failNode?=?root;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?nodes.add(child);
? ? ? ? ? }
? ? ? }
? }

匹配

從首字符，字典樹從root節(jié)點開始進行匹配，如果字符與節(jié)點值匹配，則判斷是否為尾字符，如果是匹配上一個違禁詞，記錄下來，如果不匹配則轉(zhuǎn)移到失敗指針繼續(xù)進行匹配。

/**
? ??* 匹配出str中所有出現(xiàn)的關(guān)鍵詞
? ??* @param str
? ??* @return
? ??*/
? ?public?List<String>?match(String?str) {
? ? ? ?//遍歷當(dāng)前子串串，從根節(jié)點出發(fā)，如果匹配就一直往下進行匹配，同時需要看匹配的節(jié)點是否為結(jié)尾節(jié)點，如果是，匹配上一個
? ? ? ?//如果不匹配則通過失敗指針轉(zhuǎn)移到下一個節(jié)點
? ? ? ?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;
? ? ? }
? ? ? ?//從將當(dāng)前字符與當(dāng)前node的孩子節(jié)點進行匹配，如果當(dāng)前字符與node的孩子節(jié)點.value匹配，判斷當(dāng)前字符是否為尾節(jié)點，是，則記錄，匹配到了一個
? ? ? ?//繼續(xù)匹配（子節(jié)點，與下一個元素進行匹配）
? ? ? ?//如果不匹配，則轉(zhuǎn)到失敗指針
? ? ? ?Node[]?children?=?node.childNode;
? ? ? ?Node?child?=?children[chars.charAt(chIndex)?-?'a'];
? ? ? ?if?(null?==?child) {
? ? ? ? ? ?//不匹配，轉(zhuǎn)到失敗指針
? ? ? ? ? ?//如果當(dāng)前node==root，從root匹配，root的失敗指針是null
? ? ? ? ? ?if?(node?==?root) {
? ? ? ? ? ? ? ?dfs(root,?++?chIndex,?chars);
? ? ? ? ? }?else?{
? ? ? ? ? ? ? ?dfs(node.failNode,?chIndex,?chars);
? ? ? ? ? }
? ? ? }?else?{
? ? ? ? ? ?//匹配到了
? ? ? ? ? ?if?(child.isTail) {
? ? ? ? ? ? ? ?//并且是結(jié)尾節(jié)點，取從child.value到child.tailLength的字符
? ? ? ? ? ? ? ?machStr.add(chars.substring(chIndex?-?child.tailLength??+?1,?chIndex?+?1));
? ? ? ? ? }
? ? ? ? ? ?dfs(child,?++?chIndex,?chars);
? ? ? }

? }

執(zhí)行結(jié)果

public?static?void?main(String[]?args) {
? ? ? ?ACAutomaton?acAutomaton?=?new?ACAutomaton();
? ? ? ?//初始化一個僅有根節(jié)點的字典樹
? ? ? ?acAutomaton.init();
? ? ? ?//構(gòu)建Tire樹
? ? ? ?acAutomaton.insertStr("out".toCharArray());
? ? ? ?acAutomaton.insertStr("about".toCharArray());
? ? ? ?acAutomaton.insertStr("act".toCharArray());
? ? ? ?//構(gòu)建失敗指針
? ? ? ?acAutomaton.madeFailNext();
? ? ? ?System.out.println("ces");
? ? ? ?//匹配
? ? ? ?List<String>?result?=?acAutomaton.match("abcdeasactdaboutcebcd");
? }