CKY真的需要CNF吗？

Question

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

标准版本的CYK仅在Chomsky normal form(CNF)~ Wikipedia中给出的无上下文语法中运行

但是,我也看到了一些CKY算法的例子,其中语法不在CNF中.克里斯托弗·曼宁使用的一个常见例子是"鱼人鱼缸"(参考: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 参考).为什么会出现差异？

Answer 1

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

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