- 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
- 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
张素文-第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型文法:无约束文法。 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
文档评论(0)