Java數(shù)據(jù)結(jié)構(gòu)之AC自動(dòng)機(jī)算法如何實(shí)現(xiàn)

本篇內(nèi)容主要講解“Java數(shù)據(jù)結(jié)構(gòu)之AC自動(dòng)機(jī)算法如何實(shí)現(xiàn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Java數(shù)據(jù)結(jié)構(gòu)之AC自動(dòng)機(jī)算法如何實(shí)現(xiàn)”吧!

1 概念和原理

一般的字符串匹配算法都是匹配一個(gè)子串，例如KMP、Trie，那么如果同時(shí)匹配多個(gè)子串呢？此時(shí)就需要用到AC自動(dòng)機(jī)了。

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

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

• 前綴樹(shù)Trie的實(shí)現(xiàn)原理以及Java代碼的實(shí)現(xiàn)

• KMP算法詳解以及Java代碼實(shí)現(xiàn)

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

• 對(duì)所有的關(guān)鍵詞構(gòu)建Trie前綴樹(shù)。

• 為T(mén)rie樹(shù)上的所有節(jié)點(diǎn)構(gòu)建fail失配指針。

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

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

• 在KMP算法中，是針對(duì)單個(gè)關(guān)鍵詞匹配，求出的最長(zhǎng)匹配長(zhǎng)度的前綴和后綴都位于同一個(gè)關(guān)鍵詞內(nèi)。例如關(guān)鍵詞abcdabc，最長(zhǎng)匹配前后綴，為abc，他們屬于該關(guān)鍵詞。

• 在AC自動(dòng)機(jī)算法中，是針對(duì)多個(gè)關(guān)鍵詞匹配，求出的最長(zhǎng)匹配長(zhǎng)度的前綴和后綴分別屬于不同的關(guān)鍵詞的前綴和后綴。

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

2 節(jié)點(diǎn)定義

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

• next，表示經(jīng)過(guò)該節(jié)點(diǎn)的模式串的下層節(jié)點(diǎn)，這是Trie樹(shù)結(jié)構(gòu)的保證，存儲(chǔ)著子節(jié)點(diǎn)的值到對(duì)應(yīng)的節(jié)點(diǎn)的映射關(guān)系。

• depth，表示以當(dāng)前即誒單結(jié)尾的模式串的長(zhǎng)度，也是節(jié)點(diǎn)的深度，默認(rèn)為0。

• failure，失配指針，其指向表示另一個(gè)關(guān)鍵詞前綴的最長(zhǎng)后綴節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)沒(méi)有匹配到，則跳轉(zhuǎn)到此節(jié)點(diǎn)繼續(xù)匹配。如果當(dāng)前節(jié)點(diǎn)匹配到了，那么可以通過(guò)此指針找到該節(jié)點(diǎn)的模式串包含的最長(zhǎng)后綴模式串。

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

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

    /**
     * 失配指針，如果沒(méi)有匹配到，則跳轉(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前綴樹(shù)

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

/**
 * trie根節(jié)點(diǎn)
 */
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失配指針的一種常見(jiàn)的方法如下，實(shí)際上是一個(gè)BFS層序遍歷的算法：

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

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

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

• 如果pf節(jié)點(diǎn)的子節(jié)點(diǎn)對(duì)應(yīng)的字符中，包含了當(dāng)前節(jié)點(diǎn)的所表示的字符。那么基于求最長(zhǎng)后綴的原理，此時(shí)c節(jié)點(diǎn)的失配指針可以直接指向pf節(jié)點(diǎn)下的相同字符對(duì)應(yīng)的子節(jié)點(diǎn)。

• 如果pf節(jié)點(diǎn)的子節(jié)點(diǎn)對(duì)應(yīng)的字符中，沒(méi)有包含了當(dāng)前節(jié)點(diǎn)的所表示的字符。那么繼續(xù)獲取pf節(jié)點(diǎn)的失配指針節(jié)點(diǎn)，繼續(xù)重復(fù)判斷。直到滿(mǎn)足第一種情況，或者pf指向了根節(jié)點(diǎn)，并且根節(jié)點(diǎn)的子節(jié)點(diǎn)也沒(méi)有匹配，那么此時(shí)直接將c節(jié)點(diǎn)的失配指針指向根節(jié)點(diǎn)。

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

5 匹配文本

構(gòu)建完AC自動(dòng)機(jī)之后，下面我們需要進(jìn)行文本的匹配，匹配的方式實(shí)際上比較簡(jiǎn)單。

1.遍歷文本的每個(gè)字符，依次匹配，從Trie的根節(jié)點(diǎn)作為cur節(jié)點(diǎn)開(kāi)始匹配：

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

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

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

• 如果該節(jié)點(diǎn)是某個(gè)關(guān)鍵詞的結(jié)尾，那么取出來(lái)，也就是depth不為0，那么表示匹配到了一個(gè)關(guān)鍵詞。

• 繼續(xù)判斷該節(jié)點(diǎn)的失配指針節(jié)點(diǎn)表示的模式串。因?yàn)槭渲羔樄?jié)點(diǎn)表示的模式串是當(dāng)前匹配的模式串的在這些關(guān)鍵詞中的最長(zhǎng)后綴，且由于當(dāng)前節(jié)點(diǎn)的路徑包括了失配指針的全部路徑，并且失配指針路徑也是一個(gè)完整的關(guān)鍵詞，需要找出來(lái)。

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

假如我們的文本為sheshe，那么我們來(lái)看看AC自動(dòng)機(jī)匹配的過(guò)程：

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

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

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

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

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

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

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

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

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

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

而fuilure節(jié)點(diǎn)e又包含另一個(gè)模式串e，因此找到了第8個(gè)匹配的關(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'}]

到此，相信大家對(duì)“Java數(shù)據(jù)結(jié)構(gòu)之AC自動(dòng)機(jī)算法如何實(shí)現(xiàn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！