[發明專利]AC狀態機的構建方法及裝置

無效

• 申請號: 201210038061.8
• 申請日: 2012-02-17
• 公開（公告）號: CN102646115A
• 公開（公告）日: 2012-08-22
• 發明（設計）人: 陳國鵬
• 申請（專利權）人: 北京星網銳捷網絡技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 馬爽

技術領域

本發明涉及模式匹配技術，尤其涉及一種AC狀態機的構建方法及裝置。

背景技術

多模式匹配問題是計算機科學的基本問題之一，多模式匹配問題可以簡單描述為：當存在一個搜尋文本和一個搜尋模式集合時，搜尋模式集合包括兩個以上的搜尋模式，每個搜尋模式通常是一字符串。在搜尋文本中查找搜尋模式集合中的各搜尋模式。比如：搜尋文本A為：abcdefg123456，搜尋模式集合C為{abc、ef、tian、123、67、890}。那么，進行多模式匹配后，輸出的結果就是搜尋文本A中包含搜尋模式abc、ef和123。

多模式匹配只要掃描一遍搜尋文本，就能夠找出該搜尋文本匹配的所有搜尋模式，具有很高的匹配效率，廣泛用于入侵檢測、病毒檢測、搜索引擎和數據挖掘等領域。

AC(Aho-Corasick)算法是一種經典的多模式匹配算法，能夠在任意的搜尋文本中定位任一個搜尋模式的所有位置。該算法利用有限自動機巧妙地將字符比較轉化為狀態轉移。其原理是：首先根據搜尋模式集合定義一個有限狀態模式匹配機，然后把搜尋文本作為模式匹配狀態機的輸入，只要匹配到搜尋模式，就會通報此搜尋模式成功。在標準的AC算法中，搜尋文本的每次輸入是一個字節。

以搜尋模式集合{he、she、his、hers}為例，由此搜尋模式集合構建的AC狀態機如圖1A～1C所示。圖1A～圖1C為現有技術AC狀態機的示意圖。圖1A的關鍵字樹中，每一個圓圈表示一個狀態節點，每個狀態節點都包含三個重要數據：轉移(goto)函數(圖1A)、失效(failure)函數(圖1B)、輸出(output)函數(圖1C)。

其中，goto函數用于把一個由狀態和輸入字符組成的二元組映射成另一個狀態或是失效；

failure函數用于把一個狀態映射到另一個狀態。當goto函數報告失效時，failure函數就會被詢問；

output函數，用于表示某個搜尋模式已經被匹配。

在基本AC狀態機的狀態遷移中，在當前狀態S和輸入字符c下，下一個狀態為：

操作1：如果goto(S，c)存在，那么下一個狀態為goto(S，c)，算法結束，否則，執行操作2；

操作2：將failure(S)賦值給S，執行操作1。

由于在基本AC狀態機中，如果goto函數的結果不存在，就會導致一次或是多次的訪問failure函數，為了提高AC狀態機的效率，現有技術提出一種去failure的AC狀態機。在去failure的AC狀態機中，每一個狀態節點沒有failure函數，而是把goto函數和failure函數統一為：下一個狀態(nextstate)函數。

去failure的AC狀態機的示意圖和標準AC狀態機的示意圖是一樣的，只是每個狀態節點下，不再有goto函數和failure函數，而是用nextstate函數替代。nextstate函數用于把一個由狀態和輸入字符組成的二元組映射成另一個狀態。即通過nextstate函數，可獲知一個確定的下一個狀態。

有了nextstate函數后，AC狀態機的遷移就簡單多了，在當前狀態S和當前輸入字符c下，那么下一個狀態就是：nextstate(S，c)。

為了方便獲取nextstate函數，每一個狀態節點需保存下一個狀態表，每一個狀態節點的下一個狀態表記錄：在當前狀態下，在不同的輸入字符時的下一個狀態值，即在當前狀態下，輸入某個字符，那么將遷移到哪一個狀態。由于字符是一個字節，能夠表示美國信息互換標準代碼(American?Standard?Code?for?Information?Interchange，以下簡稱：ASCII)碼中的0～255。其中，ASCII碼值表記錄的是用戶所看到的字符與計算機內部的真正數值之間的映射，由于一個字節的取值范圍是0～255，因而ASCII碼值表有256個單元。比如：用戶看到的字母a，計算機內部的保存數值是97；用戶看到的數字1，計算機內部的保存數值是31，等等。因而下一個狀態表是一個具有256個成員的數組。以圖1A中的狀態節點1為例，狀態節點1在256個不同ASCII碼值輸入時的下一個狀態表，可以如表1所示。

表1