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

有效

• 申請號: 202010042993.4
• 申請日: 2020-01-15
• 公開（公告）號: CN111222022B
• 公開（公告）日: 2023-05-12
• 發明（設計）人: 王彬;覃永靖;程詩堯;馬江波
• 申請（專利權）人: 奇安信科技集團股份有限公司;奇安信網神信息技術（北京）股份有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F9/448
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 苗曉靜

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

將每個預設正則表達式轉化為對應的非確定有窮自動機NFA狀態，基于部分NFA狀態生成目標確定有窮自動機DFA狀態；

當所述目標DFA狀態對應有子DFA狀態時，創建所述目標DFA狀態對應的所有子DFA狀態，并判斷每個子DFA狀態是否對應有次級子DFA狀態；

如果是，則創建每個子DFA狀態對應的所有次級子DFA狀態，并判斷每個次級子DFA狀態是否對應有下一層級的次級子DFA狀態；

如果否，則基于所述目標DFA狀態、每個子DFA狀態、每個次級子DFA狀態，及除所述部分NFA狀態之外的所有NFA狀態，生成目標混合有限自動機，以基于所述目標混合有限自動機對待匹配數據進行匹配。

2.根據權利要求1所述的基于正則表達式的匹配方法，其特征在于，所述將每個預設正則表達式轉化為對應的非確定有窮自動機NFA狀態，包括：

對每個預設正則表達式進行格式轉換，得到對應的目標正則表達式，其中每個目標正則表達式均用計算性算子表示；

將所述每個目標正則表達式轉化為抽象語法樹，并將每個抽象語法樹轉化為對應的NFA狀態。

3.根據權利要求1所述的基于正則表達式的匹配方法，其特征在于，所述基于所述目標DFA狀態、每個子DFA狀態、每個次級子DFA狀態，及除所述部分NFA狀態之外的所有NFA狀態，生成目標混合有限自動機，包括：

將所述目標DFA狀態、每個子DFA狀態、每個次級子DFA狀態中的最后一級DFA狀態標記為未完成DFA狀態，將除所述未完成DFA狀態之外的每級所有DFA狀態標記為已完成DFA狀態；

按照每個DFA狀態對應的層級順序，基于所述未完成DFA狀態及所有已完成DFA狀態，構建頭部半成品DFA；

將除所述部分NFA狀態之外的每個NFA狀態標記為尾部NFA，并基于所述頭部半成品DFA及所有尾部NFA狀態，生成目標混合有限自動機。

4.根據權利要求1所述的基于正則表達式的匹配方法，其特征在于，所述基于所述目標混合有限自動機執行匹配任務，包括：

通過所述目標混合有限自動機的當前DFA狀態執行匹配任務，并確定當前DFA狀態是否為未完成DFA狀態；

如果是，則判斷是否存在與所述未完成的DFA狀態對應的目標尾部NFA狀態；否則，繼續由下一級DFA狀態執行匹配任務，并確定所述下一級DFA狀態是否為未完成DFA狀態。

5.根據權利要求4所述的基于正則表達式的匹配方法，其特征在于，所述確定當前DFA狀態是否為未完成的DFA狀態，包括：

確定所述DFA狀態是否匹配成功，如果是，則確定所述當前DFA狀態是否為未完成DFA狀態，否則，停止匹配。

6.根據權利要求4所述的基于正則表達式的匹配方法，其特征在于，所述判斷是否存在與所述未完成的DFA狀態對應的目標尾部NFA狀態，包括：

若是，則獲取所述目標尾部NFA狀態，并確定與所述目標尾部NFA狀態對應的DFA狀態，并由與所述目標尾部NFA狀態對應的DFA狀態執行匹配任務，否則，停止匹配。

7.根據權利要求6所述的基于正則表達式的匹配方法，其特征在于，所述確定與所述目標尾部NFA狀態對應的DFA狀態，包括：

判斷是否存在與所述目標尾部NFA狀態對應的DFA狀態；

如果是，則由與所述目標尾部NFA狀態對應的DFA狀態繼續執行匹配任務，否則，由所述目標尾部NFA狀態執行匹配任務。