句法模式识别.ppt

第6章 句法模式识别,6.1 句法模式识别概述 6.2 形式语言的基本概念 6.3 模式的描述方法 6.4 文法推断 6.5 句法分析 6.6 句法结构的自动机识别,第6章 句法模式识别,6.1 句法模式识别概述,模式用句子形式描述，结构信息十分重要模式,子模式,基元,句子,词组,单词,,,,组合关系,自然语言的文法,,句法模式识别用小而简单的基元与语法规则描述和识别 大而复杂的模式，通过对基元的识别，进而识别子模式，最终识别复杂模式符合某个文法的所有句子的集合,一个模式类,,,（b）,（c）,图6.1 景物结构描述 与英文句子句法描述的对比,句法模式识别系统的组成：,句法模式识别的理论基础：形式语言,20世纪50年代中期乔姆斯基（Chomsky） 基元选择尚无通用的方法； * 文法推断理论远不及统计学习发展得成熟句法模式识别存在的主要问题：,6.2 形式语言的基本概念,6.2.1 基本定义,1．字母表,与问题有关的符号的有限集合，用V或∑表示2．句子,由字母表中符号组成的有限长度的符号串，又称链空句 用λ表示组成：英文小写字母、数字例：由 中元素可组成句子：,例：,abc，aacc，…,重写次数,句子的长度：句子包含符号的数目，用|•|表示。

3．语言,由字母表中的符号根据某种文法组成的句子的集合V *：V中符号组成的所有句子的集合，包括空句；,V +：不包含空句的句子集合例：,4．文法,构成一种语言的句子所必须遵守的规则VN ：非终止符的有限集，子模式的集合，大写字母表示VT ：终止符有限集，基元的集合，字母表起始部分的小写 字母表示 终止符和非终止符组成的混合字符串：,用英文字母表尾部的小写字母x，y，v，w等表示终止符组成的字符串：,用希腊字母α，β，γ等表示P：生成式的有限集用文法产生句子时的重写规则字符串,字符串,替换,S：起始符，代表模式本身，特殊的非终止符用生成式构成句子时，必须由左边是S的生成式开始一种语言有一种文法，由文法G构成的语言用L(G)表示：,文法G构成的句子 由终止符组成,VT中字符组成的 所有句子的集合,文法G的 推导关系,,①,②,③,⑤,利用文法构成句子时，除第一个生成式必须利用左边 为起始符 S 的生成式外，其余生成式使用的先后次序及重 复使用的次数都不受限制是,说明：,解：,6.2.2 文法分类,四种类型：0型文法、1型文法、2型文法和3型文法1．0型文法：无约束文法P：,其中， ， 。

2．1型文法：上下文有关文法 含意：,,3．2型文法：上下文无关文法 解：每个生成式的左边都是单变量，右边是非空字符串， 故G是上下文无关文法属于L(G)的句子：,结果不唯一4．3型文法：正则文法、有限态文法是,后一种文法的限制比前一种文法的限制严格； 限制愈多的文法愈容易推断；,句法模式识别中多采用上下文无关文法和正则文法6.3 模式的描述方法,6.3.1 基元的确定,根据结构特征对模式进行描述 —— 结构描述法，又称句法表示法模式的表示：链表示法、树表示法、图表示法对应的文法：链文法（串文法）、树文法、图文法 还有网文法、阵列文法等目前关于基元的确定没有一个通用的解决办法基元的选择遵循两个基本原则1．基元应是模式的基本单元，能够通过一定的结构关系对数 据进行紧凑、方便地描述 2．基元应该容易用现有的非句法方法进行提取或识别例如：语音识别中 —— 音素； 识别手写文字 —— 笔划6.3.2 模式的链表示法,1．链码法,链码：,用不同斜率的直线段或曲线段为基元表示图形模式弗利曼链码：,以八个基本方向的有向线段为基元， 用0~7八个数字符号表示用字符表示基元后，被描述的 图形表示成的字符串。

