CYK算法是如何工作的？

Question

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

维基百科文章上有很好的伪代码，介绍了 CYK 算法，但我不太明白。

有人会通过给我另一个 CYK 算法的伪代码来帮助我，或者在 wiki 文章中解释那个？

Answer 1

CYK 算法将乔姆斯基范式的 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 ³ )。