第十讲 句法模式识别一、 基本概念1、结构模式识别：有一些模式识别任务，不能在特征空间中用统计模式识别的方法得到解决。

汉字的识别：汉字有偏旁部首、笔划构成 字符的识别：字符的字体不影响识别 语言的识别：语言由音节、字、词构成 图像识别：画面分割，目标识别生物识别：基因序列，染色体结构，心电图分类 定义：以结构基元为基础，利用模式的结构信息完成分类的过程，称为“结构模式识别”。

其中“基元”指构成模式结构信息的基本单元，本身不包含有意义的结构信息。

基元的选取与应用有关：文字：笔划或偏旁部首作为基元 语音：音素作为基元心电图：收缩波和扩张波作为基元 图形：边缘线段、角点都可作为基元讨论：结构模式识别是与统计模式识别完全不同的一大类模式识别问题，一个基于结构信息，一个基于特征值结构模式识别不仅能完成分类，还可以得到每个模式的结构性质结构模式识别的依据是模式间结构上的“相似性”，这种相似度的度量不能用一般特征空间中的距离来表示结构模式识别可以采用句法方法、拓扑分析方法、图论方法等多种方法 基元提取和分类器训练上的困难使得结构模式识别方法仍未成熟 结构模式识别系统的模式信息通常来源于图像、音频等多媒体信息源 2、句法模式识别（1）句法模式识别的定义：句法模式识别是利用模式的结构信息，以形式语言理论为基础来进行结构模a ccbb b d ddcc c b b b dd ab c d轮廓基元式识别的方法。

傅京荪（1930-1985）美国工程院院士、Purdue大学讲座教授、台湾中央研究院院士，国际模式识别协会(InternationalAssociation for Pattern Recognition:IAPR)创始人和首任主席，上世纪60年代提出句法模式识别。

（2）句法和文法：句法句法来源于语言学，是指由字（词）构成句子的方式，也就是一个句子组成的规则。

句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂的结构。

可以用句法来表达结构模式识别中基元间的结构关系。

文法文法是指一类相似的句子的共同句法规则。

可以用文法来表示一类样本的共同特点。

对某个具体的句子进行句法分析，判别与某类的文法是否相似，可以实现模式识别。

（3）形式语言：形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言，是语言的“数学化”，它由按一定规律构成的句子或符号串的有限或无限的集合组成。

乔姆斯基（Noam Chomsky, 1928--）美国语言学家，麻省理工学院語言学与哲学系荣誉退休教授，曾任该系主任，并任该校认知科学研究中心主任。

1957年出版了《句法结构》一书，提出了形式语言理论，其最初目的是为了研究人类语言抽象和通用的结构规则，后来在计算机编程语言、自动机理论、模式识别等方面都得到了广泛的验证和应用。

在1980年到1992年，乔姆斯基是被文献引用数最多的健在学者，并是有史以来被引用数第八多的学者。

3、句法模式识别系统的组成（1） 句法分析：判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。

（2） 文法推断：从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的文法规则。

利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现结构模式识别问题的求解二、 形式语言理论1、 基本概念： （1）字母表：与所研究的问题有关的符号集合。

例：V 1={A,B,C,D}, V 2={a,b,c,d},V 3={0,2,6,8} （2）句子(链)：由字母表中的符号所组成的有限长度的符号串。

例如有字母表{0,1}，则{0,1,00,01,0110}就是有效句子的集合。

不包括任何符号的句子称为空句，记为λ。

V *：由字母表V 中的符号组成的所有句子的集合，包括空句子λ在内。

例： V *＝{λ,01, 001}V ＋：不包括空句子在内的句子集合，即V ＋＝V *－(λ) （3）句子(链)的长度：句子所包含的符号数目，例: |a 3b 3c 3|=9 （4）语言：由字母表中的符号组成的句子集合，用L 表示。

例：字母表V={a,b} L 1={ab,aab,abab} 有限语言 L 2={a n b m |n,m=0,1,2….}无限语言在一种语言中，构成任何句子都必须遵循统一的规则，这些规则的集合称为文法，用G 表示。

L(G)表示由文法G 构成的语言。

（5）文法文法的数学定义：它是一个四元式，由四个参数构成： G={V N , V T , P, S}预处理特征提取 （基元提取）句法分析文法推断模式信息分类结果类别文法训练过程分类过程V T：终止符，不能再分割的最简基元的集合，用小写字母表示。

V T={a,b,c} V N：非终止符，由基元组成的子模式和句子的集合。

用大写字母表示。

V N={A,B,C}V T，V N的关系：V T∩V N= Φ(空集)V T∪V N= V（全部字母表）S：起始符：属于V N非终止符中的一个符号P：产生式(再写规则)，存在于终止符和非终止符间的关系式。

