前面介紹的所有思想都屬于統計模式識别,然而統計模式識别存在2個問題:
1.有的模式結構很複雜,不能用一個矢量來表示。
2.有的模式識别任務中,我們更關心如何描述它的結構特征。
是以需要另外一種模式識别:結構模式識别。
這其中,句法模式識别主要使用形式語言來描述模式結構,在理論上完備,表1是句法模式識别與統計模式識别的對應關系,下面做介紹。
表1
串文法就是一種機器能識别的文法,是以先講講文法。
字母表V
字母a,b,c的有限集合。
句子x,y,z
V中的符号形成的有限長度的字元串。
這其中
是V的閉包,包含了字母表能組成所有句子的集合。
而
是V的正閉包,就是把閉包裡面的那1個空串去掉就好了。
這種差別就像是正數與非負數的關系,非負數去掉0就是非負數了。
文法G =
一個文法或者說文法,有4部分組成就好了。
這4個部分依次代表:非終止符、終止符、生成規則、起始符。
這其中有
舉個例子:The boy runs.如圖1所示。
圖1
非終止符就是那些還要繼續尋找對應關系的元素,比如說Noun,它與我們想表達的Theboy runs.這個句子相比要進一步尋找對應關系,Noun并不是最終出現在句子裡的部分,是以倒了Noun并沒有終止,Noun繼續連結到boy才OK。是以像Noun這樣的元素就叫非終止符。
終止符剛剛介紹了,就是最終要出現在句子裡的部分。像The、boy、runs這些都是。
起始符在這個例子中是Sentence,就是句子開始的标志。
P(生成規則)比較複雜,生成規則就是符号的變換規則表。就像是法律一樣,在相應的文法環境下,必須按照這個規則來生成句子。
符号習慣
非終止符:大寫字母
終止符:小寫字母
僅由終止符構成的字元串:用後面小寫字母構成的x,y,z
由終止符和非終止符混合構成:用希臘字母
表示一些列地調用P中的規則。
語言L(G)
語言是字元串的集合。由文法G産生。特點是
1.所有的字元串由終止符構成
2.每個字元串都是從S出發調用P中的規則而産生。
串文法的分類
第0類:無限制文法
這種對文法不加限制,基本沒用。
第1類:上下文有關文法
這種規則就是說,僅當上下文是
時,中間的非終止符A才能替換成為混串。這就是其名字的由來。
第2類:上下文無關文法
這種文法是說,不論上下文如何A都可以用
來替換。
第3類:正規文法
正規文法是最常用的一種文法。
四種文法的關系
如圖2.
圖2
舉個例子:染色體分析
現在要識别2類染色體:中央着絲染色體和頂端着絲染色體。如圖3.
圖3
作為句法的5種基元a,b,c,d,e分别是5種最簡單的形狀,如圖4.
圖4
這些基元能構成6種子模式(就是非終止符):
S——臂對,B――底, C——邊, D——單個臂, E——右臂, F——左臂。
于是這個染色體文法就可以表示出來了:
這個P生成規則太多了實在是,而且比如A究竟要用到哪條規則是無法事先知道的,要試試。隻要最後試出來一條能走完的路徑就認為是符合文法的。否則隻有當所有可能的路徑都不能從S出發,才可以認為該句子是不符合文法的。
最後按照該文法可以得到2種染色體對應的字元串分别為:
1. abcbabdbabcbabdb
2. ebabcbab
如圖5.
圖5
歡迎參與讨論并關注本部落格和微網誌以及知乎個人首頁後續内容繼續更新哦~
轉載請您尊重作者的勞動,完整保留上述文字以及文章連結,謝謝您的支援!