下推自動機

下推自動機可以形象的理解為，把有限狀態自動機擴展使之可以存取一個棧。每一個下推自動機都接受一個形式語言。下推自動機存在確定與非確定兩種形式，兩者並不等價。﹙對有限狀態自動機兩者是等價的﹚被非確定下推自動機接受的語言是上下文無關語言。

如果把下推自動機擴展，允許一個有限狀態自動機存取兩個棧，我們得到一個能力更強的自動機，這個自動機與圖靈機等價。

下推自動機 M 是如下的一個七元組 ( Q, Σ, Γ, δ, q0, Z0, F ) ，其中：

* Q 是一個有窮狀態集合；

* Σ 是一個字母表，稱為輸入字母表。

* Γ 是一個字母表，稱為棧字母表。

* q0 屬於 Q ，是初始狀態。

* Z0 屬於 Γ ，是一個特殊的棧符號，稱為棧起始符號。

* F 包含於 Q ，是終結狀態集合。

* δ : Q×(Σ∪{ε})×Γ -> Q×Γ* 是 M 的動作函數。 ^[1] 

在給出下推自動機的定義之前先做如下的約定:Q, Γ同上面一致 , Q , Γ, Γ*中的元素分別表示為 :q , Z ,π,其中 Γ的克林閉包 Γ* =Γ0∪ Γ∪ Γ2∪ Γ3∪ … ,這裏 Γ0 ={ε}, π同字符表中的字的概念類似叫作棧符號下推轉換矩陣[ 2] :一個矩陣 M ∈(P(∑ ∪ ε)Q×Q)JΓ*×Γ*如果對所有的 π1 , π2 ∈ Γ*,有 ,Mπ1=Zπ4,π2=π3π4 =MZ ,π3 　Z ∈ Γ, π4 ∈ Γ*0則稱該矩陣為下推轉換矩陣.對任意 Z , 非零矩陣塊 MZ ,π表示棧頂符號 Z 出棧, 棧符號表上的字 π入棧.(由於下推自動機也是無窮語言的一種有窮描述機制 ,故描述它動作的下推轉換矩陣也必是有限個非零塊矩陣組成 ,也就是説下推轉換矩陣必是行列有限的 .)J 表示矩陣是行列有限矩陣 .由下推轉換矩陣的定義可知下推轉換矩陣是一個分塊矩陣,它的每一個分塊 Mπ1,π2, π1 , π2 ∈Γ*是一個 P(∑ ∪ε)Q×Q矩陣 .進一步直觀地來理解下推轉換矩陣:假設下推棧包含 Zπ,三元組(q , a , Z)其中 a∈ ∑ ∪ ε, 它表示自動機在狀態 q , 棧頂符號為 Z , 讀入字符為 a ,與上面自動機的動作一樣 :狀態 q 變為 q1 ,棧頂符號 Z 彈出 ,並將 π1 中的符號從右到左依次壓入棧 ,然後將讀頭向右移動一個字符而指向字符串的下一個字符,記為狀態(q1 , π1).下推轉換矩陣表示為 :

a ∈ (MZπ′,π1π′)q, q1 (*)

