nlp - 这个 CYK 解析器结果是否正确？

Question

我正在尝试学习CYK 解析算法。

对于这组语法规则，结果表对于给定的两个句子是否正确？

S -> NP VP
VP -> VB NP
NP -> DT NN
PP -> IN NP
NP -> NP PP
NP -> NN
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the


['S']
[None, None]
[None, None, 'VP']
['NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog']


['S']
['NP', None]
['NP', None, 'VP']
['NP', None, None, 'NP']
[None, None, 'VP', None, None]
[None, None, 'VP', None, None, 'PP']
['NP', None, None, 'NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN', 'IN', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog', 'with', 'the', 'cat']

score 1 · Accepted Answer

你可以先尽量减少你的语法，因为有一些不必要的规则，而且这就是它的原因not in CNF。

更简洁地看一下，您碰巧None在第一个示例，第二行，第二列。实际上可以有一个S，但是由于 CYK 中的逻辑不能做进一步的优化，例如NP->NN. 从那里S -> NP VP提到的None单元格消失了。由于 CYK 无法执行这些，语法必须在 CNF 中。所以，基本上它大致就像您试图在 C++ 程序上应用 C 编译器（没有 C++ 库）。你很幸运，甚至在顶部获得了正确的结果。

话虽如此，我不会沉迷于你的第二个例子。

澄清一下，如果语法仅具有以下两种形式的CNF规则，则该语法是 in：

S -> AB
A -> a

NP -> NN很明显，CNF中没有类似的东西。

score 0 · Accepted Answer

虽然给定的文法不是 Chomosky 范式，但我们可以像下面这样轻松地将其转换为 CNF（例如，去掉非法产生式NP -> NN并用附加规则扩充文法）：

S -> NP VP
S -> NN VP
VP -> VB NP
VP -> VB NN
NP -> DT NN
PP -> IN NP
PP -> IN NN
NP -> NP PP
NP -> NN PP
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the

将语法修改为上述的，带有 CYK 算法的 DP 表（参考这里的实现，虽然它假设语法中的每个符号都是单个字符的长度，但可以很容易地扩展）将如下所示，对于第一句话：