リンク文法のソースを表示

'''リンク文法'''（{{lang-en|Link Grammar}}）は、[[Davy Temperley]]と[[Daniel Sleator]]により発明された[[文法]][[理論]]である。[[依存文法]]の一種であり、単語間の関係を元にして文が合成されるというアプローチをとる。例えば「冠詞(例：The)と名詞(例：apple)はこの順序で出現する」という文法規則は、Theに条件(linking requirements)<code>D+</code>を、appleには条件<code>D-</code>を持たせておき、Theとappleをリンク<code>D</code>によって満足させる(satisfied)事によって表現する。

== 概要 ==
リンク文法では、単語同士のリンクの結びつき方によって文法規則を表現する。例えば"The cat chased a snake."という文であれば<syntaxhighlight lang="text">
           +---O---+
 +-D-+--S--+   +-D-+
 |   |     |   |   |
The cat chased a snake.
</syntaxhighlight>というようなリンクを張る事が出来るため<ref name=":0">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</ref>、英文として合法である。尚、この時の文法規則は<syntaxhighlight lang="text">
a the: D+
snake cat: D- & (O- or S+)
chased: S- & O+
</syntaxhighlight>である<ref name=":0" />。ここで、&は左右両方が同時に使われる事を意味し、orは左右どちらか一方が使われる事を意味する。<code>{A+}</code>と書いた場合には<code>(A+ or ())</code>という意味になり、要するに省略可能な条件となる。又、<code>@A+</code>と書いた場合には<code>A+</code>が1個以上何個でも伸ばせる事を意味する。又、+はリンクが右に伸びる事を意味し、-はリンクが左に伸びる事を意味する。他の記法に<code>[A+]</code>及び<code><nowiki>[[A+]]</nowiki></code>がLink Grammar Parser<ref>https://github.com/opencog/link-grammar</ref>には存在するが、[https://github.com/opencog/link-grammar/blob/master/viterbi/README viterbi/README]に書いてあるので詳細は省く。

リンクを張る際には、以下の3つの制約を守る必要がある。
# 平面性(Planarity)：平面上に記述した時に、リンク同士は交わらない
# 結合性(Connectivity)：文中の全てのリンクが成立(suffice)されなければならない
# 満足性(Satisfaction)：文中の全ての語の条件が満足(satisfy)されなければならない
リンク文法の能力は文脈自由文法と等しい<ref name=":0" />。又、動的計画法に基づくリンク算出の計算量は、単語数<math>n</math>に対し<math>O(n^3)</math>である<ref name=":0" />。

== 関連項目 ==
* [[形式文法]]
* [[依存文法]]

== 脚注 ==
{{Reflist}}

{{デフォルトソート:りんくふんほう}}
[[Category:依存文法]]
[[Category:自然言語構文解析]]