1、第章结构模式识别第第7章结构模式识别章结构模式识别7.1结构模式识别概述结构模式识别概述7.2形式语言与自动机形式语言与自动机7.3高维文法和随机文法高维文法和随机文法7.4句法分析句法分析7.5文法推断文法推断习题习题第章结构模式识别7.1结构模式识别概述结构模式识别概述统计模式识别是从模式中提取一组特性的度量,构成特征向量来表示模式,然后通过划分特征空间的方式进行分类。对于较复杂的模式,要对其充分描述需要很多特征,以至过于复杂。第章结构模式识别结构模式识别又称句法模式识别,它采用一些比较简单的子模式组成多级结构来描述一个复杂模式,先将模式分为子模式,子模式又分为更简单的子模式,依次分解,直
2、至在某个研究水平上不再需要细分。最后一级最简单的子模式称为模式基元,识别模式基元比识别原模式要简单得多。结构模式识别主要突出模式的结构信息,常用于以结构特征为主的目标识别中,例如指纹、染色体和汉字识别等。图7-1所示是一个模式多级分解的例子。第章结构模式识别图7-1 模式分解示意图第章结构模式识别结构模式识别法将观察对象表达为一个由基元组成的句子,将模式类表达为由有限或无限个具有相似结构特性的模式组成的集合。基元构成模式所遵循的规则即为文法,或称句法。与统计模式识别类似,用已知类别的训练样本进行学习,产生该类或至少是这些样本的文法,这个学习和训练过程称为文法推断。第章结构模式识别结构模式识别的
3、系统框图如图7-2所示,包括预处理、模式表达、句法分析和文法推断四个部分。其中,模式表达包括两部分:模式分割和基元及关系的识别。对于一个模式,经过预处理并对模式分解提取基元后,得到表征模式的句子,然后进行句法分析,判断它是否能被代表某个模式类的文法所接受,最终给出识别结果和模式的结构描述。第章结构模式识别图 7-2结构模式识别系统框图第章结构模式识别7.2形式语言与自动机形式语言与自动机形式语言的渊源可以追溯到20世纪50年代中期,乔姆斯基(Chomsky)等在研究自然语言的过程中发展了文法的数学模型。他将语言形式地定义为由一个字母表中的字母组成的串的集合,在字母表上按照一定的规则定义一个文法
4、,该文法产生的所有句子组成的集合就是该文法产生的语言。若一个句子能由某种语言对应的文法产生,则判断这个句子属于该语言。第章结构模式识别克林(Kleene)在研究神经细胞时提出了自动机,用它来识别语言。按照一定规则构造任意一个自动机,该自动机所能识别的所有句子组成的集合就是一个语言,即一个自动机定义了一个语言。文法和自动机是表示语言的两种不同方法。1959年,乔姆斯基通过深入研究,证明文法和自动机具有等价性。第章结构模式识别7.2.1短语结构文法短语结构文法1.字母表和字符串字母表和字符串字符的有限集合称为字母表,记为V。由字母表V中的字符构成的有限序列称为字母表V上的字符串(链)。例如字母表V
5、=a,b,c,z,0,1,9,即表由26个英文字母和10个阿拉伯数字构成,则字符串可以是a,b,012,ce78等。一个字符串所包含字符的个数称为该字符串的长度,字符串x的长度记为|x|。允许有不含任何符号的空串,记为,空串的长度为零。第章结构模式识别假设X和Y都是字母表V上的字符串,则XY称为字符串X和Y的连接。字母表上的任意一个字符串W与空串的连接还是W,即W=W=W。V+是字母表V上所有字符串构成的集合,V*是字母表V上所有字符串和空串构成的集合,有V*=V+。第章结构模式识别2.短语结构文法短语结构文法定义7.1短语结构文法是一个四元组:G=(VN,VT,P,S)其中:VN为非终止符集
6、,通常用大写字母表示;VT为终止符集,通常用小写字母表示,VNVT=V,且VNVT=,即VN与VT不相交;P是形如的产生式有限集,且V+,V*,符号“”的含义是“能够再写为”;SVN为起始符。第章结构模式识别如果A是P中的产生式,和是V*中的字符串,则有 GA 称是A的直接推导。设,0,1,n,都是V*中的字符串,且有=0,=n,其中i直接推出i+1(0in1),则称序列是长度为n的直接推导序列,可记为n10G即*G包含了G和。第章结构模式识别有一文法G=(VN,VT,P,S),若，且是终止符和非*GS终止符组成的字符串,则是文法G的句型;若V*T,则是文法G的句子,即句子是由终止符组成的符号
7、串。定义定义7.2文法G=(VN,VT,P,S)产生的语言L(G)是由S开始根据G推出的所有终止符串组成的集合,|)(*xSVxxGLGT第章结构模式识别【例例 7.1】给定文法G=(VN,VT,P,S),其中:,ASVNaVT,aSAaASaSP，由文法产生的语言L(G)如下:,()Sa aL G,()SaAaaSaaa aaaL G,()SaAaaSaaaAaaaaSaaaaa aaaaaL G第章结构模式识别以此类推,该文法生成的语言的一般形式是0|)(12naGLn3.文法的分类文法的分类乔姆斯基(Chomsky)分类体系将短语结构文法分为四种类型,即0型、1型、2型和3型文法。1)0
8、型文法0型文法是对P中产生式的形式不加任何限制的文法,又称为无约束文法。由此可知,任何一个文法必然是0型文法。只有0型文法才允许有产生空句的产生式。第章结构模式识别2)1型文法1型文法也称上下文有关文法,它对每一产生式的形式限制为1A212,其中1、2V*,AVN,V+。文法的含义是在1和2之间的非终止符A可被重写为,1和2被视为A的上下文。第章结构模式识别理论上讲,每步推导时,可以对句型中的任何一个非终止符进行表达式替换。在形式语言理论中,为了简单,常采取每次对最左边的或最右边的非终止符进行表达式替换,即采用最左推导或最右推导。最左推导即每次对最左边的非终止符进行推导,最右推导即每次对最右边
9、的非终止符进行推导。不论是采用最左推导还是最右推导,其目的均在于简化推导过程。1型文法的一种等价定义是:产生式集P的形式为,、V+,且|。第章结构模式识别【例例 7.2】给定文法),(SPVVGTN，,BASVN，,baVT：PaSABS 改写为aSABS aABS 改写为aSABSabaA 改写为abaA bbbA改写为bbbA 第章结构模式识别该文法为上下文有关文法。虽然表面上看上下文不完整,但根据1、2V*,可以有1=2=,经过改写就可以明显看出给定文法是上下文有关的。或者根据1型文法的另一种定义,本例中每个产生式左部字符串长度小于或等于右部字符串长度,表明给定文法是上下文有关的。第章结
10、构模式识别3)2型文法型文法2型文法也称上下文无关文法,它要求每一产生式的形式为A,其中AVN,V+。产生式的左端是单个非终止符A,可被重写为右端的字符串,而与A的上下文无关。4)3型文法3型文法也称正则文法,或称正规文法、有穷文法、有限状态文法。对每一产生式的形式限制为AaB或Ab,其中A、BVN,a、bVT。第章结构模式识别由定义可以看出,从0型文法到3型文法,对产生式的限制越来越严格,四种文法的类别包含关系是:3型 2型 1型0型。对应四类文法,产生的语言也分为四类。0型文法产生的语言称为无限制性语言,1型文法产生的语言称为上下文有关语言,2型文法产生的语言称为上下文无关语言,3型文法产
11、生的语言称为正则语言。第章结构模式识别每一种类型的语言对应一种识别器,即每个语言的句子都能被某种识别器所接受。句法识别器可以被视为一个离散控制系统,一个离散控制系统可以模型化为一个自动机。短语结构文法和自动机之间的对应关系如下:文法类型 自动机类型 0型文法 图灵机 1型文法 线性有界自动机 2型文法 下推自动机 3型文法 有限自动机第章结构模式识别7.2.2正则文法和有限自动机正则文法和有限自动机定义定义7.3一个确定的有限状态自动机Af是一个五元组:),(0FqQAf其中:Q为有限状态集;是有限输入字母表;是QQ的映射;q0为起始状态;为终止状态集。QF 第章结构模式识别图7-3给出了有限
12、状态自动机的一般表示。有限状态自动机由一个带有读头的有限控制器和一条写有字符的输入带组成。有限控制器包含有限个状态,读头从左到右依次从输入带上读入字符,每当读头从输入带上读入一个字符时,控制器的状态发生改变,即出现状态转换。第章结构模式识别图 7-3有限状态自动机 第章结构模式识别假设映射(q,a)=q,其中,q、qQ,a,表示的意思是有限状态自动机当前处于状态q,读头从输入带上读入字符a,自动机的状态转换为q,读头从左到右移动一个方格。可以用状态转移图方便地描述映射,相应于映射(q,a)=q的状态转移图如图7-4所示。每个状态标以一个节点,终止状态集F中的状态用双圈标示,状态集Q中F以外的节
13、点用单圆圈表示。第章结构模式识别图 7-4(q,a)=q的状态转移图第章结构模式识别对确定的有限状态自动机而言,由当前状态及读入字符决定的下一步状态是确定的。确定的有限状态自动机Af接受的全部字符串的集合为),(,|)(0FxqxxALf上式表明,若一个串x被自动机接受,要求自动机Af从起始态q0出发,经输入串x后,状态最后转换到终止态上。第章结构模式识别【例例 7.3】设确定的有限状态自动机Af=(Q,q0,F),其中:,210qqqQ,ba，0qF:10),(qaq，21),(qaq，12),(qaq20),(qbq，01),(qbq02),(qbq自动机的状态转移图如图7-5所示。第章结
14、构模式识别图 7-5例7.3的有限状态自动机的状态转移图第章结构模式识别自动机Af从起始态q0出发,输入串x=aabbab,在逐个读入x的各字符时,自动机的状态变化过程为0120210qqqqqqqbabbaa整个输入串读完后,自动机处于状态q0F,所以输入串x被自动机接受。定义定义7.4一个非确定的有限状态自动机Af是一个五元组:),(0FqQAf第章结构模式识别与确定的有限状态自动机相比,只是映射规则不同,是Q2Q的映射。对非确定的有限状态自动机而言,在当前状态及输入符号确定的情况下,下一步的状态不唯一,即(q,a)是一个状态集合(可能为空)。例如(q,a)=q1,q2,ql,它的解释是:
15、非确定的有限状态自动机处于状态q,读头从输入带上读入字符a,选择q1,q2,ql中的任意一个作为下一步状态,并将读头向右移动一格。第章结构模式识别非确定的有限状态自动机Af接受的语言也定义为输入串后能停留在终止态上的所有串的集合:),(,|)(0FpxqpxxALf定理定理7.1设L是一个非确定的有限状态自动机),(0FqQAf所接受的语言,则有一个能接受L的确定的有限状态自动机),(0FqQAf第章结构模式识别fA的状态是Af的状态的所有子集,即，QQ200qq，是中包含F的一个状态的所有状态集合。映射为FQ1212(,),ijq qqap pp当且仅当 121(,),ikjkq appp第
16、章结构模式识别由于确定的有限状态自动机和非确定的有限状态自动机接受同样的语言,在讨论有限状态自动机时,可以不区分是确定的有限状态自动机还是非确定的有限状态自动机。定理定理7.2设G=(VN,VT,P,S)是一个正则文法,则存在一个有限状态自动机Af=(Q,q0,F),满足L(Af)=L(G),其中:(1)=VT,Q=VNT,T为一附加的非终止符,q0=S;(2)如果P包含产生式S,则F=S,T,否则F=T;(3)如果P包含产生式Ba,BVN,aVT,则T(B,a);(4)如果P包含产生式BaC,B、CVN,aVT,则C(B,a)。第章结构模式识别定理定理7.3给定一个有限状态自动机Af=(Q,
17、q0,F),则存在一个正则文法G=(VN,VT,P,S),满足L(G)=L(Af),其中:(1)VN=Q,VT=,S=q0;(2)如果(B,a)=C,且B、CQ,a,则P包含产生式BaC;(3)如果(B,a)=C,且CF,则P包含产生式Ba。定义定义7.5两个有限状态自动机Af、，若有 fA)()(ffALAL则称Af和 等价。fA第章结构模式识别7.2.3 上下文无关文法和下推自动机上下文无关文法和下推自动机1.乔姆斯基乔姆斯基(Chomsky)范式范式定义定义7.6上下文无关文法G=(VN,VT,P,S),若P中的产生式形式都是ABC或Aa,A、B、CVN,aVT,则G是Chomsky范式
18、文法,或称G为Chomsky标准型。定理定理7.4若G为上下文无关文法,且,则有Chomsky范式文法,满足L()=L(G)。对给定的上下文无关文法G,求出一个Chomsky范式文法使,称为把G化为Chomsky标准型。),(SPVVGTN)()(GLGLGG)(GL第章结构模式识别2.格雷巴赫格雷巴赫(Greibach)范式范式定义定义7.7上下文无关文法G=(VN,VT,P,S),若P中的产生式形式都是A且不含产生式,AVN,VT,V*N,则G是Greibach范式文法,或称G为Greibach标准型。定理定理7.5若G为上下文无关文法,且,则有Greibach范式文法,满足L()=L(G
19、)。对给定的上下文无关文法G,求出一个Greibach范式文法,使,称为把G化为Greibach标准型。GG)(GL),(SPVVGTN)()(GLGL第章结构模式识别3.下推自动机下推自动机若文法G中至少存在一对形式推导:ASG*和AAG*其中，,，则文法称NVA*V、V、为自嵌套或自嵌入的,非终止符A也称为自嵌套的。第章结构模式识别若上下文无关文法G的导出包括，和uAySG*vAxAG*,其中 ，则有推导序列 wAG*TVyxwvu,0,*iywxuvyAxuvuvvAxxyuvAxyuAySiiGiiGGGGG第章结构模式识别即语言L(G)是可数无穷集uviwxiy|i0。尽管有限状态自
20、动机能够识别正则语言,但不能识别这个集合。这是因为子串vi的出现必须严格地平衡子串xi的出现,而且在L(G)中存在着含有大量v和x的句子,其中,v和x的数量大大超过任何具有有限确定存储量的自动机所能容许的数量。第章结构模式识别下推自动机有一个辅助存储器,能够处理在导出中使用了自嵌套的句子。下推自动机的辅助存储器是一个容量可以任意大的堆栈,又称为下推存储器。在堆栈中,最新存入的符号把所有先前存入的符号向下推,将自己置于堆栈顶部。下推自动机的一般表示如图7-6所示。第章结构模式识别图 7-6下推自动机 第章结构模式识别定义定义7.8 一个下推自动机是一个七元组：),(00FZqQAP其中:Q为有限
21、状态集;是有限输入字母表;是有限下推字符表;q0为起始状态;为终止状态集;Z0是下推存储器顶端的初始字符;是Q()Q*映射的有限子集。QF 第章结构模式识别对于一个下推自动机,有两种能接受的语言:(1)由终止态接受的语言。定义为L(AP)=x|x+,从状态q0和栈顶Z0开始,读完字符串x,AP停在F的一个状态上(2)由存储器变空方式接受的语言。定义为L(AP)=x|x+,从状态q0和栈顶Z0开始,读完字符串x,AP的堆栈变为空第章结构模式识别【例例 7.4】下推自动机AP=(Q,q0,Z0,F),其中,Q=q0,q1,q2,=0,1,=Z,A,B,Z0=Z,F=q0,为),(),0,(10AB
22、qZq),(),0,(11AAqAq),(),1,(21qAq),(),1,(22qAq),(),0,(02qBq第章结构模式识别则字符串x=00110可被下推自动机以存储器变空方式所接受,因为),(),(),(),(),(),(00212110100qBqABqAABqABqZqx：定理定理7.6对于某个下推自动机M1,L是必然存在另一个下推自动机M2,且有L=L(M2)。由该定理可知,若L是M1以空堆栈方式接受的语言,必有另一下推自动机能以终止态方式接受它,反之亦然。)(1ML第章结构模式识别定理定理7.7设L(G)是文法G=(VN,VT,P,S)以Greibach标准型产生的上下文无关语
23、言,则存在一个下推自动机AP=(Q,q0,Z0,F),使得 ，其中:(1)=VT,Q=q0,=VN,Z0=S,;(2)如果P包含产生式A,AVN,VT,V*N,则中有(q0,a,A)=(q0,)。F )()(GLALP第章结构模式识别在此定理中,将状态集合设置为只含一个元素的集合,简化了状态的表达,换句话说,可以不考虑状态所反映的信息,只需关注下推存储器所包含的信息即可。定理定理7.8设L(AP)是下推自动机AP=(Q,q0,Z0,F)所接受的语言,则存在上下文无关文法G=(VN,VT,P,S),使得L(G)=L(AP)。第章结构模式识别7.3高维文法和随机文法高维文法和随机文法上一节研究的文
24、法只适用于描述基元间的左右连接关系,一般用于描述一维的模式。但模式识别中的许多问题不仅仅是一维的,还有二维的、三维的,甚至更高的维数。对于较复杂的模式,就需要研究高维文法。高维文法有很多种,在此只介绍树文法和网文法。7.3.1树文法和识别器树文法和识别器树文法是高维文法中应用最广泛的一种。树文法的根本特点是,树中的节点可以拥有多个直接后代节点,描述多重连接关系。第章结构模式识别1.树文法树文法树T是一个或一个以上节点的有限集,它具有如下性质:(1)具有一个唯一的指定为根的节点;(2)其余节点分到m个不相交的集合T1,T2,Tm,其中每一个集合本身都是一个完整的树,被称为T的子树。在树T中,一个
25、节点的直接子节点的数目定义为该节点的秩。假定某个节点a有秩r1,r2,rn,该节点的秩的集合记作r(a)=r1,r2,rn。第章结构模式识别定义定义7.9树文法是一个四元组:),(SPrVGT其中:V=VNVT是由非终止符和终止符构成的有限集合;,Z+表示非负整数,即r=(a,r(a)|aV,规定了V中元素的秩;P是形如TiTj的产生式有限集,Ti和Tj都是树;STV是起始树有限集,TV是V中元素作为节点标记的子树集合。2ZrV第章结构模式识别定义定义7.10L(GT)为GT生成的语言:,|)(*STTTTTTGLiGiTTT其中,TT为用终止符集VT中元素作节点标记的树的集合。如果树文法的所
26、有产生式都具有形式:第章结构模式识别则称为扩展的树文法。其中,X,X1,X2,XkVN,xVT,kr(x)。【例例 7.5】用树文法描述如图7-7所示的L-C网络。生成该电路的树文法为GT=(V,r,P,S)其中:VN=S,AVT=$,Uin,L,C,W第章结构模式识别各终止符的秩:r($)=2,r(Uin)=1,r(L)=2,1,r(C)=1,r(W)=0。第章结构模式识别图 7-7L-C网络电路图及相应树(a)L-C网络电路图;(b)树第章结构模式识别2.树自动机树自动机有限自动机和下推自动机都是从左到右逐个字符扫描输入串,而与树文法对应的树自动机则是从输入树的每个叶节点同时开始并行地扫描
27、到树根。若树句子被树自动机接受了,则判决该树属于给定的模式类,反之,则该树不属于该模式类。第章结构模式识别定义定义7.11在上的一个由叶到根的树自动机为)|,(afFQAaT其中:即VT是输入符号有限集;Q为有限状态集;FQ为终止态有限集;fa是QnQ的一个关系,n是a的秩,Qn是Q的n次笛卡儿积。第章结构模式识别给定一个扩展的树文法为GT=(V,r,P,S),可以构造一个能识别语言L(GT)的树自动机AT,其中,Q=VN,F=S,对中每个符号a定义一个关系fa,若P中有产生式Xa,则;若P中有产生式(,)afX则fa=(X1,Xn,X)。第章结构模式识别【例例 7.6】设有扩展树文法GT=(
28、V,r,P,S),其中,V=VNVT,VN=S,A,VT=x,y,z,$,产生式P为能识别该文法生成的树的自动机AT=(S,A,S,fx,fy,fz,f$),其中四个关系对应产生式P中的四个产生式,即第章结构模式识别关系fx的解释是将标记为x且无后代的节点(叶节点)指定为状态A,关系fy表示是将标记为y且无后代的节点指定为状态A,关系fz表示是将标记为z且有一个后代A的节点指定为状态A,关系f$表示是将标记为$且有两个后代A的节点指定为状态S。第章结构模式识别设输入树如图7-8(a)所示。首先使用关系fx和fy给叶节点x和y指定初始状态,如图7-8(b)所示,把状态A给这两个叶节点;第二步,节
29、点z只有一个后代节点且状态为A,根据关系fz给节点z指定状态A,如图7-8(c)所示;最后,根$的两个后代节点均已被指定状态A,根据关系f$把状态S给根节点$,如图7-8(d)所示。因为状态SF,所以输入树被树自动机接受。第章结构模式识别图 7-8树自动机工作示意图(a)输入树;(b)给叶节点指定状态;(c)给根的后代指定状态;(d)给根节点指定状态第章结构模式识别7.3.2网文法网文法网文法是一种二维文法,又称网状文法。网文法生成的句子是以终止符为节点标记的有向图。定义定义7.12一个网文法是一个四元组:),(SPVVGTNW第章结构模式识别其中:VN为非终止符集;VT为终止符集;S为起始网
30、集;P为网状产生式集。一个网状产生式的形式为,E,其中,和是子网,E是的一个嵌套规则,规定把子网嵌入到网W中用以代替子网的逻辑关系,具体说就是E规定了怎样使的节点和原与连接的每个节点相连。对于起始主网,是一个单点,不受任何限制。第章结构模式识别【例例 7.7】网文法GW=(VN,VT,P,S),其中,VN=A,VT=a,b,c,S=A,P如图7-9(a)所示,E表示能被重写为,并且把中的节点a和A标记为b和c的邻点连接起来。这个网文法所产生的语言是如图7-9(b)所示的所有网的集合。网文法主要应用于图形中,在使用时往往对产生式加一些限制以简化应用,如取VT为单终止符集合,此时的网文法称为图文法
31、。第章结构模式识别图 7-9例7.7网文法的产生式和生成的句子(a)产生式;(b)生成的句子第章结构模式识别7.3.3随机文法和识别器随机文法和识别器在实际的模式识别问题中,被研究的过程往往存在某种程度的不确定性。受不确定因素的影响,一个模式可能由多个文法产生。为解决这类问题,把概率引入结构模式识别,提出了随机文法和随机语言,给每个句子的出现加上概率分布。1.随机文法与随机语言随机文法与随机语言定义定义7.13一个随机文法是一个四元组GS=(VN,VT,PS,S)。其中：VN为非终止符集；VT为终止符集;SVN为起始符;PS为随机产生式的有限集合。随机产生式的形式如下:第章结构模式识别kinj
32、iijPiij,2,1;,2,1,式中:iV*,其中至少有一个非终止符;ijV*;Pij是应用这个随机产生式的概率,对于每个产生式而言,要求与使用这个产生式相联系的Pij满足:10ijP，11inijjP第章结构模式识别由于随机文法的产生式都具有相应的概率,对于从S出发导出终止符串x的过程而言,存在一个相关联的概率。对于x,不仅需考虑它和语言集合之间的从属关系,而且还得确定有几个推导序列能够得到x,以及每个推导序列的相应概率,则随机文法生成x的概率就是每个推导序列的概率之和。设导出x的第j条推导序列为第章结构模式识别12|13|1,2|1,2,112jjjjmmPPPPmSx则该推导相应的推导
33、概率为 12|13|1,2|1,2,1.jjjjjmmPP PPP可以简单表示为xSjP第章结构模式识别定义定义7.14一个随机文法生成的随机语言是),(SPVVGSTNS)(,2,1,)(,()(1*kjjPTSPxPkjxSVxxPxGLj式中,k为从S出发导出x的路径数目。当k1时,文法是歧义的;当k=1时,文法是非歧义的。第章结构模式识别定义定义7.15对于任意的随机文法GS,相应的特征文法是由GS中除去与每个随机产生式相关的概率而得到的文法。如果一个随机文法的特征文法是0型、1型、2型或3型文法,则该随机文法相应的是0型、1型、2型或3型的随机文法。SG第章结构模式识别2.随机识别器
34、随机识别器对于确定文法而言,给定一个句子,可以通过自动机判断它是否属于给定的语言集合。随机文法生成的语言也会有等价的以随机方式工作的识别器。识别随机正则文法的识别器是随机有限自动机,与随机上下文无关文法对应的是随机下推自动机。第章结构模式识别定义定义7.16一个随机有限自动机是一个六元组:),(0DFqQAS其中:Q为状态有限集;为输入符号有限集;q0为起始状态;为终止态有限集;是Q2Q的映射;D为赋予这个映射的一组概率值。QF 第章结构模式识别假定当前状态为q,输入符为a,下一映射状态集为q1,q2,qn,即(q,a)=q1,q2,qn。令P(qi|a,q)表示由这个集合中选择状态qi的概率
35、,如果(,)(|,)1iiqq aP qa q对Q中(q,a)的所有组合都成立,则称AS是真正的。第章结构模式识别在识别过程中,AS从q0出发,在扫描完x后,经由nx条可能路径停在F中的一个状态上,若Pi(x)是某一条路径的概率,则自动机识别x的概率是xniixPxP1)()(AS接受的语言是 )()(,|)(,()(1*xniiSxPxPxxPxAL第章结构模式识别定理定理7.9给定一个随机正则文法GS,可以构造一个随机有限自动机AS,使得L(AS)=L(GS)。构造随机有限自动机AS时,=VT,Q=VNTR,q0=S,F=T。其中:T为一附加的终止状态;R为一附加的拒绝状态,利用附加的拒绝
36、状态使概率归一化以保证AS是一个真正的随机自动机。,D根据PS定义如下:第章结构模式识别(1)若，则 PijSxaxP(,),(|,)jijiqq aP qa qP(2)若，则 PiSxaP (,),(|,)iiTq aP T a qP(3)R是陷阱态,，a(,),(|,)1R aR P R a R第章结构模式识别(4)为使AS为真,对于状态q和终止符a的每一组合,将R放在(q,a)中,定义 111(|,)1(|,),niniP R a qP qa qqT 定理定理7.10给定一个随机有限自动机AS=(Q,q0,F,D),可以产生一个随机正则文法GS=(VN,VT,PS,S),使得L(GS)=
37、L(AS)。第章结构模式识别7.4 句句 法法 分分 析析对于任意模式,经过预处理并对模式分解提取基元后,可得到表征模式的句子或串,然后进行判断,若该串能被某种文法所接受,则属于该文法所生成的语言。识别方法可分为两种:一种是采用自动机作为识别器;另一种是通过句法分析进行识别。第章结构模式识别前两节介绍的自动机识别器,本质上就是对输入串进行从左到右的分析,以判断该输入串是否被自动机所识别,若能被接受,则输入串属于自动机对应某类文法生成的语言。自动机识别模式样本的过程,实际上是对模式进行句法分析的过程,其特点是比较简单,计算量比较小,但对模式结构的剖析不够。利用句法分析可根据文法判断待识别模式属于
38、某一类,同时通过对模式结构的深入剖析,可反过来改进相应的文法。第章结构模式识别7.4.1穷举法穷举法穷举算法有两种基本方式:自上而下的分析方法和自下而上的分析方法。1.自上而下的分析方法自上而下的分析方法对于给定的串xV+T,应该给定文法G,由起始符S开始,使用产生式逐步导出给定的串。在导出过程中,句型的字符数目不断增加,若还没有达到给定串的长度|x|,句型中就不存在非终止符了,或者在导出过程中,句型中还存在非终止符,其长度达到或超过|x|,则给定串不被接受。第章结构模式识别【例例 7.8】给定文法G=(S,A,a,b,P,S),产生式P为SAb,SASb,Aa。用自上而下的方法分析串x=aa
39、bb。解解利用产生式集,从S开始,有下列三个导出序列:(1)abAbS (2)(3)aASbbaSbASbSaabbaAbbaSbASbS第章结构模式识别导出序列(1)在还没有达到被分析串x的长度前就终止了,导出序列(2)在没有终止前就超过了串x的长度,导出序列(3)是串x的正确导出路径,采用的是最左推导。为了方便,可约定在同一种分析算法中,都使用最左推导,或者都使用最右推导。一般地,自上而下的分析方法用最左推导,自下而上的分析方法用最右推导。但不论是哪一种方法,均有很强的试探性。试探时产生式的选择和运算的次序是决定分析速度的重要因素。一般而言,分析算法的效率较低。在实际应用中,上例中的三个导
40、出序列可以并行处理,以节省算法时间。第章结构模式识别2.自下而上的分析方法自下而上的分析方法给定串xV+T和文法G,从串x开始,反向使用产生式,导出可能形成串x的属于(VNVT)+的串,在反推过程中,不断用非终止符代替子串,直到反推到起始符S,并得到相应的串列。一般情况下,反推的路径不是唯一的,对给定的串,使用同一文法,可能会存在多个串列。第章结构模式识别【例例 7.9】给定文法G=(S,A,a,b,P,S),产生式P为SAb,SASb,Aa。用自下而上的方法分析串x=aabb。解解反向使用产生式集,从串x=aabb开始,反推到起始符S:(1)对aabb,反向使用产生式Aa,变成Aabb;(2
41、)对Aabb,反向使用产生式Aa,变成AAbb;(3)对AAbb,反向使用产生式SAb,变成ASb;(4)对ASb,反向使用产生式SASb,变成S。第章结构模式识别即得到一个串列aabb,Aabb,AAbb,ASb,S。如果选用不同的反推路径,可以得到另外两个串列,分别是aabb,aAbb,aSb,ASb,S 和aabb,aAbb,AAbb,ASb,S。在实际应用中,为避免同时研究所有的序列,可任意选择一个句柄进行化简,产生一个单一串列,同时准备好反向跟踪判决点,当简化停顿时,试验其他的可能性。第章结构模式识别7.4.2Cocke-Younger-Kasami算法算法无论是自上而下的分析方法还
42、是自下而上的分析方法,效率都很低,随着串长|x|的增加,所需时间按指数增加。而用CYK(Cocke-Younger-Kasami)算法进行分析时,时间随串长|x|的增加,正比于|x|3。CYK算法要求文法G=(VN,VT,P,S)是上下文无关文法,且是Chomsky标准型,即P中的产生式形式是ABC或Aa,A、B、CVN,aVT。第章结构模式识别CYK算法是一种自下而上的分析算法,它的关键是对串长|x|=n的待分析句子构造一个(n+1)(n+1)的识别矩阵。矩阵的构造方法是:方阵主对角线以下的元素全设为0,主对角线上的元素由待分析字符串的各字符构成,主对角线以上的元素由文法G的非终止符构成。假
43、定待分析字符串为x=a1a2an,具体步骤如下:第章结构模式识别(1)构造主对角线。左上角元素t00=0,从t11开始到tnn依次为字符串x的各字符a1到an。(2)构造主对角线以上紧靠主对角线的元素,即ti,i+1(i=0,1,n1)。从字符串x的第一个字符a1开始,从左到右分析每个字符,如果产生式集中有一个产生式Aai,则令ti1,i=A。这表示,对于主对角线上的每一个终止符ai,将所有可能导出它的非终止符写在它上方的空格中。第章结构模式识别(3)按平行于主对角线的方向,逐层往上填写矩阵的各元素,即对每个d=2,3,n,赋给tij(i=0,1,nd;j=i+d)字符。其中：i是矩阵元素的行
44、标号;j是矩阵元素的列标号;d为元素离主对角线的层数。给元素tij赋值时,考虑第i行下面及第j列左边的元素对:第章结构模式识别,11,22,11,jjjijiiijiiitttttt如果文法的产生式集中有ABC,其右边第一个非终止符B与上面某个元素对的第一个元素相同,第二个非终止符C与同一元素对的第二个元素相同,则将产生式左端的非终止符A赋给tij。tij中的非终止符有可能超过一个,也有可能为空。待分析字符串x=a1a2an是否由文法产生的充要条件是:起始符S是元素t0n中的一个符号。第章结构模式识别【例例 7.10】给定上下文无关文法G=(VN,VT,P,S),其中,VN=S,A,B,C,V
45、T=a,b,P为SAB,SAC,Aa,Bb,CSB。这个文法是Chomsky标准型,设输入串为x=aabb,用CYK算法分析是否为给定文法产生的句子。解解输入串长度|x|=4,构造一个55的识别矩阵,接下来具体步骤如下：(1)构造主对角线。将主对角线上的元素t11、t22、t33、t44分别设置为a、a、b、b。(2)构造主对角线以上紧靠主对角线的元素。因为有Aa和Bb,所以t01=t12=A,t23=t34=B。第章结构模式识别(3)d=2,计算t02、t13 和t24:对于t02,因为t01=A,t12=A,P中没有非终止符YAA的产生式,所以;对于t13,因为t12=A,t23=B,P中
46、有产生式SAB,所以t13=S;对于t24,因为t23=B,t34=B,P中没有非终止符YBB的产生式,所以。识别矩阵构造完成,如表7-1所示。t0n=t04中含有起始符S,说明文法所产生的语言含有句子x=aabb,即x属于给定文法所代表的那一类模式。02t 24t 第章结构模式识别表表7-1例例7.10的识别矩阵的识别矩阵 ASAASCABBBb第章结构模式识别7.4.3Earley剖析算法剖析算法厄利(Earley)剖析算法是一种自上而下的剖析算法,其特点是沿着所有可能的剖析式同时进行剖析,以提高剖析效率。通常,Earley算法的时间正比于输入串长度的三次方。Earley剖析算法适用于所有
47、的上下文无关文法,不要求转化为Chomsky标准型或Greibach标准型。因此,Earley算法的剖析过程可针对原来的子模式和基元进行,能较好地反映模式的结构关系。第章结构模式识别【例例 7.11】有上下文无关文法G=(VN,VT,P,S),其中,VN=S,T,F,VT=a,+,*,(,),P为SS+T,ST,TT*F,TF,F(S),Fa。设输入串为x=a*a,用Earley算法分析是否为给定文法产生的句子。解解用Earley算法得到对x=a*a的剖析表如下:第章结构模式识别I0:0,TSS0,TS0,FTT0,FT0),(SF0,aF第章结构模式识别I:0,aF,0SST0,TS0,FT
48、T0,FTI2:0,FTT2),(SF2,aF第章结构模式识别I3:2,aF0,FTT0,TS0,FTT0,TSS因为ST,0在I3中,所以x=a*a属于L(G)。第章结构模式识别7.5 文文 法法 推推 断断7.5.1文法推断的概念文法推断的概念文法G产生的语言L(G)是由起始符S开始根据G推出的所有终止符串组成的集合,即,但并非V*T中的所有终止符串都属于L(G)。是包含所有由VT的元素组成但不属于语言L(G)的终止符串的无穷集,称为L(G)的补集。可见,V*T被分为两个子集,即*)(TVGL)()(*GLVGLT*()()TVL GL G第章结构模式识别以S(G)表示的样本定义为集合R+
49、R,有称R+为正样本集,R为负样本集。若G中定义的每个产生式规则至少被用来产生R+的一个元素,则称语言L(G)的正样本集R+是结构完备的。)(,2,1|GLxnixRii)(,2,1|GLxmjxRjj第章结构模式识别以一个样本句子的集合为基础来学习文法的过程称为文法推断。文法推断的实质是推断一个未知文法G的句法规则。推断的依据是文法语言的一个有限样本集S(G),即属于L(G)的一个有限集R+和属于L(G)的补集的一个有限集R,推断出的文法是一组规则,它们既可以描述文法语言中的给定有限集,也可以预测给定集以外的其他句子,这些句子与给定集在某种意义上具有相同性质。第章结构模式识别7.5.2正则文
50、法的推断正则文法的推断1.规范确定文法和导出文法规范确定文法和导出文法通常的文法推断是从现有的R+和R来获得文法G,而最简单的推断是由R+得到仅仅能产生正样本集R+的限定文法。规范确定文法是只能产生给定正样本集中句子的正则文法。假定正样本集R+=x1,x2,xm,推断相应的规范确定文法,具体步骤如下:(1)检查R+中所有的链(字符串),得到所有的终止符,若终止符相同,则只保留其中一个,将这组终止符作为VT。第章结构模式识别(2)根据R+中每个形为xi=ai1ai2ain的链,得出恰好产生链xi的产生式集合:,1,1,1,2,22111inninininiiiiiiaZZaZZaZZaS其中:S
