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