1 概念和原理

一般的字符串匹配算法都是匹配一個子串，例如KMP、Trie，那么如果同時匹配多個子串呢？此時就需要用到AC自動機了。

AC自動機算法是一個多模式字符串匹配算法，在模式匹配領(lǐng)域被廣泛應(yīng)用，例如違禁詞查找替換、搜索關(guān)鍵詞查找等等。

關(guān)于Trie樹和KMP算法，我們此前已經(jīng)講解過了：

• 前綴樹Trie的實現(xiàn)原理以及Java代碼的實現(xiàn)
• KMP算法詳解以及Java代碼實現(xiàn)

AC自動機算法常被認(rèn)為是Trie樹+KMP算法的結(jié)合體，為什么呢？我們先看看它的構(gòu)建步驟：

• 對所有的關(guān)鍵詞構(gòu)建Trie前綴樹。
• 為Trie樹上的所有節(jié)點構(gòu)建fail失配指針。

第一步，對所有的關(guān)鍵詞構(gòu)建Trie前綴樹。這一步利用Trie的特點構(gòu)建快速前綴查找結(jié)構(gòu)，trie樹的特點是可以從字符串頭部開始匹配，并且相同前綴的詞共用前面的節(jié)點，因此它可以避免相同前綴pattern的重復(fù)匹配，但是對于相同的后綴無能為力。

第二步，為Trie樹上的所有節(jié)點構(gòu)建fail失配指針，即匹配失敗后應(yīng)該跳到哪個節(jié)點。所謂節(jié)點的失配指針，就是指向當(dāng)前字符串最長真后綴位置的指針節(jié)點。這里需要理解KMP的next數(shù)組的概念，這一步就是利用KMP前后綴匹配的思想實現(xiàn)關(guān)鍵詞前綴失配時利用相同的后綴信息快速跳轉(zhuǎn)到另一個關(guān)鍵詞繼續(xù)前綴匹配。他們的區(qū)別是：

• 在KMP算法中，是針對單個關(guān)鍵詞匹配，求出的最長匹配長度的前綴和后綴都位于同一個關(guān)鍵詞內(nèi)。例如關(guān)鍵詞abcdabc，最長匹配前后綴，為abc，他們屬于該關(guān)鍵詞。
• 在AC自動機算法中，是針對多個關(guān)鍵詞匹配，求出的最長匹配長度的前綴和后綴分別屬于不同的關(guān)鍵詞的前綴和后綴。

例如兩個關(guān)鍵詞dabab，ababd，那么關(guān)鍵詞dabab中第二個b位置的失敗指針應(yīng)該指向關(guān)鍵詞ababd中的第二個b。即dabab的后綴與ababd的前綴能夠匹配的最長子串為abab。

2 節(jié)點定義

在這里，我們給出一個比較簡單的節(jié)點的定義。

• next，表示經(jīng)過該節(jié)點的模式串的下層節(jié)點，這是Trie樹結(jié)構(gòu)的保證，存儲著子節(jié)點的值到對應(yīng)的節(jié)點的映射關(guān)系。
• depth，表示以當(dāng)前即誒單結(jié)尾的模式串的長度，也是節(jié)點的深度，默認(rèn)為0。
• failure，失配指針，其指向表示另一個關(guān)鍵詞前綴的最長后綴節(jié)點，如果當(dāng)前節(jié)點沒有匹配到，則跳轉(zhuǎn)到此節(jié)點繼續(xù)匹配。如果當(dāng)前節(jié)點匹配到了，那么可以通過此指針找到該節(jié)點的模式串包含的最長后綴模式串。

class AcNode {
    /**
     * 經(jīng)過該節(jié)點的模式串的下層節(jié)點
     */
    Map<Character, AcNode> next = new HashMap<>();

    /**
     * 模式串的長度，也是節(jié)點的深度
     */
    int depth;

    /**
     * 失配指針，如果沒有匹配到，則跳轉(zhuǎn)到此狀態(tài)。
     */
    AcNode failure;

