CKY構文解析（CYKとも呼ばれ、Cocke-Younger-Kasamiに由来する）は、文脈自由文法に対する構文解析アルゴリズムであり、ボトムアップ構文解析と動的計画法を用いる。これは1961年にItiroo Sakaiによって初めて発表され、後にJohn Cocke、Daniel Younger、Tadao Kasami、Jacob T. Schwartzによって独立に再発見され、彼らの名前にちなんで名付けられた。このアルゴリズムは、与えられた文字列が文法によって生成可能かどうかを判定し、可能であればその文字列に対するすべての可能な構文解析木を構築できる。
標準的なCKYのバージョンは、チョムスキー標準形（CNF）の文脈自由文法のみを対象としており、すべての生成規則はA → BC（2つの非終端記号）またはA → a（終端記号）のいずれかの形式を持つ。空文字列を生成しない任意の文脈自由文法は、等価なCNF文法にアルゴリズム的に変換できるため、この制限は原理的にはアルゴリズムの適用可能性を制限しない。空文字列を生成する文法については、開始記号Sに対して規則S → εを明示的に許可することができる。
CKY構文解析の重要性は、その最悪時の時間計算量がO(n^3 · |G|)であることに由来する。ここで、nは入力文字列の長さ、|G|はCNF文法のサイズである。これにより、漸近的な最悪時の挙動に関して最も効率的な構文解析アルゴリズムの1つとなるが、実際のシナリオでは他のアルゴリズムが平均実行時間において優れる場合もある。
アルゴリズムの概要
このアルゴリズムは、3次元テーブルP[l, s, v]を埋めることで機能し、各エントリは位置sから始まる長さlの部分文字列が非終端記号R_vから生成可能かどうかを示すブール値である。テーブルは部分文字列の長さの増加順に埋められ、長さ1の部分文字列から始まる。
入力内の各終端記号について、アルゴリズムはR_v → a_sの形式のすべての単位生成規則をチェックし、対応するテーブルエントリをtrueに設定する。より長い部分文字列については、部分文字列を2つの部分に分割するすべての可能な分割を考慮し、Bが最初の部分を生成しCが2番目の部分を生成するような生成規則A → BCが存在するかどうかをチェックする。そのような生成規則が存在する場合、Aのエントリがtrueに設定される。
擬似コード
入力をn文字からなる文字列Iとする: a1 ... an。
文法にr個の非終端記号R1 ... Rrが含まれ、開始記号はR1とする。
P[n,n,r]をブール値の配列とする。Pのすべての要素をfalseに初期化する。
back[n,n,r]を逆参照トリプルのリストの配列とする。backのすべての要素を空リストに初期化する。
各s = 1からnについて
各単位生成規則Rv → asについて
P[1,s,v] = trueに設定
各l = 2からnについて -- スパンの長さ
各s = 1からn-l+1について -- スパンの開始位置
各p = 1からl-1について -- スパンの分割
各生成規則Ra → Rb Rcについて
P[p,s,b]とP[l-p,s+p,c]がtrueの場合
P[l,s,a] = trueに設定、
<p,b,c>をback[l,s,a]に追加
P[n,1,1]がtrueの場合
Iは言語のメンバーである
backを返す -- backを通じてステップを遡ることで、文字列のすべての可能な構文解析木を容易に構築できる。
それ以外の場合
"not a member of language"を返す
例
次のCNF文法を考える:
S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish
文字列「she eats the fish with the fish」を解析するために、アルゴリズムはまずすべての長さ1の部分文字列をマークする。例えば、NP → sheのためP[1,1,NP]がtrueに設定され、VP → eatsのためP[1,2,VP]がtrueに設定される。次に、長さ2の部分文字列を処理し、「she eats」はS → NP VPとして導出できるため、P[2,1,S]がtrueになる。プロセスはより長い部分文字列に対して続き、すべての分割を考慮する。最後に、P[n,1,S]がtrueの場合、文字列は言語の一部として認識され、逆参照により構文解析木の再構築が可能になる。
応用と変種
CKY構文解析は、自然言語処理や計算言語学で広く使用されており、特に確率的文脈自由文法を用いた構文解析で重要である。重み付き文法を扱うための変種や、平均的な性能を向上させるための変種が開発されている。このアルゴリズムの動的計画法アプローチは、CNF変換なしで任意の文脈自由文法を扱うが同様の最悪時計算量を持つEarley構文解析器など、他の構文解析手法とも関連している。
現代の人工知能システムでは、CKY構文解析はニューラルネットワークベースのアプローチ、特に大規模言語モデルで使用されるトランスフォーマーモデルによって大部分が取って代わられている。しかし、このアルゴリズムは形式言語理論における重要な基礎技術であり、コンピュータサイエンスのカリキュラムで今も教えられている。その動的計画法とボトムアップ解析の原理は、系列変換モデルやビームサーチ復号などの他の分野にも現れている。
このアルゴリズムの効率性と明快さは、構文解析や機械学習に関する教科書の標準的な例となっている。MIT CSAILやスタンフォードAIラボなどの研究機関がその研究と応用に貢献しており、バイオインフォマティクスやコンパイラ設計など、構造化データの正確な解析を必要とする分野で今も関連性を持っている。
制限
CKY構文解析は文法がチョムスキー標準形であることを要求し、これにより生成規則の数と文法のサイズが増加する可能性がある。O(n^3)の最悪時時間計算量は、特にリアルタイムアプリケーションにおいて、非常に長い入力文字列に対しては法外なものとなり得る。さらに、このアルゴリズムの空間計算量はO(n^2 · r)であり、多くの非終端記号を持つ文法では大きくなる可能性がある。これらの制限にもかかわらず、CKY構文解析は正確な構文解析アルゴリズムのベンチマークであり、文脈自由言語の研究における重要な概念であり続けている。