弗利曼链码基元,数字“2”的折线化和量化结果,编码：,矩形网格覆盖；,折线化和量化；,形成链码(有序结构)例：“2”的链码表示为,2．图形描述语言法,简称PDL（Picture Description Language，PDL）基本基元：有向线段(直线段、弧线段) 由 “头(箭头端)” 和 “尾” 构成关系基元：表示基元之间连接关系的算子头尾 相接,头头 相接,尾尾 相接,头头 且 尾尾相接,头尾 颠倒,（,）,例：用PDL法表示大写英文字母Aa+b),((a+b)*c),(((a+b)*c)+b),(a+(((a+b)*c)+b)),链表示法：只能从左边或右边与其它符号相连，一维连接方式6.3.3 模式的树表示法,高维表示法1．树的定义,树T是一个或一个以上结点的有限集合，并且满足： 1）存在一个唯一的指定为根的结点； 2）其余结点分为m个不相交的集合T1，T2，…，Tm，其中 每一个集合本身都是一个树，称为T的子树同一层上各子树交换位置构成的树不同树的有序性：,一个结点具有子树的个数，结点a的秩记为 r(a) 叶结点的秩为零秩：,长方体,基元,树结构描述,—— 结点a的秩可能是2，l或0。

例：,结点a可能有 2，1或0个分枝,树文法定义为四元式,2．树文法,字母表,以字母表中字母 为根结点的树的秩,,起始树的有限集,生成式的有限集,由树文法Gt产生的语言L(Gt)是一些树的集合即模式集：,所有结点都是终止符 的树的集合,树T由S中的起始树Ti开始， 用文法Gt的生成式逐步导出,图6.7 模式 的树状表示,解：生成式① ② ③中右边的树分别用T1，T2 ，T3表示有,,试判断图6.7所示的树是否属于L(Gt)的一个句子3．扩展树文法,其中，P中生成式 形式：,一个树文法有一个对应的扩展树文法例6.6 构成例6.5中树文法对应的扩展树文法6.4 文法推断,6.4.1 基本概念,文法推断：用已知类别的模式样本集训练类别文法的过程统计模式识别 训练判别函数,句法模式识别 训练类别文法,,目的：构造出能正确描述某类模式的文法，其中主要是求 生成式集合P 选择文法形式（链文法、树文法、图文法） 根据样本进行推断文法基本步骤：,1．语言L(G)的正样本集和负样本集,2．文法推断的基本思路,根据样本集R{R+，R-}推导出文法G，简化时只有R+ 给定一个R+型的训练样本集，共n个句子，陆续送入 一个 “文法推断机”。

* 输入一个句子，由此初步推断出一个能导生出该句子 的文法G1 * 输入第二个句子，补充或修改G1，从而推断出能导生 出这两个句子的文法G2 …… * 推断出文法Gn 将Gn中各条文做合并处理 先推断出几种不同的文法，然后再选择一种简化文法的方法：,6.4.2 余码文法的推断,1．余码的定义,2．余码文法的推断,余码文法又称形式微商文法6.4.3 扩展树文法的推断,第三步：合并等价非终止符，删除被合并的非终止符的所有 后代生成式例6.8 设某类句法模式树描述的样本集中含有树T1和T2：,解：第一步：分别写出产生树T1和T2的生成式产生树T1的生成式：,增加一个，得到产生树T2的生成式：,6.5 句法分析,6.5.1 参考链匹配法,利用文法对未知类别的句法模式进行识别或分类的过程句法分析：,* 对每一类模式给出一组样本链(参考链)设有M类模式 将输入链x与每一类的参考链进行比较，并规定一个比较容 限 x被识别为与其匹配“最好”的参考链所属的模式类6.5.2 填充树图法,用于上下文无关文法的分析若已知某语言的文法Gi，给定某待识别的链x，建立一个以x 为底，以起始符S为顶的三角形，如图6.8所示。

