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

無效

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

技術領域

本發(fā)明屬于文本或網絡內容處理技術領域，尤其涉及一種匹配規(guī)則包含或運算符的并行多模式匹配的方法及系統(tǒng)。

背景技術

多模式匹配(Multiple?Pattern?String?Matching)是計算機科學領域中的基本問題之一，用于快速判斷某一數據塊中是否包含規(guī)則集中的某一或某些規(guī)則。多模式匹配技術廣泛應用于文本處理、網絡內容分析、入侵檢測、生物信息學、信息檢索等領域。

解決并行多模式匹配問題的經典方法之一，是基于有限狀態(tài)自動機的方法。該方法最初由Alfred?V.Aho和Margaret?J.Corasick于1975年提出，通常以發(fā)明者的名字簡稱為AC多模式匹配算法。AC算法的突出優(yōu)點在于其具有相同的最壞和平均性能，可用于處理各種模式集合(例如：不等長、大規(guī)模)，是一種高性能的多模式匹配方法。

對于各種確定性規(guī)則的模式匹配來說，AC算法(以及其變種)無疑是個非常優(yōu)秀的算法，但卻無法處理含有通配符的非確定性規(guī)則的匹配。

中國專利申請200810104416.2“一種并行多模式匹配的方法及系統(tǒng)”提供了一種應用AC算法來處理含有通配符的非確定規(guī)則的并行多模式匹配的方法。該發(fā)明公開了一種并行多模式匹配的系統(tǒng)，包括：

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

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

在具體的搜索過程中，當用AC算法匹配成功一個子規(guī)則后，按子規(guī)則標識查找匹配狀態(tài)表，獲得子規(guī)則所屬匹配規(guī)則的子規(guī)則總數和最近匹配的子規(guī)則順序號，比較子規(guī)則順序號和最近匹配的子規(guī)則順序號，如果子規(guī)則順序號比最近匹配的子規(guī)則順序號大1，則根據子規(guī)則順序號和子規(guī)則總數判斷所述子規(guī)則是否是最后一個子規(guī)則，如果是，則搜索對象同匹配規(guī)則匹配，如果不是，則更新匹配狀態(tài)表中最近匹配子規(guī)則順序號為當前匹配子規(guī)則的順序號。

上述發(fā)明將每個含有通配符的規(guī)則分解成多個子規(guī)則，并逐個檢查各個子規(guī)則是否按順序匹配成功。該方法解決了用AC算法來處理含有通配符的非確定規(guī)則，例如“334566*990000”，的并行多模式匹配問題，但該方法僅能用來處理兩個子模式之間的字符是任意的、長度也是任意的這種形式。如果要匹配兩個子模式是“或”關系的規(guī)則，如“334566|990000”，其中或運算符“|”表示搜索對象同子模式“334566”或“990000”中的至少一個匹配成功，則整個模式即為匹配成功，則上述發(fā)明則無法處理。

發(fā)明內容

為解決上述問題，本發(fā)明提供了一種匹配規(guī)則包含或運算符的并行多模式匹配的方法及系統(tǒng)，從而能夠應用AC算法對包含有或運算符的匹配規(guī)則進行匹配。

本發(fā)明公開了一種匹配規(guī)則包含或運算符的并行多模式匹配的系統(tǒng)，包括：

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

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

所述生成模塊進一步包括規(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ī)則標識，以供所述匹配模塊在搜索時進行查找；

所述在確定所述匹配規(guī)則的子規(guī)則后，標識所述匹配規(guī)則的子規(guī)則進一步為標識所述匹配規(guī)則，并使用所述子規(guī)則所屬匹配規(guī)則的標識來標識所述子規(guī)則。