ac算法原理ppt課件(編輯修改稿)
2025-06-01 07:50 本頁面
【文章內容簡介】 算機學院 10 AhoCorasick自動機算法 ?AhoCorasick自動機算法（簡稱 AC自動機）1975年產生于貝爾實驗室，這種算法最早被使用在圖書館的書目查詢程序中，取得了很好的效果 ?在預處理階段， AC自動機算法建立了三個函數(shù) – 轉向函數(shù) goto – 失效函數(shù) failure – 輸出函數(shù) output 哈爾濱工業(yè)大學 計算機學院 11 AhoCorasick自動機算法 數(shù)據(jù)結構和算法流程 ?樹型有限自動機是一種確定型有限自動機，對應模式串集 P的樹型有限自動機是一個程序。 ?把輸入文本 y作為輸入，輸出 P中關鍵字在 y中作為子串出現(xiàn)的位置。 ?樹型有限自動機包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字代表。 ?狀態(tài)機讀入文本串 y中的字符，然后通過產生狀態(tài)轉移或者偶爾發(fā)送輸出的方式來處理文本。 哈爾濱工業(yè)大學 計算機學院 12 AhoCorasick自動機算法 數(shù)據(jù)結構和算法流程 轉向函數(shù)把一個由狀態(tài)和輸入字符組成的二元組映射成另一個狀態(tài)或者一條失敗消息轉向函數(shù) 對應模式串集 {he, she, his, hers}的樹型有限自動機 0 1 2 8 9 6 7 3 4 5 172。{h,s} h e r s i s s h e 哈爾濱工業(yè)大學 計算機學院 13 AhoCorasick自動機算法 數(shù)據(jù)結構和算法流程 失效函數(shù) f ,失效函數(shù)把一個狀態(tài)映射成另一個狀態(tài)。當轉向函數(shù)報告失效時，失效函數(shù)就會被詢問 輸出函數(shù) output 哈爾濱工業(yè)大學 計算機學院 14 AhoCorasick自動機工作過程 ? s為狀態(tài)機的當前狀態(tài)， a為輸入文本 y的當前輸入字符 ? 如果 g(s, a) = s’ ，那么樹型有限自動機將做一個轉向動作。自動機進入狀態(tài) s’，而且 y的下一個字符變成當前的輸入字符。另外，如果 output( s’)不為空，那么狀態(tài)機將輸出與當前輸入字符位置相對應的一組關鍵字。 ? 如果 g(s, a) = fail，狀態(tài)機將詢問失效函數(shù) f并且進行失效轉移。 ? f(s) = s’，那么狀態(tài)機將以 s’作為當前狀態(tài)，a為當前輸入字符重復這個操作循環(huán)。 哈爾濱工業(yè)大學 計算機學院 15 0 1 2 8 9 6 7 3 4 5 172。{h,s} h e r s i s
教學課件相關推薦
鄂ICP備17016276號-1