Cocke-Younger-Kasamiアルゴリズム（CYK、またはCKY）は、コンピュータ科学における文脈自由文法のための構文解析アルゴリズムである。1961年にItiroo Sakaiによって最初に発表され、後にJohn Cocke、Daniel Younger、Tadao Kasami、およびJacob T. Schwartzによって再発見され、彼らの名前にちなんで命名された。このアルゴリズムは、ボトムアップ構文解析と動的計画法を用いて、与えられた文字列が与えられた文法によって生成可能かどうかを判定し、構文木を構築することもできる。その最悪実行時間はO(n^3 · |G|)であり、ここでnは入力文字列の長さ、|G|はチョムスキー標準形における文法のサイズである。これにより、漸近的最悪計算量の観点から最も効率的な構文解析アルゴリズムの一つとなっているが、実際には他のアルゴリズムが平均性能で優れる場合もある。
CYKアルゴリズムは、自然言語処理やコンパイラ設計において広く使用されており、構文解析は基本的なステップである。特に、その単純さと、曖昧な文法に対しても保証された多項式時間が評価されている。このアルゴリズムの動的計画法への依存は、すべての可能な構文解析を体系的に扱うことを可能にし、プログラミング言語の構文解析や人工知能システムにおける構文解析などの応用に有用である。
歴史的背景
このアルゴリズムは1961年にItiroo Sakaiによって最初に記述されたが、1960年代後半にJohn Cocke、Daniel Younger、およびTadao Kasamiによる独立した再発見を通じて注目を集めた。Jacob T. Schwartzもその発展に貢献した。アルゴリズムの名前はこれらの再発見を反映しており、CYKという頭字語はCocke、Younger、Kasamiに由来する。このアルゴリズムは、形式言語とオートマトン理論に関するコースなど、コンピュータ科学教育における標準的なトピックとなった。その発展は現代の機械学習やニューラルネットワークによる構文解析アプローチに先行するが、基礎的な技法として今もなお関連性を持っている。
標準形：チョムスキー標準形
標準バージョンのCYKアルゴリズムは、文脈自由文法がチョムスキー標準形（CNF）であることを要求する。CNFでは、すべての生成規則はA → BC（ここでBとCは非終端記号）またはA → α（ここでαは終端記号）の形式である。さらに、開始記号Sは空文字列を許容するためにS → εという生成を持つ場合がある。空文字列を生成しない任意の文脈自由文法は、Sipserが1997年に示したように、等価なCNF文法に変換できる。この変換はアルゴリズム的であり、文法によって生成される言語を保持する。CNFの要件は、部分文字列を2つの部分に分割する方法を制限するため、構文解析プロセスを簡素化し、効率的な動的計画法を可能にする。
アルゴリズムの説明
CYKアルゴリズムは、三次元テーブルP[l, s, v]を埋めることによって動作する。ここで、lは部分文字列の長さ、sはその部分文字列の開始位置、vは非終端記号である。エントリP[l, s, v]は、位置sから始まる長さlの部分文字列が非終端記号R_vから導出可能である場合に真に設定される。アルゴリズムは部分文字列の長さの増加順に進み、長さ1から始まる。
長さ1の各部分文字列について、アルゴリズムはR_v → a_sの形式の単一生成をチェックする。ここでa_sは位置sの終端記号である。長さ2以上の部分文字列については、部分文字列を2つの部分に分割するすべての可能な分割を考慮し、各生成A → BCについて、最初の部分がBから導出可能であり、2番目の部分がCから導出可能であるかをチェックする。もしそうであれば、その部分文字列がAから導出可能であるとマークする。アルゴリズムはまた、構文木の再構築を可能にするバックポインタテーブルも維持する。
最後に、P[n, 1, 1]が真である場合、つまり開始記号R_1が文字列全体を導出できる場合、入力文字列は言語のメンバーとして認識される。バックポインタはその後、すべての可能な構文木を構築するために使用できる。
例
以下のCNF文法を考える：
- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the
この文法は、"she eats the fish with the fork"のような文を解析できる。CYKアルゴリズムは、まず単語の部分文字列をマークすることによってテーブルを埋める："she"をNP、"eats"をVPまたはV、"the"をDet、"fish"をN、"with"をP、"fork"をNとして。次に、部分文字列を組み合わせる："the fish"をNP（Det N）、"eats the fish"をVP（V NP）、といった具合である。最終的に、文全体がSから導出可能であると判定し、バックポインタが構文木構造を明らかにする。
応用と意義
CYKアルゴリズムは、構文解析理論と実践において重要である。自然言語処理での構文解析、コンパイラ設計でのプログラミング言語の構文解析、およびバイオインフォマティクスでのRNA二次構造予測に使用される。その最悪時間計算量O(n^3)は、一般的な文脈自由文法の構文解析において最悪の場合に最適であり、Earleyパーサのような特殊なアルゴリズムは特定の文法に対してより効率的である場合がある。このアルゴリズムの動的計画法アプローチは、曖昧な文法にも適しており、すべての可能な構文解析を列挙できる。現代の人工知能では、CYKアルゴリズムは確率的文脈自由文法や統計的構文解析に適応されており、生成に対する確率分布が与えられた場合に最も可能性の高い構文木を計算する。
制限と拡張
標準CYKアルゴリズムの一つの制限は、CNFの要件であり、文法のサイズを増加させ、効率に影響を与える可能性がある。CNFにない文法に対する拡張が存在し、例えばEarleyアルゴリズムは任意の文脈自由文法を直接扱う。さらに、CYKアルゴリズムは重み付き文法や確率的文法に拡張されており、各生成に重みや確率があり、最大の重みや確率を持つ構文を見つけることを目的とする。これらの拡張は音声認識や機械翻訳で使用される。このアルゴリズムはまた、深層学習ベースのモデルにおけるより高度な構文解析技術の基礎を形成しているが、それらは明示的な文法規則ではなくニューラルネットワークアプローチを使用することが多い。