正如其他動態(tài)規(guī)劃算法那樣（最小編輯距離算法、向前算法、Viterbi算法和Earley算法），CYK算法采用歸納法來填充概率數(shù)組。為了便于描寫，我們用Wij來表示從單詞i到單詞j的單詞符號串。根據(jù) Aho and Ullman(1972)，我們有：

* 基底  考慮長度為1的輸入符號串（也就是一個單詞Wi）。在Chomsky范式中，給定的非終極符號A展開為一個單詞Wi的概率必定只來自規(guī)則A→Wi，因為當(dāng)且僅當(dāng)A→Wi是一個產(chǎn)生式時，有)。

* 遞歸 對于長度大于1（length>1）的單詞符號串，當(dāng)且僅當(dāng)至少存在一個規(guī)則A→BC以及某個k,1≤k<j時，，使得B推導(dǎo)出Wij的開頭k個符號串，C推導(dǎo)出Wij的后面j-k個符號串。因為這些符號串都比原來的符號串Wij短，它們的概率已經(jīng)被存儲在矩陣π中，我們把這兩個片斷的概率相乘，計算出Wij的概率。當(dāng)然，這時Wij也可能會出現(xiàn)多個剖析，所以要選擇在所有可能的剖析中概率最大的剖析（也就是在所有可能的k值和所有可能的規(guī)則中進行選擇）。

圖1給出了這個概率CYK算法的偽代碼，也取自Collins(1999)和Aho and Ullman(1972)。

圖1概率CYK算法。對于給定的具有Chomsky范式規(guī)則num_rule的PCFG語法，該算法用于找出由單詞num_words組成的符號串的最大概率剖析。B是反向指針的數(shù)組，用于恢復(fù)最佳的剖析（Collins,1999；Aho and Ullman,1972）

責(zé)任編輯：admin