CYKアルゴリズム

擬似コードによるアルゴリズムは以下のとおりです。

入力はn文字からなる文字列I : a 1 ... a nとする。 文法はr 個の非終端記号R 1 ... R rを含み、開始記号はR 1とする。P [ n , n , r ] をブール値の配列とする。P のすべての要素をfalse に初期化する。back [ n , n , r ]をバックポイント トリプルのリストの配列とする。back のすべての要素を空のリストに初期化する。各s = 1 からnに対して、各単位生産R v → a sに対して、 P [ 1 , s , v ] = true とします。各l = 2 からnまで-- スパンの長さ各s = 1 からn - l +1まで-- スパンの開始各p = 1 からl -1まで-- スパンの分割各生成規則R a → R b R c P [ p , s , b ] およびP [ l - p , s + p , c ]の場合、P [ l , s , a ] = true と設定します。 <p,b,c> をback [ l , s , a ]に追加する P [n, 1 , 1 ]が真であれば、Iは言語の要素である 。backを返す 。backを通して手順をたどることで、文字列のすべての可能な構文木を簡単に構築できる。そうでなければ、 「言語の要素ではない」を返す。

入力はn文字からなる文字列I : a 1 ... a nとする。 文法はr 個の非終端記号R 1 ... R rを含み、開始記号はR 1とする。P [ n , n , r ]を実数の配列とする。P のすべての要素をゼロに初期化する。back [ n , n , r ]をバックポイント トリプルの配列とする。 各s = 1 からnについて、各単位生成R v → a sについて、 P [ 1 , s , v ] = Pr( R v → a s ) と設定する。各l = 2 からnについて-- スパンの長さ、各s = 1 からn - l +1について-- スパンの開始、各p = 1 からl -1について-- スパンの分割、各生成R a → R b R cについて 、prob_splitting = Pr( R a → R b R c ) * P [ p , s , b ] * P [ l - p , s + p , c ] と設定する。prob_splitting > P [ l , s , a ]の場合、P [ l , s , a ] = prob_splitting と 設定し、 [ l , s , a ] = <p,b,c> と設定する。P [n, 1 , 1 ] > 0の場合、逆 方向にたどって構文木を見つけ、構文木を 返す。そうでない場合は 、「言語のメンバーではありません」を返す。

非公式に言えば、このアルゴリズムは入力文字列のすべての可能な部分文字列を考慮し、${\displaystyle P[l,s,v]}$長さのサブストリングが真である場合${\displaystyle l}$から${\displaystyle s}$非終端から生成できる${\displaystyle R_{v}}$長さ1の部分文字列の処理が終わると、長さ2の部分文字列の処理に移り、以下同様に続きます。長さ2以上の部分文字列については、部分文字列を2つの部分に分割するすべての可能な方法を考慮し、何らかの生成規則が存在するかどうかを確認します。${\displaystyle A\to B\;C}$そのため${\displaystyle B}$最初の部分と一致し、${\displaystyle C}$2番目の部分と一致します。そうであれば、記録します。${\displaystyle A}$部分文字列全体に一致する場合。この処理が完了すると、入力文字列全体を含む部分文字列が開始記号に一致する場合、文法によって入力文字列が生成されます。

上記のアルゴリズムは、文が対象言語に含まれるかどうかのみを判定する認識器です。これを、ブール値1の代わりに構文木ノードを配列の要素として格納することで、構文木も構築する構文解析器に簡単に拡張できます。ノードは、そのノードを生成するために使用された配列要素にリンクされ、ツリー構造を構築します。1つの構文木のみを生成する場合は、各配列要素にそのようなノードが1つだけ必要です。しかし、曖昧な文のすべての構文木を保持する場合は、対応するノードが構文解析プロセスで取得できるすべての方法のリストを配列要素に格納する必要があります。これは、いわゆるバックポインタの2番目のテーブルB[n,n,r]を使用して行われることがあります。最終的な結果は、可能な構文木の共有フォレストとなり、共通のツリー部分はさまざまな構文解析間で分割されます。この共有フォレストは、解析された文のみを生成する曖昧な文法として都合よく読むことができますが、元の文法と同じ曖昧さを持ち、非終端記号の非常に単純な名前変更を除いて同じ構文木を持ちます。これはLang（1994）によって示されています。

Lange & Leiß (2009)が指摘しているように、チョムスキー標準形への既知の変換の欠点は、文法サイズの望ましくない肥大化につながる可能性があることである。文法のサイズは、その生成規則のサイズの合計であり、規則のサイズは右辺の長さに 1 を加えたものである。${\displaystyle g}$元の文法のサイズを表すために、最悪の場合のサイズ拡大は、${\displaystyle g^{2}}$に$2^2g$変換アルゴリズムによって異なる。教育での使用のために、LangeとLeißはCYKアルゴリズムを少し一般化したものを提案している。「アルゴリズムの効率性、説明の明瞭さ、証明の簡潔さを損なうことなく」（Lange & Leiß 2009 ）。

CYKアルゴリズムを拡張して、重み付き確率的文脈自由文法を用いて文字列を解析することも可能です。この場合、ブール値の代わりに重み（確率）がテーブルPに格納されるため、P[i,j,A]には、iからjまでの部分文字列がAから導出される最小の重み（最大の確率）が格納されます。さらにアルゴリズムを拡張すると、文字列のすべての解析結果を、重みが低い順（確率が高い順）から高い順（確率が低い順）に列挙できるようになります。

CYKの最悪実行時間は$\displaystyle \Theta (n^{3}\cdot |G|)}$ここで、nは解析された文字列の長さ、| G | は CNF 文法Gのサイズです。これにより、これは実際に一般的な文脈自由言語を認識するための最も効率的なアルゴリズムの 1 つになります。Valiant (1975)は CYK アルゴリズムの拡張を提供しました。彼のアルゴリズムは CYK アルゴリズムと同じ構文解析テーブルを計算しますが、0-1 エントリを持つ行列の効率的な乗算アルゴリズムをこの計算に利用できることを示しました。

これらの行列の乗算にCoppersmith–Winogradアルゴリズムを使用すると、漸近的な最悪実行時間は次のようになります。${\displaystyle O(n^{2.38}\cdot |G|)}$しかし、ビッグオー記法で隠された定数項は非常に大きいため、コッパースミス・ウィノグラードアルゴリズムは、現代のコンピュータでは処理できないほど大きな行列に対してのみ有効であり（Knuth 1997 ）、このアプローチは減算を必要とするため、認識にしか適していません。効率的な行列乗算への依存は完全には避けられません。Lee （2002）は、時間で動作する文脈自由文法のパーサーは、${\displaystyle O(n^{3-\varepsilon }\cdot |G|)}$は、積を計算するアルゴリズムに効果的に変換できます。${\displaystyle (n\times n)}$-時間内に0-1エントリを持つ行列${\displaystyle O(n^{3-\varepsilon /3})}$そしてこれは、Abboud ら^{[ 4 ]}によって定数サイズの文法に適用するように拡張されました。