4

CYK/CKY アルゴリズムが文法を Chomsky Normal Form (CNF) にする必要がある場所をいくつか読んだことがあります。

CYK の標準バージョンは、チョムスキー正規形 (CNF) で与えられた文脈自由文法でのみ動作します ~ウィキペディア

ただし、文法が CNF にない CKY アルゴリズムの例もいくつか見てきました。Christopher Manning が使用する一般的な例は、単項規則を含む「fish people fish tanks」(参照: PPT スライド #19 ) です。

S -> NP VP [0.9]
S -> VP [0.1]
VP -> V NP [0.4]
Vp -> V [0.6]
...

また、プロダクションの RHS で 3 つの非終端記号を使用する CKY を示す他の例も見てきました (例: VP -> Verb NP NP reference )。なぜ不一致なのですか？

4

1 に答える 1

6

CYK の実行時間は、最長生成規則の長さに依存します。これは、アルゴリズムが、長さ k の生成のために文字列を k 個の部分に分解するすべての可能な方法を考慮するためです。これは、フェーズごとの実行時間が O(n k ) であることを意味します。ここで、k は最長の生産の長さです。O(n) フェーズがあるため、最大生成長 k の文法での CYK の実行時間は O(n k+1 ) です。

CYK は CNF にない文法で正しく機能しますが、ランタイムは文字列の長さが 3 次になるとは限りません。CNF 要件は k = 2 を強制するだけなので、O(n 3 ) 全体のランタイムが保証されます。

于 2016-04-27T23:03:50.910 に答える