多模式串匹配之a(chǎn)c自動機算法(已修改)
2025-08-29 09:41 本頁面
【正文】 多模式串匹配之AC自動機算法（AhoCorasick算法）簡介與C語言程序?qū)崿F(xiàn)源碼參考 任俠 發(fā)布于 2011032222:27:53 一、概述AC自動機算法全稱AhoCorasick算法，是一種字符串多模式匹配算法。該算法在1975年產(chǎn)生于貝爾實驗室，是著名的多模匹配算法之一。AC算法用于在一段文本中查找多個模式字符串，即給你很多字符串，再給你一段文本，讓你在文本中找這些串是否出現(xiàn)過，出現(xiàn)過多少次，分別在哪里出現(xiàn)。該算法應(yīng)用有限自動機巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。此算法有兩個特點，一個是掃描文本時完全不需要回溯，另一個是時間復雜度為O(n)，時間復雜度與關(guān)鍵字的數(shù)目和長度無關(guān)，但所需時間和文本長度以及所有關(guān)鍵字的總長度成正比。AC算法有三個主要步驟，一個是字典樹tire的構(gòu)造，一個是搜索路徑的確定（即構(gòu)造失敗指針），還有就是模式匹配過程。學習AC自動機算法之前，最好先熟悉KMP算法，因為KMP算法與字典樹tire的構(gòu)造很是類似。KMP算法是一種經(jīng)典的單字符串匹配算法。二、AC算法思想AC算法思想：用多模式串建立一個確定性的樹形有限狀態(tài)機，以主串作為該有限狀態(tài)機的輸入，使狀態(tài)機進行狀態(tài)的轉(zhuǎn)換，當?shù)竭_某些特定的狀態(tài)時，說明發(fā)生模式匹配。下圖是多模式he/ she/ his /hers構(gòu)成的一個確定性有限狀態(tài)機，做幾點說明： 該狀態(tài)機優(yōu)先按照實線標注的狀態(tài)轉(zhuǎn)換路徑進行轉(zhuǎn)換，當所有實線標注的狀態(tài)轉(zhuǎn)換路徑條件不能滿足時，按照虛線的狀態(tài)轉(zhuǎn)換路徑進行狀態(tài)轉(zhuǎn)換。如：狀態(tài)0時，當輸入h，則轉(zhuǎn)換到狀態(tài)1；輸入s，則轉(zhuǎn)換到狀態(tài)3；否則轉(zhuǎn)換到狀態(tài)0。 匹配過程如下：從狀態(tài)0開始進行狀態(tài)轉(zhuǎn)換，主串作為輸入。如主串為：ushers，狀態(tài)轉(zhuǎn)換的過程是這樣的：當狀態(tài)轉(zhuǎn)移到2，5，7，9等紅色狀態(tài)點時，說明發(fā)生了模式匹配。如主串為：ushers，則在狀態(tài)9等狀態(tài)時發(fā)生模式匹配，匹配的模 式串有she、he、hers。定義：在預處理階段，AC自動機算法建立了三個函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個樹型有限自動機。轉(zhuǎn)向函數(shù)，指的是一種狀態(tài)之間的轉(zhuǎn)向關(guān)系。g(pre, x)=next：狀態(tài)pre在輸入一個字符x后轉(zhuǎn)換為狀態(tài)next（上圖中的實線部分）。如果在模式串中不存在這樣的轉(zhuǎn)換，則next=failstate。失效函數(shù)，指的也是狀態(tài)和狀態(tài)之間一種轉(zhuǎn)向關(guān)系。f(per)=next：是在比較失配的情況下使用的轉(zhuǎn)換關(guān)系。在構(gòu)造轉(zhuǎn)向函數(shù)時，把不存在的轉(zhuǎn)換用failstate表示，但是failstate不是一個具體的狀態(tài)，狀態(tài)機轉(zhuǎn)換轉(zhuǎn)換到failstate狀態(tài)的時候就不知道該往哪轉(zhuǎn)了。所以就要在狀態(tài)機中找到一個有意義的狀態(tài)代替failstate，當出現(xiàn)failstate狀態(tài)時，自動切換到那個狀態(tài)。這個狀態(tài)節(jié)點應(yīng)該具有這樣的特征：從這個狀態(tài)節(jié)點向上直到樹根節(jié)點（狀態(tài)0）所經(jīng)歷的輸入字符，和從產(chǎn)生failstate狀態(tài)的那個狀態(tài)節(jié)點向上所經(jīng)歷的輸入字符串完全相同。而且這個狀態(tài)節(jié)點，是所有具備這些條件的節(jié)點中深度最大的那個節(jié)點。如果不存在滿足條件的狀態(tài)節(jié)點，則失效函數(shù)為0。累死了。舉例子說吧，對狀態(tài)9輸入任何一個字符都會產(chǎn)生failstate狀態(tài)，需要失效函數(shù)。狀態(tài)3向上到狀態(tài)0經(jīng)過的輸入字符串為s；而由狀態(tài)9向上的輸入字符串為sreh。字符串s相同，并且狀態(tài)3是滿足此條件的唯一節(jié)點，則f(9)=3。說來說去，失效函數(shù)就是要干這么件事兒：意思就是說，在比較模式串1發(fā)生失配時，找一個模式串2，使得P2[0...j1] = P1[ij+1...i]。然后繼續(xù)比較模式串2?？瓷厦婺莻€圖，想起點兒什么東西沒有？對了，是KMP算法。有人說AC算法就是KMP算法在多模式匹配情況下的擴展。輸出函數(shù)，指的是狀態(tài)和模式串之間的一種關(guān)系。output(i)={P}，表示當狀態(tài)機到達狀態(tài)i時，模式串集合{P}中的所有模式串可能已經(jīng)完成匹配。例：模式串為：he/ she/ hers/ his 時。轉(zhuǎn)向函數(shù)：失效函數(shù)：輸出函數(shù)：三、字典樹tire的構(gòu)造這個比較好理解，就是把要匹配的一些字符串添加到樹結(jié)構(gòu)中去。樹邊就是單詞中的字符，單詞中最后一個字符的連接節(jié)點添加標志，以表示改節(jié)點路徑包含1個字典中的字符串，搜索到此節(jié)點就表示找到了字典中的某個單詞，可以直接輸出。Trie是一個樹形結(jié)構(gòu)的狀態(tài)裝換圖，從一個結(jié)點到它的各個子結(jié)點的邊上有不同的標號。Trie的葉子結(jié)點表示識別到的關(guān)鍵字。當我們的模式串在Tire上進行匹配時，如果與當前節(jié)點的關(guān)鍵字不能繼續(xù)匹配的時候，就應(yīng)該去當前節(jié)點的失敗指針所指向的節(jié)點繼續(xù)進行匹配。例子：某字典P=｛he,she,his,hers｝對應(yīng)的字典樹如下圖：圖中有數(shù)字的節(jié)點到根節(jié)點的路勁正好對應(yīng)字典中的字符串，數(shù)字表述單詞在字典中的順序，也可以是其他標志。四、搜索路徑的確定我的理解是：利用后綴字符串來確定。后綴字符串就是某個字符串的后面的一部分。比如abcde的后綴字符串有bcde,cde,de和e。假定目標字符串為ushers，字典為上圖（圖1）所示。搜索過程目標字符串指針指向的字符和字典中的字符會有以下幾種情況
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1