[發明專利]壓縮正則表達式的方法、匹配字符串的方法及裝置

在審

• 申請號: 201310410575.6
• 申請日: 2013-09-10
• 公開（公告）號: CN104424329A
• 公開（公告）日: 2015-03-18
• 發明（設計）人: 胡晶;翟素平
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京龍雙利達知識產權代理有限公司 11329
• 代理人: 毛威;張亮

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

確定正則表達式的有限自動機FA包括的所有基本狀態以及所述所有基本狀態之間的遷移關系；

確定所述所有基本狀態中能夠合并為復合狀態的至少兩個基本狀態，其中，所述至少兩個基本狀態包括入態和出態，所述至少兩個基本狀態以所述入態為起點并以所述出態為終點依次遷移，第一基本狀態的下一狀態不包括第二基本狀態，且當第三基本狀態具有除所述依次遷移所對應的第一下一狀態之外的第二下一狀態時，所述第三基本狀態的第二下一狀態分別相同且分別在相同的標簽下遷移至所述第二下一狀態，所述出態也在所述相同的標簽下遷移至所述第二下一狀態，其中，所述第一基本狀態為所述所有基本狀態中除所述至少兩個基本狀態之外的基本狀態，所述第二基本狀態為所述至少兩個基本狀態中除所述入態之外的基本狀態，所述第三基本狀態為所述至少兩個基本狀態中除所述出態之外的基本狀態；

根據所述復合狀態，生成所述正則表達式的FA狀態遷移表。

2.根據權利要求1所述的方法，其特征在于，所述FA狀態遷移表包括所述第一基本狀態的基本遷移表項和所述復合狀態的復合遷移表項，其中，所述FA狀態遷移表的每個遷移表項均包括匹配條件和所述匹配條件對應的下一狀態。

3.根據權利要求2所述的方法，其特征在于，所述復合狀態的復合遷移表項中的匹配條件為由所述至少兩個基本狀態中的每個基本狀態遷移到所述第一下一狀態時的標簽依次合并而成的復合標簽，所述匹配條件對應的下一狀態為所述出態的第一下一狀態，其中，所述出態的第一下一狀態為所述出態具有的所有下一狀態中除所述第二下一狀態之外的下一狀態。

4.根據權利要求2或3所述的方法，其特征在于，當所述第二基本狀態具有所述第二下一狀態時，所述FA狀態遷移表還包括所述復合狀態的基本遷移表項，所述基本遷移表項中的匹配條件為所述相同的標簽，所述匹配條件對應的下一狀態為所述第二下一狀態。

5.一種匹配字符串的方法，其特征在于，包括：

獲取待匹配字符串和有限狀態機FA狀態遷移表，所述FA狀態遷移表的遷移表項包括匹配條件和所述匹配條件對應的下一狀態，且所述FA狀態遷移表包括基本狀態的基本遷移表項和復合狀態的復合遷移表項，所述復合遷移表項中的匹配條件能夠與單個字符完全匹配，所述基本遷移表項中的匹配條件能夠與由至少兩個字符構成的字符串完全匹配；

當當前狀態為非接受狀態時，確定所述當前狀態為基本狀態或復合狀態，其中，所述當前狀態以FA的初始狀態為起點；

當所述當前狀態為復合狀態時，讀取所述待匹配字符串的未匹配部分的首字符；

確定所述FA狀態遷移表中是否存在與所述首字符匹配的所述復合狀態的基本遷移表項；

當所述FA狀態遷移表中存在與所述首字符匹配的所述復合狀態的基本遷移表項時，遷移至所述匹配的基本遷移表項中的下一狀態。

6.根據權利要求5所述的方法，其特征在于，所述方法還包括：

當所述FA狀態遷移表中不存在與所述首字符匹配的所述復合狀態的基本遷移表項時，確定所述FA狀態遷移表中是否存在與所述首字符部分匹配的所述復合狀態的復合遷移表項；

當所述FA狀態遷移表中存在與所述首字符部分匹配的所述復合狀態的復合遷移表項時，依次讀取所述未匹配部分中的字符以獲得第一字符串，其中，所述第一字符串以所述首字符為起點且長度與所述部分匹配的復合遷移表項中的匹配條件相對應；

確定所述第一字符串是否與所述部分匹配的復合遷移表項中的匹配條件完全匹配；

當所述第一字符串與所述部分匹配的復合遷移表項中的匹配條件完全匹配時，遷移至所述部分匹配的復合遷移表項中的下一狀態。

7.根據權利要求6所述的方法，其特征在于，所述確定所述FA狀態遷移表中是否存在與所述首字符部分匹配的所述復合狀態的復合遷移表項，包括：

分別將所述首字符與所述FA狀態遷移表中包括的所述復合狀態的至少一個復合遷移表項中的每個復合遷移表項的匹配條件的起始部分進行匹配，以分別確定所述首字符是否與所述每個復合遷移表項部分匹配；

當所述復合狀態的至少一個復合遷移表項中存在與所述首字符部分匹配的復合遷移表項時，確定所述FA狀態遷移表中存在與所述首字符部分匹配的所述復合狀態的復合遷移表項。