トップ > 自然言語処理 > CYKアルゴリズム

CYKアルゴリズム

自然言語処理 計算理論

前回はCFLに関してのパンピングレンマだったが、あんまり覚えてない。正則言語だと同じところを2回通って、ループができるか?というところが肝だった(気がする)が、CFLに関してのパンピングレンマだとTreeに関して同じ構造が出てくるか?が肝っぽい、ということは記憶にある。

CYKアルゴリズム

  • CFLに関しての所属問題(CFL Lに対して語wがw \in Lか)は決定可能!
    • チョムスキー標準形を使って、空語が出てこない状態にしておく
  • これを判定するアルゴリズムはCocke-Younger-Kasami(CYK)法アルゴリズムがある
    • DPになっている
    • Kasami先生という方は、NAISTの先生だったらしく(計算理論の)伊藤先生の先生だったとか
  • 考え方としては普通のDP
    • しかし、計算量はO(n^3)...
      • 余談: Javaとかだと文法を制限することによってO(n)で構文解析が可能にしてあるらしい
  • 例7.2とかDPを素直に実行してあげればよいようだ
    • V={i, j}はi番目から始まってj文字、というのを表わしている(重要)
    • 右辺にくるような左辺はあるか? => あったら、左辺のほうを表に入れていく
    • 表の一番上の列を埋めてから、2列目の左側から埋めていく
      • 下にいくにつれてどこでくぎるかの組合せが増えていってややこしい...
  • 最後に左下にSがくるかで最後の結果を返す

問題7.1

次のCFG G
G = \{S \rightarrow AB | BC, A \rightarrow BA | a, B \rightarrow CC | b, C \rightarrow AB | A\}
に対して

  • (a) ababa
  • (b) aabab

がL(G)に属するかどうか

ababa

V_{i, j}の表を埋めると次のようになり、V_{1, 5}にSがあるので、ababaはL(G)に属する。

w b a a b a
j/i 1 2 3 4 5
1 A, C B A, C B A, C
2 S, C S, A S, C S, A
3 B S, C B
4 B B
5 S, A, C

プッシュダウンオートマトン

  • CFGに関する機械を導入
    • 正則言語の正則文法に対応するものが、プッシュダウンオートマトンと考えられる
  • 生成するもの(正則表現とCFG)と認識するもの(正則文法とプッシュダウンオートマトン)
  • 有限オートマトンの補助記憶としてスタック(最初に入ったものが最初に出ていく)を付加
  • PDAは「非決定性」で動作する

自然言語処理概論 (ライブラリ情報学コア・テキスト)

自然言語処理概論 (ライブラリ情報学コア・テキスト)