    public boolean hashNext(char nextKey) {
        return next.containsKey(nextKey);
    }

    public AcNode getNext(char nextKey) {
        return next.get(nextKey);
    }
}

3 構(gòu)建Trie前綴樹

構(gòu)建Ac自動機的Trie的方法和構(gòu)建普通Trie的方法幾乎一致。在添加每個模式串成功后，會為最后一個節(jié)點的depth賦值為當(dāng)前模式串的長度。

/**
 * trie根節(jié)點
 */
private AcNode root;
/**
 * 加入模式串，構(gòu)建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();
}

4 構(gòu)建fail失配指針

構(gòu)建fail失配指針的一種常見的方法如下，實際上是一個BFS層序遍歷的算法：

1.Trie的root節(jié)點沒有失配指針，或者說失配指針為null，其他節(jié)點都有失配指針，或者說不為null。

2.遍歷root節(jié)點的所有下一層直接子節(jié)點，將它們的失配指針設(shè)置為root。因為這些節(jié)點代表著所有模式串的第一個字符，基于KMP的next數(shù)組定義，單個字符沒有最長真后綴，此時直接指向root。

3.繼續(xù)循環(huán)向下遍歷每一層的子節(jié)點，由于bfs的遍歷，那么上一層父節(jié)點的失配指針肯定都已經(jīng)確定了?；趎ext數(shù)組的構(gòu)建思想，子節(jié)點的失配指針可以通過父節(jié)點的是失配指針快速推導(dǎo)出來。設(shè)當(dāng)前遍歷的節(jié)點為c，它的父節(jié)點為p，父節(jié)點的失配指針為pf。

• 如果pf節(jié)點的子節(jié)點對應(yīng)的字符中，包含了當(dāng)前節(jié)點的所表示的字符。那么基于求最長后綴的原理，此時c節(jié)點的失配指針可以直接指向pf節(jié)點下的相同字符對應(yīng)的子節(jié)點。
• 如果pf節(jié)點的子節(jié)點對應(yīng)的字符中，沒有包含了當(dāng)前節(jié)點的所表示的字符。那么繼續(xù)獲取pf節(jié)點的失配指針節(jié)點，繼續(xù)重復(fù)判斷。直到滿足第一種情況，或者pf指向了根節(jié)點，并且根節(jié)點的子節(jié)點也沒有匹配，那么此時直接將c節(jié)點的失配指針指向根節(jié)點。

/**
 * 為所有節(jié)點構(gòu)建失配指針，一個bfs層序遍歷
 */
public void buildFailurePointer() {
    ArrayDeque<AcNode> queue = new ArrayDeque<AcNode>();
    //將所有root的直接子節(jié)點的failure設(shè)置為root，并且加入queue
    for (AcNode acNode : root.next.values()) {
        acNode.failure = root;
        queue.addLast(acNode);
    }
    //bfs構(gòu)建失配指針
    while (!queue.isEmpty()) {
        //父節(jié)點出隊列
        AcNode parent = queue.pollFirst();
        //遍歷父節(jié)點的下層子節(jié)點，基于父節(jié)點求子節(jié)點的失配指針
        for (Map.Entry<Character, AcNode> characterAcNodeEntry : parent.next.entrySet()) {
            //獲取父節(jié)點的失配指針
            AcNode pf = parent.failure;
            //獲取子節(jié)點
            AcNode child = characterAcNodeEntry.getValue();
            //獲取子節(jié)點對應(yīng)的字符
            Character nextKey = characterAcNodeEntry.getKey();
            //如果pf節(jié)點不為null，并且pf節(jié)點的子節(jié)點對應(yīng)的字符中，沒有包含了當(dāng)前節(jié)點的所表示的字符
            while (pf != null && !pf.hashNext(nextKey)) {
                //繼續(xù)獲取pf節(jié)點的失配指針節(jié)點，繼續(xù)重復(fù)判斷
                pf = pf.failure;
            }
            //pf為null，表示找到了根節(jié)點，并且根節(jié)點的子節(jié)點也沒有匹配
            if (pf == null) {
                //此時直接將節(jié)點的失配指針指向根節(jié)點
                child.failure = root;
            }
            //pf節(jié)點的子節(jié)點對應(yīng)的字符中，包含了當(dāng)前節(jié)點的所表示的字符
            else {
                //節(jié)點的失配指針可以直接指向pf節(jié)點下的相同字符對應(yīng)的子節(jié)點
                child.failure = pf.getNext(nextKey);
            }
            //最后不要忘了，將當(dāng)前節(jié)點加入隊列
            queue.addLast(child);
        }
    }
}

