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

在審

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

本發明公開了一種從有限自動機生成簡短正則表達式的方法，包括：S1、對于候選狀態消減序列空間，定義臨時變量S*存儲當前最優狀態消減序列，定義臨時變量L存儲當前最短正則表達式長度；S2、用表達式自動機描述狀態消減的中間結果，根據表達式自動機規模估算生成的正則表達式的長度；S3、基于臨時變量S*和L，對候選狀態消減序列空間進行剪枝處理，提高狀態消減序列的搜索效率；S4、按照搜索到的最優狀態消減序列，采用狀態消減法將有限自動機轉換成簡短的正則表達式。本發明能被應用于軟件行為建模、基于模型的測試、軟件工程、計算與語言的研究等領域，顯著地提高自動機生成較短正則表達式的效率。

技術領域

本發明涉及正則語言模型的計算機技術領域，尤其是指一種從有限自動機生成簡短正則表達式的方法。

背景技術

正則表達式與有限自動機具有相同的表達能力，同屬于正則語言模型。既可以將正則表達式轉換成等價的有限自動機，也可以將有限自動機轉換成等價的正則表達式。由于正則表達式比較適合人類閱讀，現在已成為計算機各類系統工具和開發語言普遍采用的文本模式描述工具。將有限自動機轉換為簡明的正則表達式有助于正則語言理解和應用，也可以更廣泛地應用自動機學習的研究成果，研究從有限自動機生成簡明的正則表達式具有重要的理論價值和現實意義。從有限自動機生成正則表達式，已知的使用啟發式算法優化消減序列如：流量法、必經路徑法、回路計算法、動態度乘積法、靜態度乘積法、DM權重法等方法，生成的正則表達式總體長度均較長。

發明內容

本發明的目的在于克服現有技術的缺點與不足，提出了一種從有限自動機生成簡短正則表達式的方法，該方法引入了剪枝思想，為正則表達式生成問題研究提供了一條新思路，可有效提高正則表達式質量。

為實現上述目的，本發明所提供的技術方案為：一種從有限自動機生成簡短正則表達式的方法，該方法是利用狀態消減法將有限自動機轉換為正則表達式，通過搜索狀態消減序列的候選集合，獲得最優狀態消減序列，最終生成簡短的正則表達式；其包括以下步驟：

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

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

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

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

進一步，在步驟S1中，確定有限自動機進行狀態消減過程中，所有可能的狀態消減序列組成一個候選狀態消減序列空間，定義臨時變量S*存儲當前最優狀態消減序列，定義臨時變量L存儲當前最短正則表達式的長度。

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