CYK法

CYK法（英: CYK algorithm）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略（それぞれ、RISCの先駆と言われる801などでも知られるジョン・コック、Daniel Younger、嵩忠雄である）。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。

標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。

CYK法の最悪時間計算量は Θ(n³) であり、n は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。

アルゴリズム

CYK法はボトムアップ構文解析アルゴリズムであり、文脈自由言語のメンバシップ問題が決定可能であることを構成的に証明できることから、理論的にも重要である。

メンバシップ問題についてのCYK法は次の通り。

Let n 文字 a₁ ... a_n からなる文字列を入力する。
Let 文法は r 個の非終端記号 R₁ ... R_r からなる。
この文法には開始記号を含む部分集合 R_s が含まれる。
Let P[n,n,r] をブーリアン型の配列とする。P の全要素を false で初期化する。
For each i = 1 to n
  For each 生成規則 R_j → a_i があるなら、set P[i,1,j] = true.
For each i = 2 to n -- 範囲の長さ
  For each j = 1 to n-i+1 -- 範囲の開始位置
    For each k = 1 to i-1 -- 範囲の区分
      For each 生成規則 R_A -> R_B R_C
        If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
If P[1,n,x] のいずれかが true （x は集合 s について反復される。s は R_s の全てのインデックスの集合）
  Then 文字列は言語のメンバーである。
  Else 文字列は言語のメンバーではない。

解説

形式的でない説明をするなら、このアルゴリズムは単語の並びについて、考えられるあらゆる組合せを考慮し、与えられた文字列の i 番目から長さ j の並びが R_k から生成される場合に P[i,j,k] を true にセットする。長さ 1 の並びを検討したら、次に長さ 2 の並びというように検討していく。長さ 2 以上の並びの場合、その並びを2つに分け（分け方を様々に変えて）、P → Q R という生成規則で Q と R がその並びの前半部分と後半部分にマッチするかどうかを調べる。マッチする場合、P をその並び全体にマッチするものとして記録する。この一連の処理が完了すると、入力文字列全体を含む記号の並びが開始記号から生成されるかどうかが判定できる。

CYK テーブル
S
	VP

S
	VP			PP
S		NP			NP
NP	V, VP	Det.	N	P	Det	N
she	eats	a	fish	with	a	fork

拡張

このアルゴリズムを、文が言語に含まれるかどうかを決定するだけでなく、構文木を構築するよう拡張するには、構文木のノードをブーリアンの代わりに配列の要素として格納すればよい。認識しようとする文法は曖昧な場合があるので、ノードのリストを格納する必要がある（可能な解釈からひとつだけ選べばよい場合はその限りではない）。従って、結果として複数の構文木が得られる。別の方式としては、backpointers と呼ばれる第二のテーブル B[n,n,r] を使う方式もある。

加重文脈自由文法や確率文脈自由文法を使って文字列の構文解析をするよう拡張することも可能である。この場合、加重や確率はテーブル P にブーリアンの代わりに格納される。すなわち、P[i,j,A] は i から長さ j の並びが A から生成される最小加重（または最大確率）を格納する。さらにアルゴリズムを拡張すれば、あらゆる加重（確率）の構文木を列挙できる。

参考文献

John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n³. Information and Control 10(2): 189–208.