5 匹配文本

構(gòu)建完AC自動機之后，下面我們需要進行文本的匹配，匹配的方式實際上比較簡單。

1.遍歷文本的每個字符，依次匹配，從Trie的根節(jié)點作為cur節(jié)點開始匹配：

2.將當(dāng)前字符作為nextKey，如果cur節(jié)點不為null且節(jié)點的next映射中不包含nextKey，那么當(dāng)前cur節(jié)點指向自己的failure失配指針。

3.如果cur節(jié)點為null，說明當(dāng)前字符匹配到了root根節(jié)點且失敗，那么cur設(shè)置為root繼續(xù)從根節(jié)點開始進行下一輪匹配。

4.否則表示匹配成功的節(jié)點，cur指向匹配節(jié)點，獲取該節(jié)點繼續(xù)判斷：

• 如果該節(jié)點是某個關(guān)鍵詞的結(jié)尾，那么取出來，也就是depth不為0，那么表示匹配到了一個關(guān)鍵詞。
• 繼續(xù)判斷該節(jié)點的失配指針節(jié)點表示的模式串。因為失配指針節(jié)點表示的模式串是當(dāng)前匹配的模式串的在這些關(guān)鍵詞中的最長后綴，且由于當(dāng)前節(jié)點的路徑包括了失配指針的全部路徑，并且失配指針路徑也是一個完整的關(guān)鍵詞，需要找出來。

/**
 * 匹配文本
 *
 * @param text 文本字符串
 */
public List<ParseResult> parseText(String text) {
    List<ParseResult> parseResults = new ArrayList<>();
    char[] chars = text.toCharArray();
    //從根節(jié)點開始匹配
    AcNode cur = root;
    //遍歷字符串的每個字符
    for (int i = 0; i < chars.length; i++) {
        //當(dāng)前字符
        char nextKey = chars[i];
        //如果cur不為null，并且當(dāng)前節(jié)點的的子節(jié)點不包括當(dāng)前字符，即不匹配
        while (cur != null && !cur.hashNext(nextKey)) {
            //那么通過失配指針轉(zhuǎn)移到下一個節(jié)點繼續(xù)匹配
            cur = cur.failure;
        }
        //如果節(jié)點為null，說明當(dāng)前字符匹配到了根節(jié)點且失敗
        //那么繼續(xù)從根節(jié)點開始進行下一輪匹配
        if (cur == null) {
            cur = root;
        } else {
            //匹配成功的節(jié)點
            cur = cur.getNext(nextKey);
            //繼續(xù)判斷
            AcNode temp = cur;
            while (temp != null) {
                //如果當(dāng)前節(jié)點是某個關(guān)鍵詞的結(jié)尾，那么取出來
                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));
                }
                //繼續(xù)判斷該節(jié)點的失配指針節(jié)點
                //因為失配指針節(jié)點表示的模式串是當(dāng)前匹配的模式串的在這些關(guān)鍵詞中的最長后綴，且由于當(dāng)前節(jié)點的路徑包括了失配指針的全部路徑
                //并且失配指針路徑也是一個完整的關(guān)鍵詞，需要找出來。
                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 + '\'' +
                '}';
    }
}

6 案例演示