特別地下推轉換矩陣的定義要確保與 π′無關(*)這一條件的滿足 .稱((q , Zπ′),(q1 , π1 π′))是用 a 標記的邊 .邊的標記也就是字母表上的字母 .狀態(q , π)到(q′, π′)的一條路是 c ,它是邊的有序序列 :((q0 , π0),(q1 , π1))((q1 , π1),(q2 , π2)), …,((qk-1 , πk-1)(qk , πk)), k ≥0 且(q0 , π0)=(q, π), (qk , πk)=(q′, π′),記為 c ∶(q , π)※(q′, π′),並稱 k 為路c 的長度, 記為 c .如果 at 是邊((qt-1 , πt-1),(qt , πt))的標記,1 ≤t ≤k ,則稱 a1a2 …ak 為路c 的標記 ,記為‖c‖ , 也就是 ‖c ‖ =a1 a2 …ak .路的標記也就是字母表中的字.對於每個狀態(qt , πt),((qt , πt),(qt , πt))的路稱作空路 ,記為 λt ,並有 λt =0 , ‖λt ‖ =ε若c ∶(q1 , π1)※(q2 ,π2), d ∶(q2 , π2)※(q3 , π3)是路 ,則它們的合成(也就是字母表的乘法)定義為 cd ∶(q1 , π1)※(q3 , π3), 且有cd = c + d , ‖cd ‖ =‖c ‖ ‖d ‖ .從而在上面的基礎上給出下推自動機在半環中的定義 .下推自動機 :A=(Q , ∑ , Γ, M , q0 , Z0 ,F)其中, M 是下推轉換矩陣, 其他符號同上面下推自動機的定義相同 .下推自動機 A=(Q, ∑ , Γ, M , q0 , Z0 ,F)的行為‖A‖ ∈ P(∑*)定義為 :‖A‖ = ∪qf∈F ∑∞k=0 c∶(q ∑ i0,Z0)※(qf,ε),|c|=k‖c ‖ ,如果 w ∈ ‖A‖ ,則稱 w 被‖A‖接收或者產生.下面將給出下推轉移矩陣和下推自動機行為之間的關係:(M)kπ1,π2 q1, q2 是所有長度為 k 的路c ∶(q1 ,π1)※(q2 , π2)的標記 ,即 (M)kπ1,π2q1, q2 =c(q ∑ 1,π1)※(q2,π2),|c|=k‖c ‖ .對 k 實施數學歸納法證明 :這裏要用到半環同構即任意的 M′∈ 〈P(∑*)(Q×Γ*)×(Q×Γ*)J , +, · , 0 , E′〉, 必有 M′(q1, π1),(q2,π2) =(Mπ1, π2 )q1, q2, 其中M ∈〈P(∑*)(Q×Γ*)×(Q×Γ*)J , +, · , 0 , E′〉.當 k =0 時 ,(M0π1, π2 )q1, q2 =M′0(q1,π1),(q2, π2) =E′(q1,π1),(q2, π2=δ(q1, π1),(q2π2)ε, 同時 c∶(π ∑ 1, q1)※(π2, q2),|c|=0‖c‖ =δ(q1, π1),(q2,π2)ε,所以 k =0 結論成立.假設對 k -1 ,k ≥1 結論成立, 則(M)kπ1,π2q1, q2 =M′k(q1,π1),(q2,π2)=(M′k-1 M′)(q1,π1),(q2,π2)=(q,π)∑∈Q×Γ*M′k-1(q1,π1

),(q,π)M′(q, π),(q2, π2) =(q,π)∑∈Q×Γ* c ∑ 1∶(q1,π1)※(q,π),|c|=k-1‖c1 ‖c ∑ 2:(q,π)※(q2,π2),|c|=1‖c2 ‖ =(q,π)∑∈Q×Γ* c ∑ 1∶(q1,π1)※(π, q),|c|=k-1c ∑ 2∶(q, π)※(q2, π2),|c|=1‖c1c2 ‖ =c∶(q,π)※(∑q′,π′),|c|=k‖c ‖下推轉換矩陣和移動函數的等價性 :任意 w ∈((M)kπ0,πk)q0, qk, 存在即時描述序列(q0 , a0 w0 , π0),(q1 , a2 ,w1 , π1), … ,(qk ,ε, πk),其中當 i ≤j 時, wj 是 w i 的後綴, 且 w =a0a1 …ak-1 .讀完字 w 後, 自動機 A從狀態(q0 , π0)轉移到(qk , πk),即從 q0 轉變為 qk ,同時下推棧的符號串由 π0 替換為 πk .這個序列用移動函數來描述為:

δ(q0 , a0 , π0)※(q1 , π1), δ(q1 , a1 ,π1)※(q2 , π2), …, δ(qk-1 , ak-1 , πk-1)※(qk ,πk). ^[1] 

基於下推自動機的 XML 數據流遞歸查詢研究

可擴展標記語言(XML)由於其易用性和強大的複雜數據描述能力，已逐漸成為因特網上數據交換的標準。很多流行的數據庫引擎已經開始通過增加對於這種新數據類型以及相關操作的支持來滿足新的需求。XML數據流上的應用是XML研究的一個很重要的方面，在新的基於Web的應用場景下，有研究已經提出，有效地處理XML數據流[1-3]上的XPath、XQuery查詢將會成為下一代信息系統的特點。可擴展標記語言(XML)由於其易用性和強大的複雜數據描述能力，已逐漸成為因特網上數據交換的標準。很多流行的數據庫引擎已經開始通過增加對於這種新數據類型以及相關操作的支持來滿足新的需求。XML數據流上的應用是XML研究的一個很重要的方面，在新的基於Web的應用場景下，有研究已經提出，有效地處理XML數據流[1-3]上的XPath、XQuery查詢將會成為下一代信息系統的特點。出現了存在遞歸結構的 XML 數據流，如果當包含和謂詞的XPath對它進行遞歸查詢，將會發生多重匹配從而產生大量的匹配模式，需要花費大量的時間和空間管理這些匹配模式，這樣會嚴重影響到查詢處理的性能。面對這種情況，提出一種基於下推自動機技術的處理方法，能有效地實現XML數據流的遞歸查詢。

1.1 XML 數據流遞歸查詢

定義 1 XML 數據流對應的文檔樹結構中，從根到葉子的路徑上，相同名字的元素結點重複出現，我們稱作遞歸的XML 數據流[6]，在數據流中，所有從根到葉子的路徑當中，相同名字的元素結點重複出現次數的數目稱作元素結點的遞歸深度，符號為 R。

定義 2 在查詢 XML 數據流時，相互嵌套的不同深度的XML 元素可能會匹配 XPath 查詢表達式的同一個置步，這種現象稱為多重匹配。

2 基於 PDA 的遞歸查詢

N0N1 … Nn/O 作為查詢表達式最通用的表示方式，Ni表示XPath 的置步，O 表示查詢結果的輸出形式。由於 XPath 由許多置步組成，查詢目的是通過這些置步來定位 XML 文檔片段。置步處理模塊作為整個查詢模型的基本組成部分，它是由 XPath 每個置步轉化而來，該模塊實質是一個狀態集，這些狀態包括主幹路徑匹配狀態和謂詞匹配狀態，並且有模塊運行的開始狀態，狀態之間用箭頭連接在一起，箭頭上標示了跳轉條件，如果置步中存在謂詞，主幹路徑匹配狀態中有屬性為TRUE 的狀態，表明主幹路徑匹配和謂詞檢驗成功；另外主幹路徑匹配狀態中有屬性為 FALSE 的狀態，表明主幹路徑匹配成功和謂詞檢驗不成功；如果置步中不存在謂詞，則主幹路徑匹配狀態中只有屬性為 TRUE 的狀態，表明主幹路徑匹配和謂詞檢驗成功，這樣與謂詞存在的情況有良好的銜接。圖 3是置步/person[name.text() = lee]轉化成處理模塊的一個實例，S0 是整個模塊處理的開始狀態，其中S0、S1 和S3 是主幹路徑匹配狀態，其它狀態是謂詞匹配狀態。<Person>標示的箭頭，表示只有 Person 元素的開始事件才能通過箭頭到達所指狀態，</person>標示的箭頭，表示只有 Person 元素的結束事件才能通過箭頭到達所指狀態，模塊中其它標示的箭頭儘管名稱不同，但含義類似。查詢過程中，當前活躍狀態為 S2 時，將會出現 3 種情況：①Person 元素下無 Name 元素文本值，則狀態直接從 S2 跳到 S1，狀態 S1 屬性為 False，謂詞檢驗不成功；②Person 元素下有 Name 元素，但 Name 元素的文本值不符合要求，則狀態從S2—>S4—>S1；主幹路徑匹配成功和謂詞檢驗不成功；③Person 元素下有 Name 元素，並且 Name 元素的文本值符合要求，則狀態從 S2—>S5—>S3，狀態 S3 屬性為 TRUE，主幹路徑匹配成功和謂詞檢驗成功。

3 性能測試與分析

為了驗證本文提出的算法性能和相對於以前工作的性能提升，本文用 Java 語言實現了基於 PDA 的遞歸查詢算法，並進行了性能測試，並且和之前工作基於 LazyDFA 算法做了比較。實驗平台為：操作系統為 Windows XP，CPU 為雙核處理器，內存 1024M 實驗數據，採用了 IBM 的 XML Generator[9]生成不同遞歸層次結構的 XML 數據集。XML 數據流處理對時間和內存的耗用量有嚴格的要求，對於XML數據流的遞歸查詢，數據流的遞歸深度是影響這兩個方面的主要因素，算法採用了整數移位運算的方式，它便於對匹配模式的保存和檢驗，同時謂詞匹配位檢驗和緩存操作，有利於快速處理潛在的緩存結果。通過從運行時間和內存使用量上來對兩個算法進行比較，從圖 5、圖 6 的實驗結果顯示，針對不同複雜程度的XML數據流，基於 PDA 算法的性能要優於 LazyDFA 算法。 ^[2]