【基礎算法】維特比算法●Viterbi Algorithm

這個算法倒是不難，你要是在學條件随機場，恭喜你，來對地方了

維特比算法（英語：Viterbi algorithm）是一種動态規劃算法。它用于尋找最有可能産生觀測事件序列的維特比路徑——隐含狀态序列，特别是在馬爾可夫資訊源上下文和隐馬爾可夫模型中。

維特比算法利用動态規劃，可以解決任何一個圖中的最短路徑問題。維特比算法是針對一個特殊的圖——籬笆網絡（Lattice）的有向圖最短路徑的問題而提出的。它之是以重要，是因為凡是使用隐含馬爾可夫模型描述的問題都可以使用它來解碼，包括今天的數字通信、語音識别、機器翻譯、拼音轉漢字、分詞等。接下來我們用一個例子來說明（拼音轉漢字）：

目前圖上的所有狀态已經固定，其實在計算的時候，對于同一個拼音，就有很多的漢字，是以狀态并不是固定的，比如拼音：wo，則對應的漢字可能為：喔，窩，我，卧等漢字，拼音：shi，則對應的漢字又可能為：師，實，史，是等漢字。

假設每個拼音都有四個候選詞，則對于第一個拼音為第一個狀态，第一個狀态又有四種可能的漢字，用圖可以表示為：

• 如果機率最大的路徑

  P

  （或者說最短路徑）經過某個點，比如途中的X22，那麼這條路徑上的起始點

  S

  到X22的這段子路徑

  Q

  ，一定是

  S

  到X22之間的最短路徑。否則，用

  S

  到X22的最短路徑

  R

  替代

  Q

  ，便構成一條比

  P

  更短的路徑，這顯然是沖突的。證明了滿足最優性原理。
• 從

  S

  到

  E

  的路徑必定經過第

  i

  個時刻的某個狀态，假定第

  i

  個時刻有

  k

  個狀态，那麼如果記錄了從

  S

  到第

  i

  個狀态的所有

  k

  個節點的最短路徑，最終的最短路徑必經過其中一條，這樣，在任意時刻，隻要考慮非常有限的最短路即可。
• 結合以上兩點，假定當我們從狀态i進入狀态

  i+1

  時，從

  S

  到狀态

  i

  上各個節的最短路徑已經找到，并且記錄在這些節點上，那麼在計算從起點

  S

  到第

  i+1

  狀态的某個節點

  Xi+1

  的最短路徑時，隻要考慮從

  S

  到前一個狀态

  i

  所有的

  k

  個節點的最短路徑，以及從這個節點到

  Xi+1

  ，

  j

  的距離即可。

通俗了解：

1. 其實維特比算法算出了所有的路徑值（上圖共有路徑16×3條），但是算最短路徑組合方式有所變化，不同于把所有的組合方式都算出來這種指數型的算法，維特比算法采用一種動态的路徑規劃算法，即從起點開始，一層一層逐漸算出每一層的最短路徑，這樣每個節點隻保留了一條最短路徑，大大縮小了計算的複雜度。
2. 優化的地方在于，當同一層的每個節點隻保留一條最短路徑的時候，這樣就省去了通過該節點的非最短路徑與後續的節點計算的資源消耗。