问题标签 [cyk]

在 Python 中，我有一个列表输入，如下所示 -

这是以下 CYK 算法的结果 -

我要匹配的字符串是“Ron saw the mouse”

我想像这样关联输出-

我不确定应该如何构造算法，尤其是使用可能包含多个输出的模棱两可的算法。我应该如何构建代码？有什么建议有/没有递归应该是更好的方法吗？

更新 - -

在使用输入列表添加额外的父节点和子节点位置值后，我设法获得了一个精确的解析树。但是我的问题并没有用模棱两可的句子解决。

我正在尝试实现wikipedia提供的 CYK 伪代码。我输入的例句应该输出真，但输出假。考虑到提供的示例从 1 开始，我认为我在索引方面遇到了问题。

代码：

我正在尝试根据Wikipedia 的伪代码在 Ruby 中实现 CYK 算法。我的实现无法生成正确的解析表。在下面给出的方法中，grammar是我自己的语法类的成员。这是代码：

我用这个简单的例子测试了它：

解析表tbl如下：

问题肯定出在算法的第二部分——长度大于 1 的子串。第一层 ( tbl[0]) 包含正确的值。

非常感谢帮助。

我写了一个 CYK 解析器，我用它来解析像 (1+2)/3-4^5 这样的数学表达式。我还编写了一个代码，使用下面的语法从 CYK 算法提供的表（左三角矩阵）构建解析树。我的问题是，是否可以直接从我的解析树构建表达式树（哪些内部节点是操作，叶子是数字）？我用来解析的语法（CYK需要乔姆斯基范式）如下：

我正在尝试在概率 CFG 上使用 CYK 算法构建解析树。这是我的概率 CFG

这是 CYK 构建解析树的代码：

但是，介于两者之间的概率计算不正确，导致以下输出以及错误：

我遵循的算法：

有人可以帮我完成这项工作吗？我已经正确地遵循了上述算法，为什么它会失败？我已经尽力了，但仍然无法弄清楚如何解决这个问题。递归似乎存在问题，因为它返回 S -> NP VP 的 0 概率。

我试图弄清楚如何将 CYK 表转换为解析树的机制。

我的 CFG 语法如下：

测试字符串是0pm1sm0p1

生成的表格是：

现在，假设我将表中的变量更改为规则，例如 fe S,E->S -> EA等E -> EA。

通过查看表格，我无法弄清楚如何构建解析树，因为我可以看到测试字符串中只有 2 个p，但是唯一的规则生成p是A -> PT我在表格3 A -> PT条目中看到的已经无法给出正确的解析树，因为会有太多p，E-> EA 规则也是如此，因为表中的规则太多了。我想自下而上地构建树，但是，我遇到了多个规则的问题。我错过了什么吗？我需要从表格中过滤掉一些规则吗？