前面在做自然語言處理時涉及到一些詞性标注的工作，一般會使用隐馬爾科夫模型（HMM）來實作詞性标注，而HMM模型的解碼實作算法一般就會使用Viterbi算法。
HMM模型有多種應用，這裡說的是其中一個常見應用，即根據觀察序列找到最可能的隐含狀态序列。最樸素的想法就是直接窮舉所有可能的隐含狀态序列，并計算出每個組合成的狀态序列的機率，機率最大的那個組合序列即是最可能的隐含狀态序列。舉個水藻和天氣的例子，窮舉出所有可能的隐含狀态序列的機率，如下，
P(dry,damp,soggy | sunny,sunny,sunny), P(dry,damp,soggy | sunny,sunny,cloudy), P(dry,damp,soggy | sunny,sunny,rainy), … . P(dry,damp,soggy | rainy,rainy,rainy)，最大值對應的序列即為最可能的隐含狀态序列。窮舉的路徑一共有3t條，可以看到随着序列還有狀态數的增加，計算量是非常大的。
上面的窮舉法需要的計算量很大，為減少複雜度引入Viterbi算法，Viterbi算法要解決的解碼問題就是多步且每步多重選擇的最優選擇的問題。根據下圖就能很清晰看到Viterbi的核心思想，随着時刻增加，每個節點都儲存了前一時刻所有節點到該節點的最優值的子路徑，如圖中紅色箭頭，目前時刻的某一節點可能的路徑為上一時刻所有節點到該節點的路徑，但我們隻保留其中一條最優路徑。依次計算完所有步後，最後通過回溯的方法得到整個過程的最優路徑。
下面用一個例子說明整個過程，假設有3中狀态，序列為t個時刻，p(a1)表示a1節點的值，p(b1)表示b1節點的值，同理其他的節點也一樣。對于不同時刻，狀态之間的轉換機率是不變的，是以p(aa)表示從a狀态轉移到a狀态的機率，不管是從1時刻到2時刻，還是從2時刻到3時刻，都是相同的。同理還有p(ab)、p(ac)、p(ba)…。
t+1時刻節點值的計算公式為pt+1(y)=pt(x)p(xy)其中x,y都屬于a,b,c一種狀态。
我們計算t=2時刻的p(a)的值，它可能從a1到a2、b1到a2或c1到a2，假如a1到a2這條路徑計算出來的p(a)最大，那麼就保留該路徑。同理分别計算p(b)和p(c)的最大值，保留b1到b2的路徑，b1到c2的路徑。接着計算t=3時刻的p(a)、p(b)和p(c)，最後到達t時刻，計算該時刻最大的p(a)、p(b)和p(c)，選擇出它們最大的值的節點，再根據保留的上一時刻的路徑依次往前回溯，就得到最優的序列。比如ct是最大的節點，那就是ct>ct−1>...>b3>c2>b1即最可能的序列為bcb…cc。
========廣告時間========
<a href="http://blog.csdn.net/wangyangzhizhou/article/details/74080321" target="_blank">為什麼寫《Tomcat核心設計剖析》</a>
=========================
歡迎關注：