[科普中国]-下推自动机

技术原理

下推自动机可以形象的理解为，把有限状态自动机扩展使之可以存取一个栈。每一个下推自动机都接受一个形式语言。下推自动机存在确定与非确定两种形式，两者并不等价。﹙对有限状态自动机两者是等价的﹚被非确定下推自动机接受的语言是上下文无关语言。

基本特征如果把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。

下推自动机 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 元素的结束事件才能通过箭头到达所指状态，模块中其它标示的箭头尽管名称不同，但含义类似。查询过程中，当前活跃状态为 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