张素文-第6章句法模式识别讲解.pptVIP

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型文法：无约束文法。 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法表示大写英文字母A。 (a+b) ((a+b)*c) (((a+b)*c