[發(fā)明專利]匹配規(guī)則包含或運算符的并行多模式匹配的方法及系統(tǒng)

無效

• 申請?zhí)枺?/td>: 200810225563.5
• 申請日: 2008-11-05
• 公開（公告）號: CN101388044A
• 公開（公告）日: 2009-03-18
• 發(fā)明（設計）人: 胡振宇;葉潤國;李博;鄧煒;王雷章
• 申請（專利權）人: 北京啟明星辰信息技術股份有限公司;北京啟明星辰信息安全技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權代理有限公司
• 代理人: 祁建國;常大軍

1.一種匹配規(guī)則包含或運算符的并行多模式匹配的系統(tǒng)，其特征在于，包括：

生成模塊，用于讀取包含匹配規(guī)則的規(guī)則集，將所述規(guī)則集中包含或運算符的匹配規(guī)則從或運算符處分割成所述匹配規(guī)則的子規(guī)則，所述子規(guī)則為確定規(guī)則，所述規(guī)則集中為確定規(guī)則的匹配規(guī)則作為其自身的子規(guī)則，并將所有子規(guī)則按照AC算法生成AC自動機；

匹配模塊，用于讀取搜索對象，按AC算法應用所述AC自動機進行搜索，判斷所述搜索對象是否匹配所述匹配規(guī)則的至少一個子規(guī)則，如果是，則所述搜索對象匹配所述匹配規(guī)則，并輸出匹配結果。

2.如權利要求1所述的匹配規(guī)則包含或運算符的并行多模式匹配的系統(tǒng)，其特征在于，所述生成模塊進一步包括規(guī)則解析模塊和節(jié)點處理模塊，

所述規(guī)則解析模塊，用于進行所述將所述規(guī)則集中包含或運算符的匹配規(guī)則從或運算符處分割成所述匹配規(guī)則的子規(guī)則，所述規(guī)則集中為確定規(guī)則的匹配規(guī)則作為其自身的子規(guī)則，并將所有子規(guī)則按照AC算法生成AC自動機的過程，并在確定所述匹配規(guī)則的子規(guī)則后，標識所述匹配規(guī)則的子規(guī)則；

所述節(jié)點處理模塊，用于生成節(jié)點規(guī)則表，所述節(jié)點規(guī)則表記錄在所述AC自動機中的終態(tài)節(jié)點處匹配的所有子規(guī)則標識，以供所述匹配模塊在搜索時進行查找。

3.如權利要求2所述的匹配規(guī)則包含或運算符的并行多模式匹配的系統(tǒng)，其特征在于，所述在確定所述匹配規(guī)則的子規(guī)則后，標識所述匹配規(guī)則的子規(guī)則進一步為標識所述匹配規(guī)則，并使用所述子規(guī)則所屬匹配規(guī)則的標識來標識所述子規(guī)則。

4.如權利要求2所述的匹配規(guī)則包含或運算符的并行多模式匹配的系統(tǒng)，其特征在于，所述匹配模塊進一步包括

狀態(tài)轉移模塊，用于進行所述讀取搜索對象，按AC算法應用所述AC自動機進行搜索的過程；

處理模塊，用于查找所述節(jié)點規(guī)則表，依次獲得當前終態(tài)節(jié)點匹配的子規(guī)則的標識，確定所述搜索對象同當前終態(tài)節(jié)點匹配的子規(guī)則所屬的匹配規(guī)則匹配，并輸出該匹配規(guī)則的標識。

5.一種匹配規(guī)則包含或運算符的并行多模式匹配的方法，其特征在于，包括：

步驟1，讀取包含匹配規(guī)則的規(guī)則集，將所述規(guī)則集中包含或運算符的匹配規(guī)則從或運算符處分割成所述匹配規(guī)則的子規(guī)則，所述子規(guī)則為確定規(guī)則，所述規(guī)則集中為確定規(guī)則的匹配規(guī)則作為其自身的子規(guī)則，并將所有子規(guī)則按照AC算法生成AC自動機，并輸出所述AC自動機；

步驟2，讀取搜索對象和所述AC自動機，按AC算法應用所述AC自動機進行搜索，判斷所述搜索對象是否匹配所述匹配規(guī)則的至少一個子規(guī)則，如果是，則所述搜索對象匹配所述匹配規(guī)則，并輸出匹配結果。

6.如權利要求5所述的匹配規(guī)則包含或運算符的并行多模式匹配的方法，其特征在于，所述步驟1進一步包括，

步驟61，在確定所述匹配規(guī)則的子規(guī)則后，標識所述匹配規(guī)則的子規(guī)則；

步驟62，在生成所述AC自動機后，生成節(jié)點規(guī)則表，記錄在所述AC自動機中的終態(tài)節(jié)點處匹配的所有子規(guī)則標識，以供在搜索時進行查找。

7.如權利要求6所述的匹配規(guī)則包含或運算符的并行多模式匹配的方法，其特征在于，所述步驟61進一步為標識所述匹配規(guī)則，并使用所述子規(guī)則所屬匹配規(guī)則的標識來標識所述子規(guī)則。

8.如權利要求5所述的匹配規(guī)則包含或運算符的并行多模式匹配的方法，其特征在于，所述步驟2進一步包括，

步驟81，讀取搜索對象的一個字符，按所述AC算法進行在所述AC自動機中進行狀態(tài)轉移，轉移到一個狀態(tài)節(jié)點，執(zhí)行步驟82；

步驟82，判斷該狀態(tài)節(jié)點是否是終態(tài)節(jié)點，如果是，查找所述節(jié)點規(guī)則表，依次獲得匹配的子規(guī)則標識，確定所述搜索對象同當前終態(tài)節(jié)點匹配的子規(guī)則所屬的匹配規(guī)則匹配，并輸出該匹配規(guī)則的標識，執(zhí)行步驟81直至所述搜索對象被讀取完。