图7-1所示是一个模式多级分解的例子。
第7章 结构模式识别
图7-1 模式分解示意图
第7章 结构模式识别
结构模式识别法将观察对象表达为一个由基元组成的句 子, 将模式类表达为由有限或无限个具有相似结构特性的模 式组成的集合。 基元构成模式所遵循的规则即为文法, 或称 句法。 与统计模式识别类似, 用已知类别的训练样本进行学 习, 产生该类或至少是这些样本的文法, 这个学习和训练过程 称为文法推断。
自动机的状态转移图如图7-5所示。
第7章 结构模式识别
图 7-5 例7.3的有限状态自动机的状态转移图
第7章 结构模式识别
自动机Af从起始态q0出发, 输入串x=aabbab, 在逐个读入x 的各字符时, 自动机的状态变化过程为
q0 a q1 a q2 b q0 b q2 a q1 b q0
整个输入串读完后, 自动机处于状态q0∈F, 所以输入串x 被自动机接受。
定义7.4 一个非确定的有限状态自动机Af是一个五元组:
Af (Q, , , q0 , F )
第7章 结构模式识别
与确定的有限状态自动机相比, 只是映射规则不同, δ是 Q×Σ→2Q的映射。
对非确定的有限状态自动机而言, 在当前状态及输入符号 确定的情况下, 下一步的状态不唯一, 即δ(q, a)是一个状态集合 (可能为空)。 例如δ(q, a)={q1, q2, …, ql},它的解释是: 非确定的 有限状态自动机处于状态q, 读头从输入带上读入字符a, 选择q1, q2, …, ql中的任意一个作为下一步状态, 并将读头向右移动一 格。
第7章 结构模式识别
结构模式识别又称句法模式识别, 它采用一些比较简单 的子模式组成多级结构来描述一个复杂模式, 先将模式分为 子模式, 子模式又分为更简单的子模式, 依次分解, 直至在某 个研究水平上不再需要细分。 最后一级最简单的子模式称 为模式基元, 识别模式基元比识别原模式要简单得多。