问题标签 [cyk]

我对自然语言解析很感兴趣，并编写了一个 Brill Part of Speech Tagger，并希望通过将它与基于语法规则的 POS 标记器结合起来来增强它。有人知道任何地方的英语开源规则集文件吗？我对任何与 CYK (Cocke-Younger-Kasami) 算法相关的东西特别感兴趣，尤其是 C#。谢谢。

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

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

我必须检查是否可以从 Chomsky 范式的给定上下文中派生一个字符串。我正在使用 C++。

维基百科文章中有非常好的伪代码涵盖了 CYK 算法，但我不能很好地理解它。

有人会这么好心地帮助我，给我另一个 CYK 算法的伪代码，或者解释一下 wiki 文章中的那个吗？

所以我一直在阅读维基百科和许多 powerpoints/pdf 中的CYK 算法。

在维基百科中，有一部分我不是 100% 想要说的。你们能帮我分解一下吗？

真正让我困惑的部分是“如果 P[1,n,x] 中的任何一个为真（x 在集合 s 上迭代，其中 s 是 Rs 的所有索引），那么 S 是语言的成员，否则 S 不是成员语言"

如果它是真的，它是说存在的任何 n 和 x，那么它是一个成员吗？还是说字符串长度 n 和 x 如果它是真的那么它是一个成员？还是完全不同的东西？

X究竟是什么？

编辑：

谢谢大家，我确实学会了怎么做。希望我能将您的两个答案都作为选定的答案。

我偶然发现了许多不同的算法（CYK 和 Earley）来检查字符串是否是提供 CFG 的 CFL 的一部分。我正在寻找一些易于理解和实施的东西。我需要知道的是字符串是否在 CFG 中。CFG 通常以以下形式给出

该解决方案也应该接受 epsilon 转换，例如 S1-> a | e

有任何想法吗？

我想在 C/C++ 中实现CYK 算法，但在各种网站上提供的伪代码并没有回答如何有效地实现它。我写了一个版本，它使用了一些 stl 结构，比如 map 和 sets，但是速度很慢。我正在考虑通过仅使用二进制操作来改进我的实现，但我不知道如何用集合存储我的表。假设我们只有 8 个非终端符号和 26 个终端符号。我正在考虑使用无符号字符表（0-1 的 2^8 -> 8 个位置）来存储有关产品的信息，但我不知道如何存储它。

你能给我一些帮助或线索吗？

我正在阅读有关CYK 算法的内容，其中一部分伪代码我无法理解。整个伪代码是：

这些部分是我感到困惑的：

有人会对这些伪代码给出一些提示吗？

我写了一些实现CYK 算法的代码。我的代码有一些问题，但我不知道我做错了什么。我还询问了 CYK 算法的伪代码。

你能帮我处理这段代码吗：

感谢你们！

编辑：

调试代码一段时间后，我发现代码的一部分不起作用。

它是：</p>

我怀疑这个错误与我遇到的第一个问题有关。很可能是关于我对 AB 和 C 索引的解释方式。有人可以看看 findIndex 是否是查找索引的正确方法吗？

我目前正在尝试使用 epsilon 转换实现 CYK 。提供的算法如何处理 epsilon 转换？如果不是，您将如何实施它？（我正在使用 Java）

我正在尝试基于维基百科伪代码实现 CYK 算法。当我测试语法输入的字符串“ab”时：

S->AB

一个->一个

B->b

它给了我虚假，我认为它应该是真实的。我有一个名为 AllGrammar 的数组列表，其中包含所有规则。对于上面的示例，它将包含：

[0]：S->AB
[1]：A->a
[2]：B->b

对于示例 S->hello 和输入字符串 hello 它给了我应有的真实感。更复杂的测试（更多产品）给了我错误：S