CYK算法是如何工作的？

Question

CYK算法是如何工作的？

c++stringparsingcontext-free-grammarcyk

5

我需要检查一个字符串是否可以从给定的Chomsky正规形式的上下文无关文法中推导出来。我正在使用C++。

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

是否有人能够帮助我提供另一个CYK算法的伪代码，或者解释一下维基文章中的伪代码？

- neojb1989

1

尽管我很喜欢维基百科，但它并不总是最易读的来源。对于初学者的技术信息，通常最好寻找其他来源。你在谷歌上搜索过CYK的其他位置吗？ - RonaldBarzell

我已经在谷歌上搜索过了，但要么是我找到了一些我无法理解的实际代码，要么是我找到了手动执行该操作的算法，但我甚至开始将其转换为代码都很困难。 - neojb1989

是的，很多链接都不太易读。如果您想熟悉它，可以在此处查看演示：http://www.diotavelli.net/people/void/demos/cky.html。此外，这里有一系列幻灯片，似乎更易读：http://www.cs.ucdavis.edu/~rogaway/classes/120/winter12/CYK.pdf。最后，这是一个C++实现：http://nitishkr.wordpress.com/2011/03/29/cyk-algorithm-implementation/。 - RonaldBarzell

很遗憾听到这个消息...我想我理解CYK算法，问题在于它可能需要一些其他术语的基础来解释，这些术语不一定是计算机科学相关的。如果你想在聊天中讨论这个问题，也许我可以帮忙，但这并不适合作为一个答案，因为它需要来回交流。 - RonaldBarzell

太好了！我很高兴听到这个消息。 - RonaldBarzell

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

CYK算法以Chomsky正规形式的CFG作为输入。这意味着每个产生式都具有以下形式之一：

- S → a，其中a是某个终端符号 - S → AB，其中A和B是某些非终端符号。

现在，想象一下你有一个字符串w，你想知道是否可以从起始符号为S的语法中推导出它。有两种选择：

1. 如果w只有一个字符长，则解析它的唯一方法是使用形式为S → a的产生式，其中a是某个字符。因此，看看是否有任何单字符产生式与a匹配。 2. 如果w的长度超过一个字符，则解析它的唯一方法是使用形式为S → AB的产生式，其中A和B是某些非终端符号。这意味着我们需要将字符串w分成两个部分x和y，其中A派生x，B派生y。一种方法是尝试将w分成两个部分并查看它们中的任何一个是否有效。

请注意，这里的选项（2）最终变成了一个递归解析问题：要查看是否可以从S导出w，请查看是否可以从A导出x，从B导出y。

有了这个见解，以下是递归函数的伪代码，您可以使用它来查看非终结符S是否能够派生字符串w：

bool canDerive(nonterminal S, string w) {
    return canDeriveRec(S, w, 0, w.size());
}

/* Can you derive the substring [start, end) of w from S? */
bool canDeriveRec(nonterminal S, string w, int start, int end) {
    /* Base case: Single characters */
    if (end - start == 1) {
        return whether there is a production S -> a, where a = w[start];
    }

    /* Recursive case: Try all possible splits */
    for (each production S -> AB) {
        for (int mid = start + 1; mid < end; mid++) {
            if (canDeriveRec(A, w, start, mid) &&
                canDeriveRec(B, w, mid, end)) {
                return true;
            }
        }
    }
    return false;
}

这个算法可以正常工作，但是如果你绘制递归的形状，你会发现：

它会进行大量冗余的递归调用，但是
并不会有那么多不同的可能递归调用。

事实上，不同可能的调用次数为O(n² N)，其中n是输入字符串的长度（对于每个可能的开始和结束索引的组合），N是语法中非终结符的数量。这些观察结果表明，这个算法将受益于记忆化或动态规划，具体取决于您认为哪种方法更好。

CYK算法是当您记忆以上递归算法的结果时得到的结果，或者等价地说，当您将以上递归算法转换为动态规划问题时得到的结果。

有O(n² N)种可能的递归调用。对于尝试的每个产生式，它需要O(n)的工作量。如果对于一个非终结符平均有P个产生式，这意味着总运行时间为O(n³ NP)，对于固定的语法来说是O(n³)。