c++ - CYK 算法如何工作？

Question

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

有很好看pseudocode关于CYK算法的维基百科文章，但我不是很理解。

有人会非常好心地通过给我另一个 CYK 算法的伪代码来帮助我，或者解释一下维基文章中的伪代码吗？

Answer 1

CYK 算法将 Chomsky 范式的 CFG 作为输入。这意味着每个产生式要么具有以下形式

• S → a，对于某个终端a，或者
• S → AB，对于一些非终结符 A 和 B。

现在，假设你有一个字符串 w，你想看看是否可以从起始符号为 S 的文法中导出它。有两种选择:

1. 如果 w 是单个字符长，那么解析它的唯一方法是对某个字符 a 使用 S → a 形式的产生式。所以看看是否有任何单字符产生式与 a 匹配。
2. 如果 w 的长度超过一个字符，那么解析它的唯一方法是对一些非终结符 A 和 B 使用 S → AB 形式的产生式。这意味着我们需要将字符串 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;
}

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

1. 它进行了大量冗余的递归调用，但是
2. 没有那么多不同的可能递归调用。

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

CYK 算法是当你采用上述递归算法并记住结果时得到的，或者等效地，当你将上述递归算法转换为动态规划问题时得到的。

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