CKY真的需要CNF吗？
Does CKY really require CNF?
我读过很多地方 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 使用的一个常见示例是 "fish people fish tanks"（参考：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）。为什么会出现差异？
CYK 的运行时间取决于最长产生式规则的长度，因为该算法考虑了将字符串分解为 k 个部分以产生长度为 k 的所有可能方式。这意味着每个阶段的运行时间为 O(nk)，其中 k 是最长生产的长度。由于有 O(n) 个阶段，CYK 在最大生产长度 k 的文法上的运行时间为 O(nk+1).
CYK 将在 CNF 中没有的语法上正常工作，但运行时可能不会以字符串长度为立方体。 CNF 要求仅强制 k = 2，因此保证 O(n3) 整体运行时间。
我读过很多地方 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 使用的一个常见示例是 "fish people fish tanks"（参考：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）。为什么会出现差异？
CYK 的运行时间取决于最长产生式规则的长度，因为该算法考虑了将字符串分解为 k 个部分以产生长度为 k 的所有可能方式。这意味着每个阶段的运行时间为 O(nk)，其中 k 是最长生产的长度。由于有 O(n) 个阶段，CYK 在最大生产长度 k 的文法上的运行时间为 O(nk+1).
CYK 将在 CNF 中没有的语法上正常工作，但运行时可能不会以字符串长度为立方体。 CNF 要求仅强制 k = 2，因此保证 O(n3) 整体运行时间。