例：α→β，α∈V N，β∈V N, V T.例：V T＝{你，我，他，吃，饭，水果}；V N＝{句子，主语，谓语，宾语}；S＝“句子”；P：S →“主语”“谓语”“宾语”；“主语” →“你”，“主语” →“我”，“主语” →“他”；“谓语” →“吃”；“宾语” →“饭”，“宾语” →“水果”，2、4种类型的文法：（1）无约束文法（0型文法）设文法G = (V N,V T, P, S)V N：非终止符，用大写字母表示V T：终止符，用小写字符表示S：起始符P：α→β，其中α∈V+，β∈V*α，β无任何限制例：0型文法G = (V N,V T, P, S)，V N = {S,A}，V T = {a,b,c}P: ①S→aSb ②Sb→bA ③abA→cS→aSb→aaSbb→a n Sb n→a n bAb n-1→a n-1abAb n-1→a n-1cb n-1此文法G可产生的语言为：L(G)={a n cb n|n=0,1,2...}.（2）上下文有关文法（1型文法）设文法G = (V N,V T, P, S)P：α1Aα2→α1βα2其中A ∈V N，β∈V+, α1,α2∈V*|α1Aα2|≤|α1βα2|, 或|A|≤|β|α1和α2被视为A的上下文例：G = (V N,V T, P, S)，V N = {S, B, C} V T = {a, b, c}P: ①S→aSBC ②S→abC ③CB→BC④bB→bb ⑤bC→bc ⑥cC→ccP可改写为：①λSλ→λaSBCλ②λSλ→λabCλ③λCBλ→λBCλ④bBλ→bbλ⑤bCλ→bcλ⑥cCλ→ccλ∴都符合1型文法规则∴所以G属于上下文有关文法S →abC →abcS →aSBC →aabCBC →aabBCC →aabbCC →aabbcC →aabbcc S →aSBC → aaSBCBC → aaabCBCBC → aaabBCCBC → aaabBCBCC → aaabBBCCC → aaabbBCCC→ aaabbbCCC → aaabbbcCC → aaabbbccC → aaabbbccc此文法G 可产生的语言为：L(G)={a n b n c n |n=1,2...}（3）上下文无关文法（2型文法） 设文法 G = (V N ,V T , P, S) 产生式P ： A →β其中A ∈V N （是单个的非终止符)β∈V + (可以是终止符，非终止符，不能是空句)对产生式的限制更严格例：文法G = (V N ,V T , P, S)，V N = {S, A, B}，V T = {a, b}P: ① S →aB ② S →bA ③ A →a ④ A →aS ⑤ A →bAA ⑥ B →b ⑦ B →bS ⑧B →aBB各生成式左侧均为V N ，右侧为V N 和V T 的混合，满足上下文无关文法的生成规则，S →aB →abS →abaB →abab S →aB →abS →abbA →abbaS →bA →baS →baaB →baab S →bA →baS →babA →baba S →aB →ab S →bA →ba两种方法替换非终止符：① 最左推导：每次替换都是先从最左边的非终止符开始。

② 最右推导：每次替换都是先从最右边的非终止符开始， （4）正则文法（3型文法） 设文法 G = (V N ,V T , P, S)a cb a cb aacc bb a a ccbbacb基元结构相似的样本产生式P ：A →aB 或 A →a ，其中A,B ∈V N （且是单个字符）， a ∈V T （且是单个字符）产生式右端必须含有终止符正则文法可用状态图表示，非终止符代表状态，终止符代表状态转移的类型例：文法G = ({S, A},{0, 1}, P, S)P: ① S →0A ② A →0A ③ A →1 上述生成式满足正则文法生成规则。

S →0A →00A →000A →0001此文法G 可产生的语言为： L(G)={0n 1|n=1,2...} 此文法对应的状态图为：（5）四种文法的关系限制不严格的文法必然包含限制严格的文法。

（6）四种文法和自动机的关系SAT1 0状态图3型2型1型0型0型无约束文法 → 图灵机1型上下文有关文法 → 线性界限自动机 2型上下文无关文法 → 下推自动机 3型正则文法 → 有限状态自动机三、 句法分析1、模式识别中的句法分析：设有m 个模式类，分别为ω1, ω2,… ωm ，又有对应的m 种文法G 1，G 2，…，G m ，如对于任意样本x ，当有x ∈L （G i ）时，可判定x ∈ωi ，则分类器可由句法分析判别构成。

2、句法分析的主要方法： （1）参考匹配法：将待识别的样本x （句子）与代表各类的模板或参考链Xi 进行匹配，将x 分类到匹配得最好的参考链对应的类特点：简单快速，但未充分利用句法信息，也无法得到x 的句法结构。

（2）状态图法（适用于正则文法）：先画出正则文法对应的状态图：方法一：从状态图的起始符开始，依次处理输入模式x 的各个字符，如果可以找到一条通往终止状态T 的通路，则表示x 可以由该状态图生成。

方法二：从状态图推导中出该文法可产生的所有句子的形式，再用待识别模式x 去匹配；例：正则文法G = ({S, A},{0, 1}, P, S)P: ① S →0A ② A →0A ③ A →1 状态图中的每一个状态（节点）为 1个非终止符，T 为终止状态A →aB 代表两个节点间的状态转移， A →a 代表状态转移的结束。

判决X ∈L （G 1）？X ∈L （G m ）？分类结果待分类样本xx ∈参考链X 1x…… x ∈参考链X 2 x ∈参考链X N判决x ∈ωix ∈X i法一：x 1=0100 不属于该类，x 2＝0001属于该类法二：可推导出该文法可产生的语言为：L(G)={0n 1|n=1,2...}例：G = (V N ,V T , P, S)，V N =（S, A, B, C ），V T =（0,1）P: S →1A ，S →0B ，S →1C ，A →0A ，A →0，B →0，C →0C ，C →0，C →1B法一：x 1=10010，存在通路，可以识别；x2=10110，不存在通路，不可识别 法二： 此文法可生成的句子类型有：X 1=10n+1 , X 2=00 , X 3=10n 10, n=0,1,2,…… （3）填充树法（适用于上下文无关文法）：当给定某待识别句子x 及某个模式类的文法G 时，我们建立一个以x 为底，S 为顶的三角形，按文法G 的产生式来填充此三角形。