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

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

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

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

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

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