確定型有限自動機生成最短正則表達式的啟發式算法研究

蒙祖祈

(東北石油大學 計算機與信息技術學院, 黑龍江 大慶 163318)

0 引言

正則表達式與確定型有限自動機同屬于正則語言模型，具有相同的表達能力，可以等價地相互轉換。雖然自動機容易轉化為高效的計算機內部程序，但狀態間復雜的變遷關系難于理解，無法在工程實踐中直接用于語法規則的設計和交流。根據自動機生成易于閱讀的正則表達式有助于正則語言的理解和應用，也可以更廣泛地應用自動機學習的研究成果，是形式語言領域研究的一個經典問題。

將確定型有限自動機轉換為正則表達式的經典方法主要有3種：狀態消減法、Brzozowski代數法和傳遞閉包法[1]。這3種方法生成的表達式質量均具有很大的不確定性，容易生成冗長的正則表達式，給表達式的閱讀和理解帶來困難。其實，無論采用哪種正則表達式生成方法，結果表達式的不確定性都源于狀態排序的差異，狀態排序的優化是提高正則表達式質量的關鍵。

目前，針對狀態排序優化問題出現一批啟發式狀態排序算法，在一定程度上提高了結果表達式的質量。依據啟發信息的類型，現有啟發式排序算法可以分為結構特征算法和局部特征算法兩類。結構特征算法由自動機拓撲結構決定狀態順序，包括橋狀態法、回路計算法和嵌套回路法；局部特征算法根據狀態自身及鄰接狀態決定狀態順序，包括流量法、靜態度乘積法、動態度乘積法和權重法。具體算法介紹請參照文獻[2]。

由于在各類實驗中權重法[3]效果優異，已成功應用于XML數據模式挖掘[4]和日常行為規則挖掘[5]等應用領域中。因此，本研究分析權重法的計算原理，研究向前預測的改進權重法。相較于其他啟發式算法，該算法能保證取得更優的結果表達式。

1 預備知識

有限自動機從識別語言的角度定義正則語言，包括確定型有限自動機和非確定型有限自動機，非確定型有限自動機可以轉化為確定型有限自動機。其形式化定義如下。

定義1 確定型有限自動機。確定型有限自動機是一個五元組A=(Q,Σ,δ,s,f)。其中，Q為有限的狀態集合；Σ為有限的輸入符號集合；s為自動機的一個初始狀態，簡稱初態，且s∈Q；f為自動機的一個終結狀態或接受狀態，簡稱終態，且f∈Q；δ為轉移函數，輸入一個狀態和一個符號，輸出一個狀態，若轉移函數的輸入狀態qi∈Q，符號是k∈Σ，輸出狀態qj∈Q，則qj=δ(qi,k)。

本研究針對精簡的確定型有限自動機，定義如下。

定義2 精簡性。若確定型有限自動機是精簡的，則自動機中的每個狀態都會出現在從初態到終態的某條路徑上。

在狀態消減過程中，精簡的確定型有限自動機將失去每次轉移只處理單個字符的性質，轉化為等價的表達式自動機，其形式化定義如下。

定義3 表達式自動機[6]。表達式自動機EA的定義如式(1)。

EA=(Q,Σ,δ,s,f)

(1)

式中，Q、Σ、s、f的定義與確定型有限自動機相同。δ為表達式轉移函數，有δ?Q×RΣ→Q。RΣ為一個正則表達式的集合，而且是Σ的超集。并規定：從任意狀態p到q，只有一個正則表達式α且α∈RΣ，滿足q=δ(p,α)。表達式自動機的字符規模|EA|是轉移函數δ所能接受的所有正則表達式的長度和。

雖然正則表達式應用十分廣泛，但其定義存在諸多差異。如UNIX正則表達式與POSIX正則表達式不同，PERL語言的正則表達式甚至可以容納非正則語言。下面給出正則表達式的形式化定義。

定義4 正則表達式。字符集Σ上的正則表達式被遞歸地定義如下。

若Φ表示空集，ε表示空字符串，則Φ和ε是正則表達式；

每個α∈Σ為正則表達式；

若α和β為正則表達式，則二者選擇運算(α|β)的結果為正則表達式；

若α和β為正則表達式，則二者連接運算(α·β)或(αβ)的結果為正則表達式；

若α為正則表達式，α*表示匹配α任意次，則α*也是正則表達式。

正則語言可以由無限多個等價的正則表達式描述，越簡短的正則表達式越容易表現語言的共性特征，也越容易理解。本研究采用正則表達式的長度作為衡量正則表達式質量的依據。

