按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
）可能是第一
条产生式，产生式
个给出一个完整的图象文法的人。他构造了一个能够产生任
意等边直角三角形的文法。文法中包括
以图形方式给出。以具有九个方格的方块表示：
第 307 页
中的一个。所描绘的直角三角形以表示直角顶点， 、
和斜边由
和、
组成，另一条边由组成，三角形的内点为字母
可、中的一个，
其他两个顶点分别为组成，一条底边由
在上述产生式中，符号可以是
是中的一个， 可以是以
及空白中的一个。在产生式（ ） 中，
条开始，以
在
不同的位置可以代表不同的字母。在使用产生式时，箭头两
端希腊字母代表同样的符号。这些产生式从第
任何方式进行直至没有规则可用而构成一个等边直角三角形
方块中可以是空白，或者是英文字母
第 308 页
为止。所产生的三角形如图所示，从这些产生式的形式
可以看出来，要求在一定条件下进行代换所以这一文法是上
下文敏感的文法。
接起来用一个向量表示，然后定义种连接运算关系：
把每个图象元素规定头（ ）和尾（ ，并且把头尾连
另外还提出过一种图象描述语言
图
第 309 页
）描述房子。其树状表示如下：
描述英文字母链（ ） ）
于是上述文法产生的链（（ ）
三角形（
房子（ ） ） （ 三角形）
房子， （三角形） ）
以及产生式集
， ，
形＝
，其中＝ 房子，三角
用下面的文法可以产生英文字母和房子
如果以种线段作为基本元素
此外，运算表示把头尾例置
第 310 页
，丛状文法（ ，其中
先后曾经提出过一些图象文法如网状文法（ 与
第 311 页
产生的链表
表示的模
，使得由文法
分析”。除了回答
所示：
树状文法因为能有效地进行句法分析，所以比较广泛的采
用。下面的例子给出用树状表示描绘一个简单的电感电容线
路，如图
个模式类，可以分
四、句法分析 如果构造了一个文法来产生一种语言，
这种语言恰好能描述我们所研究的模式。识别模式就变成识
别语言了。下一步就是设计一个识别程序来识别由文法所产
生的语言，并且要求根据某个特定的文法所设计的识别程序
只能识别这个文法产生的语言。例如有
个文法
类中的模式。那么对于一个未知的、用链
别构造
示第
式，模式识别问题基本上成为这样的问题： 属于个文法
代表的模式属于或不属于
中哪一个文法产生的语言？求解这一问题的过程称为“句法
产生的语言
之外，句法分析的过程还提供这个模式的结构信息。
如果是有限状态文法，那么就可以根据有限状态文法
与有限状态自动机之间的对应关系，设计一个有限状态自动
～
第 312 页
机来产生的语言。如果文法
相一致，那么
是上下文无关文法
一般说来要求设计一个非确定的自动机，我们可以用下述方
式来了解句法分析：给定一个句子
号表示的一条链）以及一个文法
是用字母表中的符
。如果能做到构造一个三
角形，三角形的内部由文法
就属于
产生的树状表示填满，而底边
的符号正好与产生的语言，否则
就不属于产生的语言。举个简单的例子，考虑
产生链的树状表示式如下：
第 313 页
号开始，是否能把终止符用非终止符代替，逐步自下往上，
法称为“自上而下”的句法分析。另一种是从输入链的符
是否能产生与输入链的符号相一致的终止符链。这种作
上即从树形的根向下的方式进行。根据文法规则考虑最终
如何把三角形填满，在则上并不重要，我们可以从顶
第 314 页
最后是否能与起始符相吻合。这种作法称为“自下上”的
句法分析。
扬格一凯萨密算法
进行句法分析不能乱凑，要研究算法用机器来进行分
析。对于上下文无关文法已经提出不少有效的算法，如厄利
算法是一种自下而上的有效算法，凯克
是一种自上而下的有效算法。至于上下文敏感的文法句法非
常繁复，句法分析的算法未得到好的解决。
用一个摄象机或者用一
五、噪声和畸变模式的识别 用机器来识别图象模
式，首先就要通过扫描装置把胶片上或者纸上的图象经个
过光电转换变成数字信号。扫描可
飞点扫描装置，免不了会有噪声使图象发生某种畸变，具
体应用模式识别技术的过程中也不可避免的会遇到一些不确
定的因素，如在通信，存储、信息检索、测量和处理具体模
式时都会遇到噪声和干扰。所以应该把识别程序设计得在有
干扰的情况下也能正确地进行识别。
用语言来描述噪声和畸变模式时就会遇到所谓的“含
混”问题，即几个不同的文法都可产生同一条链，换句话
说可能发生模式类之间有一部分重叠的现象。解决这类问题
的一种自然的办法是把短语结构语言推广到随机短语结构语
言，分别把文法、识别程序中的状态转移加以随机化建立随
机文法以及随机句法分析算法。用随机语言来描述有噪声和
和畸变的模式，就可以用概率信息来解决含混问题。另一种
办法是在句法方法中用统计模式识别中模板匹配的作法，定
义两条链之间的距离度量，用一条链称为标准模式链来描述
模板。由于噪声干扰的影响，标准模式链可能畸变成为另一
条链。考虑可能有种误差①代换误差，链中的一个符号
第 315 页
换除链中的一个符被掉； 插入
插入： 删除： 。
另一符号； 删
误差，在链的两个相连符号之间插入一个新的符号。于是用这
三种误差的数目，或者这三种误差加数后的和来作为两条链
之间的距离度量。这充分体现出句法的结构作用。最初乔姆
斯基在建立语言的生成模型时，由于研究的对象是英语。根
据短语结构语言这一模型来生成英语句子，必须经过一个极
其复杂而又繁琐的过程，为了使生成能力比较强，乔姆斯基
）转换部分；
提出转换生成文法模型。早期的转换生成文法包括三部分：
短语结构部分； 语素音位部分。转换
运算方式主要有五种（ 置换：
。（
（复写）：
代换：
。在句法模式识别中，模式的结构不象英语句子的结构
那样复杂，对于一条标准模式链所可能发生的畸变，只要考
虑上述五种运算中的后三种即可。用代换、删除、插入三种
误差的数目作为距离度量称为列维施坦距离，至于求二条链
之间的列维施坦距离可以用动态规划方法来解决，在此基础
上可以用误差校正句法分析来解决模式类有部分重叠的问
题。这部分内容过于专门这里就不介绍了。
六、词意句法方法 模式识别中的统计方法和句法
方法各有优点和弱点，前者不能描述复杂模式的结构以及
子模式与子模式之间的关系，后者在利用数值信息方面又往
往无为力。如何把两者有机地结合起来就是一个值得研究
的课题。这个新方向中主要就是利用词意信息。这一点与认知
心理方面的实验结果相吻合，人的视觉信息如何存储到长时
记忆中去是心理学上比较困难而又谜惑不解的问题，例如一
个方形存在我们的记忆中，也许在我们脑中实际有的不是那
～
第 316 页
是产
中
？ ？
其中每个是终止符和非终止符组成的
链。对于每个定义它的属性
的属性用表示，那么与中的每个产生式
就有相应的词意关系式
） ， 这个关系组成词意部分， 此外词意部分还
个方形的形状，而是一些节点和链（实际上也可能不是这
样，只是想象而已）。同样，如果一个东西的意义存储在脑
话彼此之间的关系
中，肯定说，它不是几个字或一句话存进去，可能是一句
又如中文， 存在我们脑中的不
是一个个的汉字，而是与这些汉字有关的意义。总之除了构
成句子的句法这个重要的因素外，对于记忆与认识说来句子
所包含的意义可以说也是非常重要的。在模式识别方面句法
方法有其局限性，需要加入词意。最近几年来的研究取得了
进展，在一般短语结构文法的基础上加入词意信息扩大为属
一词意、句法方法〔
性文法。用属性文法把句法方法和统计方法统一起来取长补
短成为一种新的方法〕。现在的研
究结果已经为建立词意、句法模式识别迈出了一大步。
性文法（
是非终止符有限集，
是一般文法