问题标签 [cyk]

我已经实现了 CYK 算法来检查具有给定语法的输入字符串。
如果我有以下语法

如果我检查 string ab，算法会说它是语法。但如果我有如下语法，

如果我通过 string aih，算法会说它不在语法中。但是正如您所看到aih的，显然会创建非终结符ABC并且它们相等S。所以我对此感到困惑。如果我错了，请指出我..提前谢谢。

编辑：上面显示了算法如何构造单词。在 (1,3) 中为空。所以它不在语法中。是我语法有问题吗？

我开始使用 Erlang，作为练习，我尝试实现CYK 算法。

主要代码（cyk.erl）：

语法文件 (grammar.txt)

可以从 erlang shell 测试代码

这个例子的代码似乎工作得很好，但我一直在寻找改进它的方法（让它更符合 erlang 风格），特别是让处理分布在多个进程/节点上。

我猜每个步骤的所有 process_subtree 执行都可以同时完成，但我真的不知道如何。

任何建议将不胜感激！

我使用CYK算法（已经在 J​​ava 中实现）来查看是否根据特定语法识别字符串。现在我需要为字符串生成一个解析树，是一种从我使用CYK算法时使用的矩阵生成树的方法吗？

我正在为上下文无关语法实现 CYK 解析算法。

然而，困难的部分是我需要在 XSL（一种函数式语言）中执行此操作，而不是我非常熟悉的更程序化的语言 - 例如 Java。

我在 Java 中有一个算法的工作实现，但我想将它转换为 Xsl

任何帮助将不胜感激。提前致谢。

我目前正在从事一个涉及 NLP 的项目。我已经实现了 Jurafsky 和 ​​Martin 中给出的 CKY 标识符（第 450 页的算法）。这样生成的表实际上将非终结符存储在表中（而不是通常的布尔值）。但是，我得到的唯一问题是检索解析树。

这是我的 CKY 标识符的作用的说明：

这是我的语法

这是算法：

这就是我的解析表在填充后的样子：

现在我知道由于 S 位于 [0,5] 中，字符串已被解析，并且对于 k = 1（根据 Martin 和 Jurafsky 中给出的算法），我们有 S -> table[0][2 ] 表[2][5] 即 S -> NP VP

我得到的唯一问题是我已经能够检索使用的规则，但是它们的格式混乱，即不是基于它们在解析树中的出现。有人可以建议一种算法来检索正确的解析树吗？

谢谢你。

我一直在尝试根据维基百科给出的伪代码来实现 CYK 算法，但是我似乎无法做到正确，也不知道代码有什么问题。我最好的猜测是我的索引是错误的，因为伪代码不使用数组索引。

这是我正在测试的语法：
/ --> U1V1 | U2V2 | V1V1 | V2V2 | 一个 | b
S --> U1V1 | U2V2 | V1V1 | V2V2 | 一个 | b
V1 --> a
V2 --> b
U1 --> V1S
U2 -- > V2S
这个语法接受回文，所以应该接受“baab”，但是它不被接受为语法的一部分

下面是代码：

辅助函数只返回变量的所有给定产生式及其在变量向量中的索引 {/,S,V1,V2,U1,U2}

此文法（在 CNF 中）来自转换后的文法 S>aSa|bSb|aa|bb|a|b（不在 CNF 中）

任何帮助将不胜感激

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

CYK 的标准版本仅适用于以乔姆斯基范式 (CNF) 给出的上下文无关文法 ~维基百科

但是，我还看到了许多 CKY 算法的示例，其中语法不在 CNF 中。Christopher Manning 使用的一个常见示例是“鱼人鱼缸”（参考：PPT 幻灯片 #19），其中包含一元规则：

我还看到了演示 CKY 的其他示例，这些示例在生产的 RHS 中使用了三个非终端（例如VP -> Verb NP NP reference）。为什么会出现差异？

注意：对于这个问题，我不能使用除 io 和 sys 之外的任何导入

对于 NLP 作业，我必须创建一个程序，将语法文件和话语文件作为系统参数，我已经完成了。

问题是，我对如何实现将字符串输出为扩展乔姆斯基范式（eCNF）的确定性 CYK 算法感到非常困惑。

我尝试实现一个 Node 类，但在实现正确的形式时遇到了很多麻烦。我还发现了 CYK 算法的概率版本的实现，但它们让我更加困惑。我不想要任何概率分数。

我尝试成功创建一个矩阵 P[i][j]，但它并没有呈现为三角形，当我用我的话语行中的单词填充它时，它只包含了该行中的最后一个单词。

这是我试图遵循的伪代码：

以下是两个示例输入文件：

语法

话语

到目前为止，我的程序可以判断什么时候可以解析一个句子，什么时候不能。现在我需要获取可以解析的话语并解析它们。

输出应如下所示：

这是我的程序，删除了所有导致错误的代码：

我了解该算法的原理，但是在没有 NLTK 的情况下尝试用 Python 编写它是很棘手的。

对于我正在创建的方法，我想接收在行尾找到的单词，然后我想将找到的单词附加到它的左侧（在行的开头直到一个空格字符）到一个数组。

到目前为止，这是我的代码：

到目前为止，输出的数组一直都是空的。不知道我的逻辑哪里错了。

语法文件中的一行如下所示，例如：

副总裁 -> V NP

NP -> N

副总裁 -> V PP

我想将 -> 右侧的部分作为输入，并将左侧附加到一个数组中，以便在程序的其他部分中使用。

自从我开始尝试找到解决此问题的方法以来已经 1 周了，我最终阅读了有关 CYK 算法的内容，但我不明白它对我有什么帮助。

所以我有一个特定的字符串作为开始，我们称之为startString。
我有一个特定的字符串，我想通过应用稍后解释的规则来获得它，称为stopString。

------------

现在让我们举个例子：

此示例的规则如下：

该程序将采用上述输入并输出从 startString 到 stopString 的最小转换列表，可能如下：

------------

我的问题是：CYK 在这里如何帮助我？如何使用 CYK 从“A”获取“2403”？这个问题有没有更简单的解决方案？