用文法Gi的生成式填充这个三角形，使之成为一个分析树 若填充成功，表示x可以由文法Gi导出，,图6.8 待填充的三角形,填充三角形的方法： 顶下法 底上法,,解：填充三角形成功，,图6.9 用文法G的生成式填充的三角形,6.5.3 CYK分析法,库克(Cocke) -杨格(Younger) -卡塞米(Kasami)分析法,用于上下文无关文法的分析,1．乔姆斯基范式,要求：生成式必须表示为乔姆斯基范式或,其中A，B，C为非终止符，a为终止符例如，,乔姆斯基范式为,2．CYK分析法,输入：乔姆斯基范式的上下文无关文法G、输入链x； 输出：关于链x的分析表 关键：构造x的分析表,方法：,步骤：,第五步：停机，填表结束6.5.4 厄利分析法,一种有效的上下文无关文法的分析算法圆点：分割开经分析后符合的部分和尚未考虑的部分思路：,步骤：,反复执行2和3，到没有新项目加入I0为止反复执行5和6，到没有项目加到Ij中为止解：,6.6 句法结构的自动机识别,自动机：句法模式识别器识别输入链是否符合与该机相对应的文法0型文法,图灵机,1型文法,线性有界自动机,2型文法,下推自动机,3型文法,有限态自动机,,,,,每类文法对应一类自动机：,链文法：,树文法,树自动机。

其他：,1．有限态自动机,6.6.1 有限态自动机与正则文法,输入字母表,内部状态 有限集,状态转换规则,初始状态,终止状态集,自动机每次从一个状态只能转换到另一个指定的状态确定的有限态自动机：,非确定的有限态自动机：,,自动机每次从一个状态可以转换到一个指定状态集中 的任意一状态如：,2．有限态自动机接受语言的方式,有限态自动机接受的语言：,指有限态自动机接受的链x的集合，记为L(A)结构：,* x中的字符从左到右依次记录在输入带上工作方式：,* 只读头从输入带的最左边一个单元开始依次读取输入字符 每读取一个字符，状态控制器搜寻原存入的状态转换规则， 接受/拒绝这个字符 如果自动机连续地接受输入链的每个字符，最后停在一个终 止状态上，则称输入链属于该自动机能接受的那种语言，即,解：将链x输入自动机A，状态转换过程为,状态转换图：,状态,终止态,进入 箭头,状态变化,状态变 化方向,3．有限态自动机与正则文法的对应状态,1）按正则文法构造有限态自动机,A和G的对应关系：,* 由正则文法G构成对应的有限态自动机A；,应用：,若将非终止符Ai，Aj分别命名为qi，qj：,A接受链x的过程为：,2）按有限态自动机确定正则文法,对应关系：,若将qi，qj分别命名为Ai，Aj：,6.6.2 下推自动机与上下文无关文法,1．下推自动机,有限态自动机的限制：,下推自动机(PDA)：有限态自动机+下推存储器,只能接受正则文法产生的语言， 不能接受上下文无关文法产生的语言。

可识别上下文无关文法产生的句子结构：,* 初始状态q0：栈顶为最初的非终止符；,* 只读头读取输入带字符：输入链中的终止符和栈顶的非终止 符共同决定自动机状态的转换；,* 状态转换同时，栈顶内容发生变化 自动机内部状态处于终止态或堆栈变空时，称输入链被自动 机接受（识别）了下推自动机定义：,有限态自动机 加Z0和Γ,下推符号 有限集,最初处于栈顶 的非终止符,内部状态转换和 栈顶内容改变的规则,,规则δ ：,讨论：,* 为单个非终止符 为非终止符串有下推动作， 最左边的符号处于栈顶；,* 为空串栈顶Z被弹出，处于Z下面的非终止符处于栈顶2．下推自动机接受语言的方式,1）终止态方式,2）空堆栈方式,自动机接受的语言为：,,下推自动机接受的语言为：,两种语言等价3．下推自动机与上下文无关文法的对应关系,构成方法：依据,一个上下文无关文法对应一个下推自动机上下文无关文法的乔姆斯基范式,上下文无关文法的格雷巴赫（Greibach）范式,1）格雷巴赫范式生成式,2）由上下文无关文法构成下推自动机,δ为：,结束,。