模式识别原理幻灯片第6章句法模式识别

1、第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

2、，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 文法分类,四种类型

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

4、式。,弗利曼链码：,以八个基本方向的有向线段为基元， 用07八个数字符号表示。,用字符表示基元后，被描述的 图形表示成的字符串。,弗利曼链码基元,数字“2”的折线化和量化结果,编码：,矩形网格覆盖；,折线化和量化；,形成链码(有序结构)。,例：“2”的链码表示为,2图形描述语言法,简称PDL（Picture Description Language，PDL）。,基本基元：有向线段(直线段、弧线段) 。,由 “头(箭头端)” 和 “尾” 构成。,关系基元：表示基元之间连接关系的算子。,头尾 相接,头头 相接,尾尾 相接,头头 且 尾尾相接,头尾 颠倒,（,）,例：用PDL法表示大写英文字母A。,(a+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的子树。,同一层上各子树交换位置

5、构成的树不同。,树的有序性：,一个结点具有子树的个数，结点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。,* 选择文法形式（链文法、树文法、图文法）。,* 根据样本进行

6、推断文法。,基本步骤：,1语言L(G)的正样本集和负样本集,2文法推断的基本思路,根据样本集RR+，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类模式。,

7、* 将输入链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为终止符。,例如，,乔姆斯基范式为,2CYK分析法,输入：乔姆斯基范式的上下文无关文法G、输入链x； 输出：关于链x的分析表。 关键：构造x的分析表,方法：,步骤：,第五步：停机，填表结束。,6.5.4 厄利分析法,一种有效的上下文无关文法的分析算法。,圆点：分割开经分析后符合的部分和尚未考

8、虑的部分。,思路：,步骤：,反复执行2和3，到没有新项目加入I0为止。,反复执行5和6，到没有项目加到Ij中为止。,解：,6.6 句法结构的自动机识别,自动机：句法模式识别器。,识别输入链是否符合与该机相对应的文法。,0型文法,图灵机,1型文法,线性有界自动机,2型文法,下推自动机,3型文法,有限态自动机,每类文法对应一类自动机：,链文法：,树文法,树自动机。,其他：,1有限态自动机,6.6.1 有限态自动机与正则文法,输入字母表,内部状态 有限集,状态转换规则,初始状态,终止状态集,自动机每次从一个状态只能转换到另一个指定的状态。,确定的有限态自动机：,非确定的有限态自动机：,自动机每次从一个状态可以转换到一个指定状态集中 的任意一状态。如：,2有限态自动机接受语言的方式,有限态自动机接受的语言：,指有限态自动机接受的链x的集合，记为L(A)。,结构：,* x中的字符从左到右依次记录在输入带上。,工作方式：,* 只读头从输入带的最左边一个单元开始依次读取输入字符。,* 每读取一个字符，状态控制器搜寻原存入的状态转换规则， 接受/拒绝这个字符。,* 如果自动机连续地接受输入链的每个字符

9、，最后停在一个终 止状态上，则称输入链属于该自动机能接受的那种语言，即,解：将链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）由上下文无关文法构成下推自动机,为：,结束,

《模式识别原理幻灯片第6章句法模式识别》由会员F****n分享，可在线阅读，更多相关《模式识别原理幻灯片第6章句法模式识别》请在金锄头文库上搜索。