模式识别原理11

nullnull第七章  句法模式识别 类聚吸附力模型: 类别间，类别与整体间的结构关系（J）， 句法模式问: 结构间的关系需借助结构信息解决 结构信息重要，如图片，语音。景物的识别十分复杂，要求 特征量非常巨大，要把每一模式分类准确很困难，希望:   识别基元 子模式 复杂模式 （汉字，指纹，连续语音 已获得一定成功） 类比： 文库 句子 句子 字，字符 字 字母 文库，句子，正确与否看是否合文法null执行模式推理，按模式文法看是否得出（识别所要求的模式) 句法PR系统： null一 基本模式描述方法（模式示） 要用小而简单的基元文法规则描述大而复杂的模式的能力 可利用语法递归性；同一语法规则，递归使用多次。 1 树形表示法：类似谱系图，要标明物体对象及关系 。null2 字符串表示法：用字串表示一个物体 形状：复杂，简单 字串：长，短 二 源模式选择 原则： （1）原模式与研究的模式有明确的易于表达的关系 （2）应不难用普通方法来辨认和提取 （3）其结构应是最简单。众所周知的，易于分析的。 null在选择上没有一成不变的方法，选出源模式后，再出相应原模式抽取方法 在字串表示法中 对一个阶梯结构 用基元（源模式） 表示该结构…abab… 一个矩形 表示为aabbcccdd null串表示法适合描述一些物体或实体，物体结构是以该模式相当简单的连接为基础的。 串文法形成的句子为有序长度串（有穷：有穷个元素；可数的无穷串），一维， 左侧或右侧连接子模式或原模式链文法。 应用中，为实现功能更强的方法，要用树表示法。本质上任何一个分层有序的系统都导致树结构。 *树形结构表示法 null仍选 做基元，再利用“ 的一部分”这个关系，可组合成树 null如果给树结点加标记的次序与在串中的次序相同，那么串是只包含单个分叉的树的一个特例。 树文法 汉字识别中 得到一个网，网文法（高维文法） null汉字识别还可用划分四个象素，每个象限端点点数作源模式。 *图形，源模式：曲线段，直线段 曲线段源模式：起点，长度，斜率 直线段源模式：起点，弧长，曲率 染色体 基元 依染色体边界顺时针移动出基元， 基元编码成合格的串形式null三 模式文法 原模式――某种文法承认的符号 文法――能生成由给定符号组成的句子的句法规则集 合，（每类至少有一个文法） （串文法中，其中一个句子＝一个串＝模式（样本），一个文法对应很多个句子） 两个文法 分别产生语言 对应一个类别或一部分 建立文法 句法模式识别过程 输入模式句子－－符合哪类文法①属于 ②属于 ③不符合各类，拒绝类 ④同时符合多个，难判别 null1. 文法定义 字符表：规定模式文法用下列字符表     各层－－非终结符 终结符 关系符 顶层－－起始符S 最下层 节点数 （空串－－不含任何字符的串） 模式语句：V中字符组成的有限长字符串 如 语句 ；长度为 ，字串 中字符数（终结符数）null句子，对终结符集合 长为 记xy为语句x与语句y连接， ；空串 ， 模式语言 集合，记作L 具有某些共性，规则 例 字符表 若 则 N个a链接构成的串 两种语言 ，其链接null句法模式识别基本系统：给出一个规则的有穷集合（文法） 产生且只产生某一特殊语言的串集合 文法定义：四元组 非终结符集 终结符集 产生规则 起始符 产生规则，改写规则 有限个产生式－说明源模式与被研究模式间结构关系 产生式 ，子模式 能够 非终结符 ，null 产生式 ，子模式A由源模式b构成 含意有多种解释，取决于‘+“表示什么 若“＋”表示在…之下，则整个产生式表示a在b之下 2 文法推导 从起始符或非终结符开始，有限次以任意次序重复运用产生式（产生规则），最后导出句子（由终结符组成，不能再分解转换null导出方法：按照导出的每一相邻步骤中，重写哪个非终结符 可分为： 最左导出－－在现有串中仅仅重写最左的那个非终结符 最右导出――每一个中只重写最右的非终结符 作为导出串的方法，不会限制由文法产生的语言，旨在 使导出强制的按一个有秩序的方式进行。 null例： a，b是源模式，若看作RLC网络，则语言L（G）代表一类网络n节低通滤波器 3  文法类型 ① 类型： G中关键是P――决定文法性质 0型文法，产生式形式不受任何限制，则它就是无约束的. 对产生式加上某些限制，文法就分成适当的层次。 null1型：上下文有关文法 (产生式形式 ) 仅当 出现在字串 与 之间时， 才有可能被改写为 上文（前因） 下文（后果） 2型： 上下文无关文法：( , ) 这类型非终结符A可按产生式重写成 ，与A出现在什么样的上下文中无关。 3型： 正则文法: (产生式 ) 0，1型 提供计算理论方面的重要成果 2，3型文法 对实际应用重要 语言归类到能产生这种语言的限制最严格文法 （属于正则文法，就不应分类到上下文无关文法） null②文法多义性（歧义性：同一文法。不同的最左导出 方式，得到同一个句子 ③ 自嵌入式产生式、循环结构     得到的循环结构，A一直在中间，代表一个长（正） 方形可用于改变比例大小 null④产生式标准形式： chmosky范式（上下文无关文法均可化作该范式） 对不合要求的 若 是 null 用一长串表示了 多了一些中间 nullGREIBACH范式 一般式先化成chmosky范式，再化Greibach范式 上例 化作标准范式后，其中一些是无用产生式，可删除 （如何判断，牵涉文法化简问题）