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

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

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

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

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

責(zé)任編輯：admin