我需要检查一个字符串是否可以从给定的Chomsky正规形式的上下文无关文法中推导出来。我正在使用C++。
维基百科的CYK算法文章中有非常好的伪代码pseudocode,但我不能很好地理解它。
是否有人能够帮助我提供另一个CYK算法的伪代码,或者解释一下维基文章中的伪代码?
维基百科的CYK算法文章中有非常好的伪代码pseudocode,但我不能很好地理解它。
是否有人能够帮助我提供另一个CYK算法的伪代码,或者解释一下维基文章中的伪代码?
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(n2 N),其中n是输入字符串的长度(对于每个可能的开始和结束索引的组合),N是语法中非终结符的数量。这些观察结果表明,这个算法将受益于记忆化或动态规划,具体取决于您认为哪种方法更好。
CYK算法是当您记忆以上递归算法的结果时得到的结果,或者等价地说,当您将以上递归算法转换为动态规划问题时得到的结果。
有O(n2 N)种可能的递归调用。对于尝试的每个产生式,它需要O(n)的工作量。如果对于一个非终结符平均有P个产生式,这意味着总运行时间为O(n3 NP),对于固定的语法来说是O(n3)。