正如其他动态规划算法那样（最小编辑距离算法、向前算法、Viterbi算法和Earley算法），CYK算法采用归纳法来填充概率数组。为了便于描写，我们用Wij来表示从单词i到单词j的单词符号串。根据 Aho and Ullman(1972)，我们有：

* 基底  考虑长度为1的输入符号串（也就是一个单词Wi）。在Chomsky范式中，给定的非终极符号A展开为一个单词Wi的概率必定只来自规则A→Wi，因为当且仅当A→Wi是一个产生式时，有)。

* 递归 对于长度大于1（length>1）的单词符号串，当且仅当至少存在一个规则A→BC以及某个k,1≤k<j时，，使得B推导出Wij的开头k个符号串，C推导出Wij的后面j-k个符号串。因为这些符号串都比原来的符号串Wij短，它们的概率已经被存储在矩阵π中，我们把这两个片断的概率相乘，计算出Wij的概率。当然，这时Wij也可能会出现多个剖析，所以要选择在所有可能的剖析中概率最大的剖析（也就是在所有可能的k值和所有可能的规则中进行选择）。

图1给出了这个概率CYK算法的伪代码，也取自Collins(1999)和Aho and Ullman(1972)。

图1概率CYK算法。对于给定的具有Chomsky范式规则num_rule的PCFG语法，该算法用于找出由单词num_words组成的符号串的最大概率剖析。B是反向指针的数组，用于恢复最佳的剖析（Collins,1999；Aho and Ullman,1972）

责任编辑：admin