问题标签 [cyk]

所以我在一维数组中有一个语法，由形式给出

例子：

这被翻译成：

------

其他示例：

此外，array.number 以 [0, 9] 为界。

array.right 和 array.left 是区间 [A, Z] 中的文字。

我需要返回一个链接列表，其中包含应用于从一个名为 startString 的输入字符串获取到另一个名为 stopString 的输入字符串的所有规则（语法组件）。

如您所见，乔姆斯基范式中没有给出这个语法，我相信我无法将其翻译成 CNF，因为语法会改变，我无法返回程序请求的链表。

我应该如何进行？就像 Post-Scriptum 一样，语法中最多有 1000 条这样的规则，所以我想递归解析器可能不是要走的路。我之前问过，我被告知要阅读 CYK 算法，我这样做了。这是我作为一个项目遇到的问题。请记住，我刚开始这个级别的编程。但是，我确实具备所有基本知识。

获得CYK表后如何构建解析树？我不明白维基百科想说什么。
例子：

如何返回适用于从 A 到 BCED 的规则列表（或表格最长行的任何其他字母组合）？

I think they are the same concept, https://courses.engr.illinois.edu/cs498jh/Slides/Lecture10.pdf Probabilistic CYK algorithm is used the viterbi algorithm to parse, is my concept is correct?

我已经实现了 CYK 解析算法，它使用自下而上的方法来构建解析树。当它遍历算法时，最终解决方案的路径存储在反向指针中。从反向指针，我们构造树。这最后一步是我遇到的问题。

这是我用来存储树的数据结构：

以下是我构建树的方式，其中back存储了一个元组，其中split用于拆分树的索引是用于拆分树的索引，left_rule并且right_rule是由 int 表示的相应树的规则。如果到达叶节点，则没有元组，只有一个表示终端规则的 int。

问题是当功能完成构建树时，会添加额外的分支，即节点没有正确粘合在一起。

这是它的样子：

data树之间不应该有节点。

编辑：

问题不在于多了一个数据节点（上面的说法是错误的），而是在Lvl1之后，不是在Lvl2上添加新的分支，而是添加到L1.left/right和字段中。所以最终成为一棵树本身，并且没有被使用，因此。 R1.left/rightL1R1's dataL1/R1.dataL1.left/rightR1.left/rightNone

它应该如下所示：

这就是我所说的构建树：

我运行 CYK 算法，但是，我试图将其作为自上而下的设计（记忆）来做，有什么帮助吗？

我使用递归编写了以下代码来执行CYK 算法，以便语法G可以生成任何具有相同数量的a' 后跟任意数量b' 的单词，但由于某种原因它非常慢，不知道为什么？当我使用 s2 时，它可以工作，但如果我使用 s1 ，它是一个较长的字符串，它需要永远。谁能告诉我，因为我不知道瓶颈在哪里？

我已cProfile按照@wwii 的建议使用，结果如下：

当 s1 = "aaaaabbbbb" 当 s1 = "aaaaaaaaabbbbbbbbbb"

我们正在使用 CYK 表形成的概念在 Prolog 上产生这些结果。以下是 product_c(+Cell1, +Cell2, -Product) 的一些示例输出：

我试过使用 string_concat，但这给了我这样的结果：

我不确定如何解决这个问题。任何帮助深表感谢。

我目前正在开发一个 Prolog 程序，该程序将在获得一组产品后生成一个 CYK 解析表。但是，我在检查两行以查看它们是否相等时遇到了麻烦。这是我到目前为止所拥有的：

假设输入是：

我认为我的问题是我需要找到一种方法来创建一个等效于列表最大长度的变量并每次递减它，但是我遇到了将 sublist_check 的初始长度设置回其原始数字的错误。

任何输入/反馈都会很棒，非常感谢！

呃，

我正在尝试通过 ocaml 和 CYK 表来学习函数式编程，因此没有 List.mem 或任何命令式函数。我的目标是形成 2 个细胞的产物。

这是我目前拥有的：

预期的输出应该是这样的：

我的想法是制作一系列递归函数，基本上循环遍历列表，将每个字符串与另一个列表中的每个字符串放在一起。

我认为我的错误是我的附加方式，特别是在 append_func 中。我认为要问的更好的问题可能是如何创建字符串列表。

为了理解 cyk 算法，我研究了以下示例： https ://www.youtube.com/watch?v=VTH1k-xiswM&feature=youtu.be 。

结果是：

如何提取与每个解析相关的概率并提取最可能的解析树？