[發明專利]一種從有限自動機生成簡短正則表達式的方法

在審

• 申請號: 202110966638.0
• 申請日: 2021-08-23
• 公開（公告）號: CN113657078A
• 公開（公告）日: 2021-11-16
• 發明（設計）人: 高俊濤;劉云峰;文必龍;王志寶;王永安
• 申請（專利權）人: 東北石油大學
• 主分類號: G06F40/151
• 分類號: G06F40/151
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 馮炳輝

1.一種從有限自動機生成簡短正則表達式的方法，其特征在于，該方法是利用狀態消減法將有限自動機轉換為正則表達式，通過搜索狀態消減序列的候選集合，獲得最優狀態消減序列，最終生成簡短的正則表達式；其包括以下步驟：

S1、對于候選狀態消減序列空間，定義臨時變量S*存儲當前最優狀態消減序列，定義臨時變量L存儲當前最短正則表達式長度，變量S*和L作為搜索候選狀態消減序列空間過程的臨時變量；

S2、用表達式自動機描述狀態消減的中間結果，根據表達式自動機規模估算生成的正則表達式的長度；

S3、基于臨時變量S*和L，對候選狀態消減序列空間進行剪枝處理，提高狀態消減序列的搜索效率；

S4、按照搜索到的最優狀態消減序列，采用狀態消減法將有限自動機轉換成簡短的正則表達式。

2.根據權利要求1所述的一種從有限自動機生成簡短正則表達式的方法，其特征在于，在步驟S1中，確定有限自動機進行狀態消減過程中，所有可能的狀態消減序列組成一個候選狀態消減序列空間，定義臨時變量S*存儲當前最優狀態消減序列，定義臨時變量L存儲當前最短正則表達式的長度。

3.根據權利要求1所述的一種從有限自動機生成簡短正則表達式的方法，其特征在于，在步驟S2中，對有限自動機進行狀態消減的每個階段需要選擇一個狀態進行消減并產生一個表達式自動機，用EAs表示，其中EA表示當前表達式自動機，s是一個狀態序列，s既能夠是包含所有待消減狀態的完整狀態消減序列，也能夠是不完整的只包含部分待消減狀態的狀態消減子序列；在狀態消減過程中，每個階段產生的表達式自動機依賴于當前消減的狀態和前一階段的表達式自動機，依據表達式自動機間依賴關系將給定有限自動機生成的表達式自動機全集構造成一棵樹，樹上每個結點代表一個表達式自動機，葉子結點對應的表達式自動機依賴于父結點對應的表達式自動機，由于葉子結點對應的表達式自動機只包含初態和終態，所以葉子結點唯一確定一個正則表達式，正則表達式的長度就是葉子結點表達式自動機的字符規模。

4.根據權利要求1所述的一種從有限自動機生成簡短正則表達式的方法，其特征在于，在步驟S3中，采用剪枝策略的最優序列搜索算法OSSAP(A_n)對候選狀態消減序列空間進行全局搜索，在搜索過程中調用NextSeq(l,d)算法進行剪枝操作，對每條狀態消減序列使用Eliminate(EA,q_k)算法進行狀態消減；將|EA|與當前記錄的最短長度L做比較，以判斷是否需要進行剪枝操作；如果|EA|小于L，那么需要進行剪枝操作；如果|EA|大于L，則不需要進行剪枝操作；最后，返回不需要進行剪枝操作的狀態消減序列或已進行剪枝操作的狀態消減序列，即返回最優狀態消減序列；其中，A_n表示需要進行n次消減操作的有限自動機，l表示狀態消減序列，d表示剪枝深度，EA表示當前表達式自動機，|EA|表示當前表達式自動機的字符規模，q_k表示第k個狀態消減序列。

5.根據權利要求4所述的一種從有限自動機生成簡短正則表達式的方法，其特征在于，所述NextSeq(l,d)算法實現以下過程：

按字典序枚舉下一個未被剪掉的狀態消減序列，如果狀態消減序列長度與搜索到的當前表達式自動機樹節點深度相等，則不需要剪枝，否則跳過以根節點到當前搜索節點為前綴的狀態消減序列來完成剪枝；對搜索節點之后的后綴狀態消減序列按升序排列以保證按字典序枚舉狀態消減序列。