リンク文法
リンク文法(英語: Link Grammar)は、Davy TemperleyとDaniel Sleatorにより発明された文法理論である。依存文法の一種であり、単語間の関係を元にして文が合成されるというアプローチをとる。例えば「冠詞(例:The)と名詞(例:apple)はこの順序で出現する」という文法規則は、Theに条件(linking requirements)D+
を、appleには条件D-
を持たせておき、TheとappleをリンクD
によって満足させる(satisfied)事によって表現する。
概要
リンク文法では、単語同士のリンクの結びつき方によって文法規則を表現する。例えば"The cat chased a snake."という文であれば
+---O---+ +-D-+--S--+ +-D-+ | | | | | The cat chased a snake.
というようなリンクを張る事が出来るため[1]、英文として合法である。尚、この時の文法規則は
a the: D+ snake cat: D- & (O- or S+) chased: S- & O+
である[1]。ここで、&は左右両方が同時に使われる事を意味し、orは左右どちらか一方が使われる事を意味する。{A+}
と書いた場合には(A+ or ())
という意味になり、要するに省略可能な条件となる。又、@A+
と書いた場合にはA+
が1個以上何個でも伸ばせる事を意味する。又、+はリンクが右に伸びる事を意味し、-はリンクが左に伸びる事を意味する。他の記法に[A+]
及び[[A+]]
がLink Grammar Parser[2]には存在するが、viterbi/READMEに書いてあるので詳細は省く。
リンクを張る際には、以下の3つの制約を守る必要がある。
- 平面性(Planarity):平面上に記述した時に、リンク同士は交わらない
- 結合性(Connectivity):文中の全てのリンクが成立(suffice)されなければならない
- 満足性(Satisfaction):文中の全ての語の条件が満足(satisfy)されなければならない
リンク文法の能力は文脈自由文法と等しい[1]。又、動的計画法に基づくリンク算出の計算量は、単語数に対しである[1]。
関連項目
脚注
- ^ a b c d Parsing English with a Link Grammar, Daniel D. K. Sleator and Davy Temperley, October 1991, CMU-CS-91-196 http://arxiv.org/pdf/cmp-lg/9508004.pdf
- ^ https://github.com/opencog/link-grammar