nlp - CKY 真的需要 CNF 吗？

Question

我读过很多地方，CYK/CKY 算法要求语法采用乔姆斯基范式 (CNF)，例如

The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF) ~Wikipedia

然而，我也看到了一些 CKY 算法的例子，其中语法不在 CNF 中。 Christopher Manning 使用的一个常见示例是“鱼人鱼缸”(引用: PPT slide #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(nk)，其中 k 是最长生产的长度。由于有 O(n) 个阶段，CYK 在最大生产长度 k 的文法上的运行时间为 O(nk+1)。

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