定義5 正則表達式長度。正則表達式α長度定義為α所包含字符數量，不包括元操作符及ε，標記為|α|。例如，正則表達式(a|b)(a·b)*的長度為4。

本研究將狀態消減法設定為自動機生成正則表達式的方法，這種方法的生成效果會受到狀態消減序列的影響。下面給出狀態消減序列的定義。

定義6 狀態消減序列。定義狀態消減序列s為〈q1,q2,…,qn-1,qn〉，序列長度|s|=n，如圖1所示。

2 狀態消減法

下面通過例子介紹狀態消減法，并分析該方法對狀態序列的敏感性。為保持自動機的語義不變性，每次狀態消減需要給前驅狀態和后繼狀態重建轉移。若消減狀態qk有m個前驅狀態和n個后繼狀態，則需要重建m×n個轉移，此外初態和終態不能是消減狀態。重建轉移的輸入表達式為式(2)。

(2)

狀態消減法得到的正則表達式長度依賴于所選的狀態消減序列。以圖1(a)中自動機為例，若消減序列為s1=〈q1,q4,q2,q3〉，生成的正則表達式為ea*bhp*e|ea*dp*e|ea*ck*jhp*e，長度為19。若消減序列為s2=〈q3,q2,q1,q4〉，生成的正則表達式為ea*(d|(b|ck*j)h)p*e，長度為10。消減序列s2生成的表達式明顯優于消減序列s1。

(a) 六階自動機

(b) 消減q3后

(c) 消減q2后

3 向前預測的改進權重法

向前預測的動態權重法以權重函數為核心，以向前預測為主要的改進策略，改進算法還包含了并行消減策略，進一步提高計算結果質量。

3.1 權重法

權重法的核心思想是，在每次狀態消減的迭代過程中，選擇消除權重最低的狀態。而權重函數的主要內容是給定一個狀態，根據該狀態的輸入轉移數，輸出轉移數，以及轉移上的字符長度，計算消減該狀態前后時自動機字符總量的變化。

定義7 權重函數。對于自動機A上的狀態q，其權重函數w(q)如式(3)。

w(q)=(inq-1)×∑r∈outRE(q)|r|+

(outq-1)×∑r∈inRE(q)|r|+

(3)

(inq×outq-1)×|loopRE(q)|

其中，inRE(q)表示狀態q輸入轉移上表達式集合；inq表示q不包含自身環的入度；outRE(q)表示q的輸出轉移上表達式集合；outq表示q不包含自身環的出度；loopRE(q)表示狀態q自身環轉移上的表達式；r表示確定型有限自動機中的字符或表達式自動機中的表達式；|r|表示字符或表達式的長度。

在每次迭代計算前，需要使用權重函數計算每個狀態的權重，并通過排序得到一個權重最小的狀態，而后才能使用狀態消減法消減該狀態。

3.2 并行消減狀態策略

在某些表達式自動機中，即使是運用向前預測策略，也會出現在同一狀態消減階段中得出多個最小權值狀態的情況。其狀態表達式自動機如圖2所示。

在第一個消減階段中，最小權值的狀態為q2、q3和q4，這兩個狀態的權值均為1，在常見的算法中多采用只消減其中一個狀態的操作，而最優狀態序列為〈q2,q3,q4,q1,q5〉。若此時消減的是狀態q2，則有可能在最終得出最優消減序列；但是若消減狀態q3或q4，則最后得出表達式的字符長度不會是最短的。因此在遇到多個最小權值狀態時，逐個消減狀態，可重構出多個自動機。將圖2(a)的自動機同時消減q2、q3和q4，形成圖2(b)，圖2(c)和圖2(d)中的3個表達式自動機，運用權重函數分別對3個自動機中的狀態計算權值后，可知在圖2(a)的自動機，能夠找到3個自動機中最小權值的狀態q3，它的權值為0。此時便可以拋棄另外兩個表達式自動機，沿著〈q2,q3〉這個狀態序列繼續消減狀態。

(a) 七階表達式自動機

(b) 消減q2后重構的表達式自動機

(c) 消減q3后重構的表達式自動機

(d) 消減q4后重構的表達式自動機

3.3 向前預測策略

向前預測策略的核心思想在于，首先連續消減k個狀態，然后運用權重函數，計算重構后自動機中各個狀態的權值，以各狀態中的最小權值作為自動機重構前的消減狀態權值，從而達到“向前預測”的目的。具體操作如算法1所示。

算法1，第2步中k的自減用于跳出遞歸，第5步的向前預測策略是利用權重函數計算重構后的表達式自動機中各狀態權值，步驟如算法2所示。

