CYK法

CYK法 (Cocke-Younger-Kasami アルゴリズム)について

CYK法は、与えられた文字列が特定の文脈自由文法によって生成可能かどうかを判定し、可能であればその生成方法を求めるアルゴリズムです。このアルゴリズムは、ジョン・コック、ダニエル・ヤンガー、嵩忠雄の3人の研究者によって独立に開発され、それぞれの頭文字を取ってCYK法と呼ばれています。文脈自由文法の構文解析手法として広く認識されており、特に動的計画法の一種として知られています。

CYK法の概要

標準的なCYK法は、チョムスキー標準形で記述された文脈自由文法を対象としています。しかし、任意の文脈自由文法はチョムスキー標準形に変換することが比較的容易であるため、CYK法は広範な文脈自由文法の解析に適用できます。また、CYK法を拡張することで、チョムスキー標準形でない文脈自由文法にも対応できますが、アルゴリズムの複雑性が増す傾向があります。

時間計算量

CYK法の最悪時間計算量はO(n^3)であり、ここでnは入力文字列の長さです。この計算量は、任意の文脈自由言語を認識するアルゴリズムとしては非常に効率的であり、CYK法が広く利用される理由の一つです。ただし、特定の文脈自由言語のサブセットに対しては、より効率的なアルゴリズムが存在する場合もあります。

アルゴリズムの詳細

CYK法は、ボトムアップ型の構文解析アルゴリズムであり、文脈自由言語のメンバーシップ問題を決定可能であることを構成的に証明できるという点で、理論的にも重要な意味を持ちます。アルゴリズムの基本的な手順は以下の通りです。

1. 初期化:
- 入力文字列を `a1 ... an` とします。
- 文法に含まれる非終端記号を `R1 ... Rr` とします。
- 開始記号を含む非終端記号の集合を `Rs` とします。
- 3次元のブール型配列 `P[n, n, r]` を `false` で初期化します。

2. 長さ1の文字列の処理:
- 各 `i` について、生成規則 `Rj -> ai` が存在する場合、`P[i, 1, j]` を `true` に設定します。

3. 長さ2以上の文字列の処理:
- 文字列の長さ `i` を 2 から `n` まで増やしながら、以下の処理を繰り返します。
- 各開始位置 `j` について、文字列を2つの部分に区切り、それぞれの部分に対する非終端記号 `RB` と `RC` を探します。
- もし生成規則 `RA -> RB RC` が存在し、`P[j, k, B]` と `P[j + k, i - k, C]` がともに `true` ならば、`P[j, i, A]` を `true` に設定します。

4. 結果判定:
- `P[1, n, x]` のいずれかが `true` である場合 (ここで `x` は `Rs` のインデックスを指す)、入力文字列は文法によって生成可能です。
- それ以外の場合は、入力文字列は文法によって生成できません。

アルゴリズムの解説

CYK法は、与えられた文字列の全ての可能な部分文字列に対して、それがどの非終端記号から生成可能かを調べます。この過程は、まず長さ1の部分文字列から始まり、徐々に長い部分文字列へと進みます。長さが2以上の部分文字列に対しては、その部分文字列を2つに分割し、それぞれの部分が対応する非終端記号によって生成可能かどうかを調べ、最終的に、入力文字列全体が開始記号から生成されるかどうかを判定します。

アルゴリズムの拡張

CYK法は、構文木を構築するよう拡張することも可能です。この拡張では、ブール値の代わりに、構文木のノードを配列に格納します。また、文法が曖昧な場合は、複数の構文木を格納する必要があります。さらに、バックポインタと呼ばれる別のテーブルを使うことで、構文木をより効率的に構築することも可能です。

加重文脈自由文法や確率文脈自由文法を扱うように拡張することも可能です。この場合、配列にはブール値ではなく、重みや確率を格納し、最適な構文木を探索することができます。

その他の情報

• - 関連アルゴリズム:

- チャートパーサ (特にアーリー法) は、CYK法と同様に構文解析を行うアルゴリズムです。
- GLR法は、より広範な文法を扱える構文解析アルゴリズムです。
- パックラット構文解析は、再帰下降構文解析の拡張であり、文法を直接コードに変換できる特徴があります。

• - 参考文献

- John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes.
- T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages.
- Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3.

CYK法は、構文解析の分野において基礎となる重要なアルゴリズムであり、コンパイラや自然言語処理など、多くの分野で応用されています。

もう一度検索