[發(fā)明專利]AC狀態(tài)機的構建方法及裝置

無效

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

1.一種AC狀態(tài)機的構建方法，其特征在于，包括：

將各搜尋模式中的各通配符設置為特定字符；

根據(jù)所述各搜尋模式構建關鍵字樹，所述關鍵字樹包括各狀態(tài)節(jié)點、各狀態(tài)節(jié)點的goto函數(shù)表和output函數(shù)表，其中，將基于所述特定字符所轉移至的狀態(tài)節(jié)點視為通配符節(jié)點；

將所述通配符節(jié)點的goto函數(shù)表復制到兄弟狀態(tài)節(jié)點中，并記錄轉移至所述兄弟狀態(tài)節(jié)點的輸入字符為待排除字符，其中，所述兄弟狀態(tài)節(jié)點為與所述通配符節(jié)點具有同一上層狀態(tài)節(jié)點的狀態(tài)節(jié)點；

當識別到復制goto函數(shù)表與兄弟狀態(tài)節(jié)點的原有goto函數(shù)表存在不確定goto函數(shù)時，將復制goto函數(shù)表中的不確定goto函數(shù)視為新goto函數(shù)，原有goto函數(shù)表中的不確定goto函數(shù)視為舊goto函數(shù)；

將新goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的goto函數(shù)表復制到舊goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的goto函數(shù)表中，去除新goto函數(shù)，并返回執(zhí)行上述識別步驟，直至未識別到不確定goto函數(shù)為止；

將所述特定字符轉換為所述通配符，并從所述通配符中排除所述兄弟狀態(tài)節(jié)點對應的所有待排除字符。

2.根據(jù)權利要求1所述的AC狀態(tài)機的構建方法，其特征在于，各搜尋模式中的確定字符由ASCII碼值表示，所述特定字符由非ASCII碼值的數(shù)值表示。

3.根據(jù)權利要求1或2所述的AC狀態(tài)機的構建方法，其特征在于，識別復制goto函數(shù)與兄弟狀態(tài)節(jié)點的原有goto函數(shù)存在不確定goto函數(shù)包括：

識別復制goto函數(shù)與兄弟狀態(tài)節(jié)點的原有goto函數(shù)的各轉移函數(shù)表達式和轉移函數(shù)輸出值；

將轉移函數(shù)表達式相同，且轉移函數(shù)輸出值不同的轉移函數(shù)作為不確定goto函數(shù)。

4.根據(jù)權利要求1所述的AC狀態(tài)機的構建方法，其特征在于，所述通配符為？。

5.根據(jù)權利要求4所述的AC狀態(tài)機的構建方法，其特征在于，所述搜尋模式中所述通配符的個數(shù)為1個或多個。

6.根據(jù)權利要求1所述的AC狀態(tài)機的構建方法，其特征在于，所述將新goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的goto函數(shù)表復制到舊goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的goto函數(shù)表中，去除新goto函數(shù)之后，且在返回執(zhí)行上述識別步驟，直至未識別到不確定goto函數(shù)為止之前，還包括：

判斷所述新goto函數(shù)輸出值所對應的狀態(tài)節(jié)點是否為終狀態(tài)節(jié)點，當判斷結果為是時，將所述新goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的output函數(shù)表復制到舊goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的output函數(shù)表中，所述終狀態(tài)節(jié)點為所述各搜尋模式中最后一個輸入字符對應的狀態(tài)節(jié)點。

7.根據(jù)權利要求1所述的AC狀態(tài)機的構建方法，其特征在于，在所述排除所述兄弟狀態(tài)節(jié)點對應的所有待排除字符之后，還包括：

根據(jù)所述關鍵字樹和去failure算法構建AC狀態(tài)機。

8.一種AC狀態(tài)機的構建裝置，其特征在于，包括：

設定模塊，用于將各搜尋模式中的通配符設置為特定字符；

構建模塊，用于根據(jù)所述各搜尋模式構建關鍵字樹，所述關鍵字樹包括各狀態(tài)節(jié)點、各狀態(tài)節(jié)點的goto函數(shù)表和output函數(shù)表，其中，將基于所述特定字符所轉移至的狀態(tài)節(jié)點視為通配符節(jié)點；

復制模塊，用于將所述通配符節(jié)點的goto函數(shù)表復制到兄弟狀態(tài)節(jié)點中，并記錄轉移至所述兄弟狀態(tài)節(jié)點的輸入字符為待排除字符，其中，所述兄弟狀態(tài)節(jié)點為與所述通配符節(jié)點具有同一上層狀態(tài)節(jié)點的狀態(tài)節(jié)點；

識別模塊，用于當識別到復制goto函數(shù)表與兄弟狀態(tài)節(jié)點的原有goto函數(shù)表存在不確定goto函數(shù)時，將復制goto函數(shù)表中的不確定goto函數(shù)視為新goto函數(shù)，原有goto函數(shù)表中的不確定goto函數(shù)視為舊goto函數(shù)，并將新goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的goto函數(shù)表復制到舊goto函數(shù)輸出值所對應的狀態(tài)節(jié)點的goto函數(shù)表中，去除新goto函數(shù)，并返回執(zhí)行上述識別步驟，直至未識別到不確定goto函數(shù)為止；

排除模塊，用于將所述特定字符轉換為所述通配符，并從所述通配符中排除所述兄弟狀態(tài)節(jié)點對應的所有待排除字符。

9.根據(jù)權利要求8所述的AC狀態(tài)機的構建裝置，其特征在于，各搜尋模式中的確定字符由ASCII碼值表示，所述特定字符由非ASCII碼值的數(shù)值表示。