|
CYK法（）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略。文字列の構文解析手法として知られている。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。 CYK法の最悪時間計算量は Θ(n3) であり、''n'' は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。 == アルゴリズム == CYK法はボトムアップ構文解析アルゴリズムであり、文脈自由言語のメンバシップ問題が決定可能であることを構成的に証明できることから、理論的にも重要である。 メンバシップ問題についてのCYK法は次の通り。 Let ''n'' 文字 ''a''1 ... ''a''''n'' からなる文字列を入力する。 Let 文法は ''r'' 個の非終端記号 ''R''1 ... ''R''''r'' からなる。 この文法には開始記号を含む部分集合 Rs が含まれる。 Let P をブーリアン型の配列とする。P の全要素を false で初期化する。 For each i = 1 to n For each 生成規則 Rj → ai があるなら、set P = true. For each i = 2 to n -- 範囲の長さ For each j = 1 to n-i+1 -- 範囲の開始位置 For each k = 1 to i-1 -- 範囲の区分 For each 生成規則 RA -> RB RC If P and P then set P = true If P のいずれかが true （x は集合 s について反復される。s は Rs の全てのインデックスの集合） Then 文字列は言語のメンバーである。 Else 文字列は言語のメンバーではない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「CYK法」の詳細全文を読む スポンサード リンク
|