ac算法原理ppt課件-在線瀏覽
2025-06-22 07:50本頁面
【正文】 。 ?一種字符串匹配算法一般由二部分組成：模式 x的預(yù)處理分階段和搜索 x在 y中的位置。搜索階段使用數(shù)據(jù)結(jié)構(gòu) X，它努力迅速確定這種模式是否在正文里發(fā)生。 哈爾濱工業(yè)大學(xué) 計算機(jī)學(xué)院 6 串匹配的多種策略 確定型有限自動機(jī) ?有限自動機(jī)的定義 –確定型有限自動機(jī)（ DFA），是指一個包括狀態(tài)集 S，輸入的字符集 Σ，狀態(tài)轉(zhuǎn)換函數(shù) δ，起始狀態(tài) s0和終止?fàn)顟B(tài)集 S1的五元組 M = {S,Σ,δ,s0,S1}。 哈爾濱工業(yè)大學(xué) 計算機(jī)學(xué)院 7 串匹配的多種策略 確定型有限自動機(jī) ?串匹配自動機(jī) – 能夠識別語言 *x（在這里是文本 x）的串匹配的有限狀態(tài)自動機(jī) DFA A(x) =(Q, q0, T, E) 形式化定義如下：（ ε表示空字符串） – Q 是 x所有前綴的集合，即 Q={ε, x[0], x[0 .. 1], ... , x[0 .. m2], x}； q0=ε； – T={x}； – 如果 q ∈ Q (q是 x的前綴 )且 a ，那么 (q, a, qa) E當(dāng)且僅當(dāng) qa 也是 x的前綴，否則 (q, a, p) E ，其中 p是qa的最長后綴而且 p也是 x的前綴。如圖所示狀態(tài)轉(zhuǎn)移圖。只需從起始狀態(tài) q0開始用預(yù)處理建立的有限自動機(jī) A(x)分析文本 y。在某個狀態(tài) q和輸入字符 a下，找到狀態(tài)圖中的相應(yīng)的邊，然后進(jìn)入下一個狀態(tài)，這就完成一次狀態(tài)轉(zhuǎn)移。 哈爾濱工業(yè)大學(xué) 計算機(jī)學(xué)院 10 AhoCorasick自動機(jī)算法 ?AhoCorasick自動機(jī)算法（簡稱 AC自動機(jī)）1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，這種算法最早被使用在圖書館的書目查詢程序中，取得了很好的效果 ?在預(yù)處理階段， AC自動機(jī)算法建立了三個函數(shù) – 轉(zhuǎn)向函數(shù) goto – 失效函數(shù) failure – 輸出函數(shù) output 哈爾濱工業(yè)大學(xué) 計算機(jī)學(xué)院 11 AhoCorasick自動機(jī)算法 數(shù)據(jù)結(jié)構(gòu)和算法流程 ?樹型有限自動機(jī)是一種確定型有限自動機(jī)，對應(yīng)模式串集 P的樹型有限自動機(jī)是一個程序。 ?樹型有限自動機(jī)包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字代表。 哈爾濱工業(yè)大學(xué) 計算機(jī)學(xué)院 12 AhoCorasick自動機(jī)算法 數(shù)據(jù)結(jié)構(gòu)和算法流程 轉(zhuǎn)向函數(shù)把一個由狀態(tài)和輸入字符組成的二元組映射成另一個狀態(tài)或者一條失敗消息轉(zhuǎn)向函數(shù) 對應(yīng)模式串集 {he,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1