下面通過舉例說明向前預測策略的計算過程，以自動機為例,如圖3所示。

(4)

(a) 六狀態自動機

(b) 消減q1后重構的表達式自動機

(c) 消減q2后重構的表達式自動機

(d) 消減q3后重構的表達式自動機

(e) 消減q4后重構的表達式自動機

分別消減圖3(a)中的狀態q2，q3和q4，重構后的表達式自動機分別如圖3(c)，圖3(d)，圖3(e)所示。按照計算q1的權值的方法，同理計算其他狀態的權值則可得式(5)—式(7)。

(5)

(6)

(7)

比較W1，W2，W3和W4可知，此時W2和W4為最小值，因此應該先消減q2和q4。消減狀態后繼續運用向前預測策略消減狀態，可知最終狀態序列為〈q2,q4,q1,q3〉或〈q4,q2,q1,q3〉，與該自動機的最優狀態消減序列一致。

為保證預測步數k大于消減操作數n，在結合動態計算策略消減自動機的狀態時，應使k隨消減操作數n的減少而減少。當自動機的狀態數較少時，向前預測步數取1—3步左右，便可以獲得較短的表達式。而當自動機的狀態數較多時，向前預測步數可以取狀態數的開方，便可以獲取比其他啟發式算法短的表達式。

3.4 算法復雜度分析

改進算法的復雜度受到自動機狀態數和預測步數的影響。給定n階自動機A，權重法需要計算每個狀態的權值，故時間復雜度為O(n)；權重法只取權值最小的狀態，故空間復雜度為O(1)。消減一個狀態時，結合并行消減狀態后，向前預測k步的改進權重法的時間復雜度則約為式(8)。

(8)

在低階自動機中，當k取1到3便可以獲得較優序列，此時時間復雜度平均為O(n2)；而當狀態數較大，k取狀態數的開方時，此時時間復雜度平均為O(kn2)。

在遞歸計算過程需要存儲自動機，以矩陣形式進行存儲時，算法的空間復雜度約為O(kn2)。

4 實驗及結果分析

對比實驗在Pentium E6800的雙核CPU機器上運行，主頻為3.33 GHz，配置內存為4.00 GB，操作系統為Windows 10。實驗中使用C#作為編程語言，并以Visual Studio 2017作為實驗平臺。

在下述實驗中，自動機的隨機生成方案設計如下：給定自動機的狀態數量，狀態間轉移的建造概率服從0—1均勻分布，若概率大于0.5則建造轉移，反之則不建造。生成的自動機還需滿足2個條件：一是至少有一條從始態到終態的路徑；二必須是精簡的自動機。

該實驗是向前預測的改進權重法(實驗中簡稱為改進權重法)與其他啟發式算法的實驗進行正確率對比，實驗方案如下：生成6到10階自動機各1 000個，分別對各類啟發式算法進行測試，算法中包含隨機序列算法和自然序列算法，隨機序列算法指序列中的狀態隨機排列，自然序列算法指序列中的狀態按照狀態編號由小到大排列。記錄不同算法生成正則表達式的長度，然后與窮舉狀態序列算法所生成的最短正則表達式進行對比，得出算法的正確率μ，計算式如式(9)。

(9)

式中，C表示實驗時自動機的個數；lh表示根據啟發式算法生成序列，某個自動機轉化成正則表達式的長度；le則表示根據窮舉算法生成的正則表達式長度，即一個自動機能夠轉化的最優正則表達式。若上述二者相同，則令計數值k置1；否則記為0。通過計算計數值的統計數與自動機個數的比值獲取正確率。

實驗結果如圖4所示。

圖4 各類算法生成表達式的正確率對比圖

改進權重法的正確率明顯優于其他各類啟發式算法。在10階自動機的實驗中，其他算法的正確率不到10%，而改進權重法的正確率仍能保持50%以上。

5 總結

本研究分析了狀態消減法對消減序列的敏感性，在此基礎上，提出了向前預測的改進權重法。實驗結果顯示，在轉化低階自動機時，向前預測的改進權重法可以顯著提高生成最優表達式的正確率，但在轉化高階自動機時仍然存在正確率下降的問題。在下一步研究中，若是考慮利用智能優化或神經網絡等機器學習算法，有望進一步提高生成表達式質量。

目前，向前預測的改進權重法主要應用在吉林油田的錄井數據質量管理項目中，用于將樣本構造的自動機轉化成用正則表達式描述的數據質量校驗規則。在轉化少狀態的自動機時，該算法可以生成較多簡短的校驗規則。