基于上面的方法，假如關(guān)鍵詞為：he、shes、shers、hes、h、e，那么最終構(gòu)建的AC自動機的結(jié)構(gòu)如下（紅色圈表示某個關(guān)鍵詞的結(jié)束位置）。

假如我們的文本為sheshe，那么我們來看看AC自動機匹配的過程：

遍歷文本，cur首先指向root。

nextKey=s，cur.next包含s，表示這是一個匹配成功的節(jié)點，那么獲取到該節(jié)點s，cur=s，s不是某個關(guān)鍵詞的結(jié)尾，failure節(jié)點也不包含模式串，那么查找完畢進行下一輪。

nextKey=h，cur=s，cur.next包含h，表示這是一個匹配成功的節(jié)點，那么獲取到該節(jié)點h，cur=h，h節(jié)點不是某個關(guān)鍵詞的結(jié)尾，但是它的failure節(jié)點包含模式串h，因此找到了第1個匹配的關(guān)鍵詞h，查找完畢后進行下一輪。

nextKey=e，cur=h，cur.next包含e，表示這是一個匹配成功的節(jié)點，那么獲取到該節(jié)點e，cur=e，e節(jié)點不是某個關(guān)鍵詞的結(jié)尾，但是它的failure節(jié)點包含模式串he，因此找到了第2個匹配的關(guān)鍵詞he。

而fuilure節(jié)點e又包含另一個模式串e，因此找到了第3個匹配的關(guān)鍵詞e，查找完畢后進行下一輪。

nextKey=s，cur=e，cur.next包含s，表示這是一個匹配成功的節(jié)點，那么獲取到該節(jié)點e，cur=e，s節(jié)點是關(guān)鍵詞shes的結(jié)尾，因此找到了第4個匹配的關(guān)鍵詞shes。

繼續(xù)判斷s的failure，它的failure節(jié)點包含模式串hes，因此找到了第5個匹配的關(guān)鍵詞hes，查找完畢后進行下一輪。

nextKey=h，cur=s，cur.next不包含h，表示這是一個匹配失敗的節(jié)點，那么繼續(xù)匹配它的failure節(jié)點，經(jīng)過s-s-s的匹配，最終匹配到子節(jié)點h。

該節(jié)點h并不是關(guān)鍵詞的結(jié)尾，但是h的failure，它的failure節(jié)點包含模式串h，因此找到了第6個匹配的關(guān)鍵詞h，查找完畢后進行下一輪。

nextKey=e，cur=h，cur.next包含e，表示這是一個匹配成功的節(jié)點，那么獲取到該節(jié)點e，cur=e，e節(jié)點不是某個關(guān)鍵詞的結(jié)尾，但是它的failure節(jié)點包含模式串he，因此找到了第7個匹配的關(guān)鍵詞he。

而fuilure節(jié)點e又包含另一個模式串e，因此找到了第8個匹配的關(guān)鍵詞e。

到此字符串遍歷完畢，查找完畢！

最終文本sheshe，匹配到關(guān)鍵詞如下：

[{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'}]

7 總結(jié)

AC自動機匹配某個文本text，需要遍歷文本的每個字符，每次遍歷過程中，都可能涉及到循環(huán)向上查找失配指針的情況，但是這里的循環(huán)次數(shù)不會超過Trie樹的深度，在最后匹配成功時，同樣涉及到向上查找失配指針的情況，這里的循環(huán)次數(shù)不會超過Trie樹的深度。

設(shè)匹配的文本長度m，模式串平均長度n，那么AC自動機算法的匹配的時間復(fù)雜度為O(m*n)?？梢园l(fā)現(xiàn)，匹配的時間復(fù)雜度和關(guān)鍵詞的數(shù)量無關(guān)，這就是AC自動機的強大之處。如果考慮模式串平均長度不會很長，那么時間復(fù)雜度近似O(m)。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之AC自動機算法的實現(xiàn)的文章就介紹到這了,更多相關(guān)Java AC自動機算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！