[發明專利]一種正則表達式匹配方法及裝置

有效

• 申請號: 201310603980.X
• 申請日: 2013-11-25
• 公開（公告）號: CN103617226B
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 王宇平;王雨濛
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司11291
• 代理人: 黃志華

1.一種正則表達式匹配方法，其特征在于，包括：

確定正則表達式的指紋；

根據所述正則表達式的指紋，確定所述正則表達式的代表指紋；

根據所述正則表達式的代表指紋，確定正則表達式組，并確定所述正則表達式組的代表指紋；

基于所述正則表達式組的代表指紋與所述正則表達式組編譯成的確定有限狀態自動機DFA的對應關系，對待匹配數據進行正則表達式匹配；

所述確定正則表達式的指紋，具體包括：

提取正則表達式的必經字符串，并截取預設長度的所述必經字符串作為所述正則表達式的指紋；所述必經字符串為能夠匹配上所述正則表達式的數據中都包含的字符串。

2.根據權利要求1所述的方法，其特征在于，所述提取正則表達式的必經字符串，具體包括：

當正則表達式中至少包含嵌套元字符時，若最外層嵌套元字符中不包含分支元字符，且最外層嵌套元字符后沒有重復元字符，則提取刪除所述正則表達式的最外層嵌套元字符后的正則表達式的必經字符串，作為所述正則表達式的必經字符串；

當正則表達式中至少包含嵌套元字符和分支元字符時，若任何嵌套元字符中均不包含分支元字符，或僅最外層嵌套元字符包含分支元字符，確定所述正則表達式包括的不包含分支元字符的分支正則表達式；提取所述分支正則表達式的必經字符串；確定所述正則表達式的必經字符串為所有分支正則表達式的必經字符串中都包含的字符串；

當正則表達式中至少包含嵌套元字符、分支元字符和重復元字符時，若任何嵌套元字符中均不包含重復元字符，確定所述正則表達式包括的不包含分支元字符的分支正則表達式；提取所述分支正則表達式的必經字符串；確定所述正則表達式的必經字符串為所有分支正則表達式的必經字符串。

3.根據權利要求1至2任一所述的方法，其特征在于，所述根據所述正則表達式的指紋，確定所述正則表達式的代表指紋，具體包括：

將所述正則表達式的指紋進行哈希，選擇哈希沖突最小的指紋作為所述正則表達式的代表指紋。

4.根據權利要求1至2任一所述的方法，其特征在于，所述根據所述正則表達式的代表指紋，確定正則表達式組，具體包括：

根據所述正則表達式的代表指紋的哈希值，將所述正則表達式放入哈希槽中，并判斷放入的哈希槽中是否已存在正則表達式；

在放入的哈希槽中已存在正則表達式時，若所述正則表達式的代表指紋和已存在正則表達式的代表指紋相同，則將所述正則表達式和已存在正則表達式合并為一個正則表達式組。

5.根據權利要求4所述的方法，其特征在于，所述將所述正則表達式和已存在正則表達式合并為一個正則表達式組之前，還包括：

判斷所述正則表達式和已存在正則表達式合并為一個正則表達式組后編譯成的DFA狀態數量是否超過預設閾值；

所述將所述正則表達式和已存在正則表達式合并為一個正則表達式組，具體包括：

在所述正則表達式和已存在正則表達式合并為一個正則表達式組后編譯成的DFA狀態數量不超過預設閾值時，將所述正則表達式和已存在正則表達式合并為一個正則表達式組。

6.根據權利要求1至2任一所述的方法，其特征在于，所述確定所述正則表達式組的代表指紋，具體包括：

將所述正則表達式組的指紋進行哈希，選擇哈希值在所有正則表達式組的代表指紋的哈希值中出現次數最少的指紋作為所述正則表達式組的代表指紋。

7.一種正則表達式匹配裝置，其特征在于，包括：

第一確定單元，用于確定正則表達式的指紋；

第二確定單元，用于根據所述正則表達式的指紋，確定所述正則表達式的代表指紋；

第三確定單元，用于根據所述正則表達式的代表指紋，確定正則表達式組，并確定所述正則表達式組的代表指紋；

匹配單元，用于基于所述正則表達式組的代表指紋與所述正則表達式組編譯成的確定有限狀態自動機DFA的對應關系，對待匹配數據進行正則表達式匹配；

所述第一確定單元，具體用于提取正則表達式的必經字符串，并截取預設長度的所述必經字符串作為所述正則表達式的指紋；所述必經字符串為能夠匹配上所述正則表達式的數據中都包含的字符串。