[發(fā)明專利]一種正則表達(dá)式匹配方法及裝置

有效

• 申請?zhí)枺?/td>: 201310603980.X
• 申請日: 2013-11-25
• 公開（公告）號: CN103617226B
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計）人: 王宇平;王雨濛
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達(dá)信恒知識產(chǎn)權(quán)代理有限公司11291
• 代理人: 黃志華

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)處理領(lǐng)域，尤其涉及一種正則表達(dá)式匹配方法及裝置。

背景技術(shù)

正則表達(dá)式可以用簡單的語法描述復(fù)雜的數(shù)據(jù)特征，因此被廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測、文檔內(nèi)容檢索等多個領(lǐng)域。

判斷待匹配數(shù)據(jù)中是否包含正則表達(dá)式所描述的數(shù)據(jù)特征，稱為正則表達(dá)式的匹配。目前的正則表達(dá)式匹配方案中通常會將包含相同的字符串的正則表達(dá)式分為一組，該相同的字符串稱為該正則表達(dá)式組的廣義字符串，然后將每個正則表達(dá)式組編譯成一個確定有限狀態(tài)自動機(Deterministic Finite Automaton，DFA)，建立每個正則表達(dá)式組的廣義字符串與DFA的對應(yīng)關(guān)系，在進(jìn)行匹配時，先將待匹配數(shù)據(jù)和各正則表達(dá)式組的廣義字符串進(jìn)行匹配，確定出待匹配數(shù)據(jù)中包含正則表達(dá)式組的廣義字符串時，獲取與該包含的廣義字符串對應(yīng)的DFA，每個DFA由多個狀態(tài)以及狀態(tài)之間的轉(zhuǎn)移邊構(gòu)成，根據(jù)獲取的DFA通過狀態(tài)跳轉(zhuǎn)的方式實現(xiàn)正則表達(dá)式的匹配。

然而，采用上述方案將會生成大量的DFA，不但會占用大量的存儲空間，還會導(dǎo)致匹配速度較慢。

發(fā)明內(nèi)容

本發(fā)明實施例提供一種正則表達(dá)式匹配方法及裝置，用以解決正則表達(dá)式匹配速度較慢的問題。

第一方面，提供一種正則表達(dá)式匹配方法，包括：

確定正則表達(dá)式的指紋；

根據(jù)所述正則表達(dá)式的指紋，確定所述正則表達(dá)式的代表指紋；

根據(jù)所述正則表達(dá)式的代表指紋，確定正則表達(dá)式組，并確定所述正則表達(dá)式組的代表指紋；

基于所述正則表達(dá)式組的代表指紋與所述正則表達(dá)式組編譯成的確定有限狀態(tài)自動機DFA的對應(yīng)關(guān)系，對待匹配數(shù)據(jù)進(jìn)行正則表達(dá)式匹配。

結(jié)合第一方面，在第一方面的第一種實現(xiàn)方式中，所述確定正則表達(dá)式的指紋，具體包括：

提取正則表達(dá)式的必經(jīng)字符串，并截取預(yù)設(shè)長度的所述必經(jīng)字符串作為所述正則表達(dá)式的指紋；所述必經(jīng)字符串為能夠匹配上所述正則表達(dá)式的數(shù)據(jù)中都包含的字符串。

結(jié)合第一方面的第一種實現(xiàn)方式，在第一方面的第二種實現(xiàn)方式中，所述提取正則表達(dá)式的必經(jīng)字符串，具體包括：

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

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

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

結(jié)合第一方面或者第一方面的第一種實現(xiàn)方式或者第一方面的第二種實現(xiàn)方式，在第一方面的第三種實現(xiàn)方式中，所述根據(jù)所述正則表達(dá)式的指紋，確定所述正則表達(dá)式的代表指紋，具體包括：

將所述正則表達(dá)式的指紋進(jìn)行哈希，選擇哈希沖突最小的指紋作為所述正 則表達(dá)式的代表指紋。

結(jié)合第一方面或者第一方面的第一種實現(xiàn)方式或者第一方面的第二種實現(xiàn)方式或者第一方面的第三種實現(xiàn)方式，在第一方面的第四種實現(xiàn)方式中，所述根據(jù)所述正則表達(dá)式的代表指紋，確定正則表達(dá)式組，具體包括：

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

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

結(jié)合第一方面的第四種實現(xiàn)方式，在第一方面的第五種實現(xiàn)方式中，所述將所述正則表達(dá)式和已存在正則表達(dá)式合并為一個正則表達(dá)式組之前，還包括：

判斷所述正則表達(dá)式和已存在正則表達(dá)式合并為一個正則表達(dá)式組后編譯成的DFA狀態(tài)數(shù)量是否超過預(yù)設(shè)閾值；

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