[發明專利]多字符串模式匹配方法、裝置、計算機設備及存儲介質

在審

• 申請號: 202110270270.4
• 申請日: 2021-03-12
• 公開（公告）號: CN112784127A
• 公開（公告）日: 2021-05-11
• 發明（設計）人: 劉瑩;王士誠;張夢豪;李冠宇;劉暢;徐明偉
• 申請（專利權）人: 清華大學
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 北京聿宏知識產權代理有限公司 11372
• 代理人: 吳大建;金淼

1.一種多字符串模式匹配方法，其特征在于，包括：

獲取字符串匹配的規則集；

從所述規則集中提取字符模式串集合及字符模式串的邏輯關系；

基于自動機算法，根據所述字符模式串集合，構建無條件轉移表及失效轉移表；

對所述失效轉移表的狀態進行編碼，為所述失效轉移表的每一狀態分配三元碼及精確碼，得到編碼后的所述失效轉移表；

根據所述無條件轉移表及編碼后的所述失效轉移表，構建非確定有限狀態自動機匹配表；

根據所述字符模式串集合及所述邏輯關系，構建策略匹配表；

根據所述非確定有限狀態自動機匹配表及所述策略匹配表對字符串進行匹配，輸出匹配結果。

2.根據權利要求1所述的多字符串模式匹配方法，其特征在于，所述對所述失效轉移表的狀態進行編碼，為所述失效轉移表的每一狀態分配三元碼及精確碼，得到編碼后的所述失效轉移表的步驟，包括：

基于陰影編碼算法，對所述失效轉移表的狀態進行編碼，為所述失效轉移表的每一狀態分配在匹配字段中的所述三元碼及在動作字段中的所述精確碼，得到編碼后的所述失效轉移表。

3.根據權利要求1所述的多字符串模式匹配方法，其特征在于，所述對所述失效轉移表的狀態進行編碼的步驟，包括：

從所述失效轉移表轉中構建失效轉移樹；

對所述失效轉移樹的狀態進行編碼。

4.根據權利要求1所述的多字符串模式匹配方法，其特征在于，所述根據所述無條件轉移表及編碼后的所述失效轉移表，構建非確定有限狀態自動機匹配表的步驟，包括：

將所述無條件轉移表的轉移邊轉化成表項，并對所述表項賦予優先級，得到轉化后的所述無條件轉移表；

根據轉化后的所述無條件轉移表及編碼后的所述失效轉移表，構建所述非確定有限狀態自動機匹配表。

5.根據權利要求1所述的多字符串模式匹配方法，其特征在于，所述根據所述字符模式串集合及所述邏輯關系，構建策略匹配表的步驟，包括：

將所述字符模式串集合及所述邏輯關系轉換成布爾表達式；

將所述布爾表達式轉換成合取范式，構建所述策略匹配表。

6.根據權利要求1所述的多字符串模式匹配方法，其特征在于，所述根據所述非確定有限狀態自動機匹配表及所述策略匹配表對字符串進行匹配，輸出匹配結果的步驟，包括：

對所述非確定有限狀態自動機匹配表中狀態的步長進行擴大，得到擴大后的所述非確定有限狀態自動機匹配表；

根據擴大后的非確定有限狀態自動機匹配表及所述策略匹配表對字符串進行匹配，輸出匹配結果。

7.根據權利要求6所述的多字符串模式匹配方法，其特征在于，所述非確定有限狀態自動機匹配表包括初始狀態和非初始狀態；

所述對所述非確定有限狀態自動機匹配表的步長進行擴大，得到擴大后的所述非確定有限狀態自動機匹配表的步驟，包括：

根據所述無條件轉移表，對所述非初始狀態的步長進行擴大；

通過增加通配符方式，對所述初始狀態的步長進行擴大，得到擴大后的所述非確定有限狀態自動機匹配表。

8.一種多字符串模式匹配裝置，其特征在于，包括：

獲取模塊，用于獲取字符串匹配的規則集；

提取模塊，用于從所述規則集中提取字符模式串集合及字符模式串的邏輯關系；

轉移表構建模塊，用于基于自動機算法，根據所述字符模式串集合，構建無條件轉移表及失效轉移表；

編碼模塊，用于對所述失效轉移表的狀態進行編碼，為所述失效轉移表的每一狀態分配三元碼及精確碼，得到編碼后的所述失效轉移表；

第一構建模塊，用于根據所述無條件轉移表及編碼后的所述失效轉移表，構建非確定有限狀態自動機匹配表；

第二構建模塊，用于根據所述字符模式串集合及所述邏輯關系，構建策略匹配表；

匹配模塊，用于根據所述非確定有限狀態自動機匹配表及所述策略匹配表對字符串進行匹配，輸出匹配結果。