向前算法有一種簡(jiǎn)單的變體，稱為Viterbi算法，這種算法可以讓我們同時(shí)考慮所有單詞，并且還能計(jì)算出最佳路徑。Viterbi這個(gè)術(shù)語(yǔ)在語(yǔ)音和語(yǔ)言處理中用得很普遍，但正如向前算法一樣，Viterbi算法確實(shí)也是經(jīng)典的動(dòng)態(tài)規(guī)劃算法的一種很標(biāo)準(zhǔn)的應(yīng)用，并且它看起來(lái)很像最小編輯距離算法。Viterbi算法首先由Vintsyuk（1968）應(yīng)用在語(yǔ)音識(shí)別中，并且這種算法也有像Kruskal（1983）所說(shuō)的那種“多重獨(dú)立發(fā)現(xiàn)和發(fā)表的引人注目的歷史”。Viterbi的名字在語(yǔ)音識(shí)別中使用得非常普遍，盡管人們也使用諸如動(dòng)態(tài)規(guī)劃對(duì)齊（Dynamic Programming Alignment,簡(jiǎn)稱DP對(duì)齊）、動(dòng)態(tài)時(shí)間偏移（Dynamic time warping）以及一遍解碼（one-pass decoding）等術(shù)語(yǔ)。Viterbi算法這個(gè)術(shù)語(yǔ)應(yīng)用于單個(gè)詞的加權(quán)自動(dòng)機(jī)和隱馬爾可夫模型的解碼，也應(yīng)用于連續(xù)語(yǔ)音等復(fù)雜問(wèn)題的解碼。在此僅簡(jiǎn)單介紹怎樣使用這種算法來(lái)發(fā)現(xiàn)通過(guò)構(gòu)成單詞網(wǎng)絡(luò)的最佳路徑，從而對(duì)于給定的單詞符號(hào)串觀察序列選出具有最佳概率的單詞。

我們?cè)谶@里介紹的這種Viterbi算法取一個(gè)單獨(dú)的加權(quán)自動(dòng)機(jī)和所觀察音子的集合O=（O?O?O?…Ot，）作為輸入，返回具有最佳概率的狀態(tài)序列q=（q?q?q?…qt）及其概率。我們可以這樣來(lái)建立一個(gè)單獨(dú)的加權(quán)自動(dòng)機(jī)，在這個(gè)加權(quán)自動(dòng)機(jī)中，用一個(gè)初始狀態(tài)和一個(gè)終結(jié)狀態(tài)把knee,need,new和neat這四個(gè)單詞的發(fā)音網(wǎng)絡(luò)并行地結(jié)合起來(lái)。圖1 說(shuō)明了這些網(wǎng)絡(luò)結(jié)合的情況。

圖1 把單詞need,neat,new和knee的發(fā)音網(wǎng)絡(luò)結(jié)合為一個(gè)單獨(dú)的加權(quán)自動(dòng)機(jī)。單詞的概率一般并不是該單詞的發(fā)音網(wǎng)絡(luò)的一部分，但在這里都加上了單詞的概率，這樣做主要是為了使我們對(duì)于Viterbi算法的解釋變得簡(jiǎn)單一些

圖2 說(shuō)明了這個(gè)Viterbi算法的偽代碼。正如在最小編輯距離算法和向前算法中那樣，Viterbi算法也建立了一個(gè)概率矩陣，矩陣的列（column）表示每個(gè)單詞的索引號(hào)t，矩陣的行表示狀態(tài)圖中的每個(gè)狀態(tài)。正如在向前算法中那樣，對(duì)于把這4個(gè)單詞結(jié)合起來(lái)的這個(gè)單獨(dú)的自動(dòng)機(jī)中的每個(gè)狀態(tài)qi，每個(gè)列都有一個(gè)單元。事實(shí)上，Viterbi算法中的代碼與向前算法中的代碼一樣，只不過(guò)是做了上述的兩個(gè)修改而已。向前算法把前面所有路徑的總和放到當(dāng)前單元中，而Viterbi算法則把前面所有路徑中最大的放到當(dāng)前單元中。

算法首先建立N+2或四個(gè)狀態(tài)列。第一列是初始的偽觀察值，第二列代表第一個(gè)觀察音子[n]，第三列代表[iy]，第四列代表最后的偽觀察值。開始時(shí)，在第一列中置開始狀態(tài)的概率為為1.0，置其他概率為0；讀者可以參看圖5.20。為便于閱讀，概率為0的單元都簡(jiǎn)單地用空白表示。

然后，正如在向前算法中那樣，我們轉(zhuǎn)移到下一個(gè)狀態(tài)。對(duì)于列0中的每個(gè)狀態(tài)，計(jì)算轉(zhuǎn)移到列1中的每個(gè)狀態(tài)的概率。取引導(dǎo)入當(dāng)前單元的所有路徑的延伸中最大的值為viterbi[t,j]的值。在時(shí)刻t-1從狀態(tài)i出發(fā)的一條路徑的延伸，只要把在向前算法中使用的三個(gè)因素相乘即可計(jì)算得到：