nlp - CKY 真的需要 CNF 吗？

Question

我已经阅读了许多 CYK/CKY 算法要求语法采用乔姆斯基范式 (CNF) 的地方，例如

CYK 的标准版本仅适用于以乔姆斯基范式 (CNF) 给出的上下文无关文法 ~维基百科

但是，我还看到了许多 CKY 算法的示例，其中语法不在 CNF 中。Christopher Manning 使用的一个常见示例是“鱼人鱼缸”（参考：PPT 幻灯片 #19），其中包含一元规则：

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

我还看到了演示 CKY 的其他示例，这些示例在生产的 RHS 中使用了三个非终端（例如VP -> Verb NP NP reference）。为什么会出现差异？

Answer 1

CYK 的运行时间取决于最长产生式规则的长度，因为该算法考虑了将字符串分解为 k 个部分以产生长度为 k 的所有可能方式。这意味着每个阶段的运行时间是 O(n ^k )，其中 k 是最长生产的长度。由于存在 O(n) 个阶段，CYK 在具有最大产生长度 k 的文法上的运行时间是 O(n ^k+1 )。

CYK 可以在不在 CNF 中的语法上正常工作，但运行时可能最终不会是字符串长度的三次方。CNF 要求只是强制 k = 2，因此保证了 O(n ³ ) 的整体运行时间。