蒙祖祈

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

0 引言

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

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

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

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

1 預備知識

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

2 狀態(tài)消減法

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

(2)

狀態(tài)消減法得到的正則表達式長度依賴于所選的狀態(tài)消減序列。以圖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生成的表達式明顯優(yōu)于消減序列s1。

(a) 六階自動機

(b) 消減q3后

(c) 消減q2后

3 向前預測的改進權重法

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

3.1 權重法

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

定義7 權重函數(shù)。對于自動機A上的狀態(tài)q，其權重函數(shù)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)表示狀態(tài)q輸入轉移上表達式集合；inq表示q不包含自身環(huán)的入度；outRE(q)表示q的輸出轉移上表達式集合；outq表示q不包含自身環(huán)的出度；loopRE(q)表示狀態(tài)q自身環(huán)轉移上的表達式；r表示確定型有限自動機中的字符或表達式自動機中的表達式；|r|表示字符或表達式的長度。

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

3.2 并行消減狀態(tài)策略

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

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

(a) 七階表達式自動機

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

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

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

3.3 向前預測策略

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

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

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

(4)

(a) 六狀態(tài)自動機

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

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

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

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

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

(5)

(6)

(7)

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

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

3.4 算法復雜度分析

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

(8)

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

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

4 實驗及結果分析

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

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

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

(9)

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

實驗結果如圖4所示。

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

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

5 總結

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

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