Viterbi-Algorithm（维特比）算法简述
维特比算法是一个特殊但应用最广的动态规划算法。在求解隐马尔科夫、条件随机场的预测以及seq2seq模型概率计算等问题中均用到了该算法，即对状态序列进行预测时用到。利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图-篱笆网了（Lattice）的有向图最短路径问题而提出来的。它之所以重要，是因为凡是使用隐马尔科夫模型描述的问题都可以用它解码，包括当前的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
背景
假定用户（盲打时）输入的拼音时y1,y2,...,yNy1,y2,...,yN（虽然真正的输入法产品都是以词作为输入单位的，为了便于说明问题及简单起见，以字为单位来解释维特比算法），那么根据当前介绍的工具：
x1,x2,...,xN=ArgMaxx∈XP(x1,x2,...,xN|y1,y2,...,yN)=ArgMaxx∈X∏Ni=1P(yi|xi)P(xi|xi−1)x1,x2,...,xN=ArgMaxx∈XP(x1,x2,...,xN|y1,y2,...,yN)=ArgMaxx∈X∏i=1NP(yi|xi)P(xi|xi−1) (1)
输入的可见序列为y1,y2,...,yNy1,y2,...,yN。可以用下图描述这样一个过程：
这是一个相对简单的隐马尔科夫链，没用状态跳跃，也没有自环。P(xi|xi−1)P(xi|xi−1)个可能的值。如果把每个状态按照不同的值展开，就得到下面这个篱笆网络(Lattice):
在上图中，每个状态有3个或4个值，当然时间中它们可以有任意个值。
那么从第一个状态到最后一个状态的任何一条路径（Path）都可能产生我们观察到的输出序列Y。当然这些路径的可能性不一样，而我们要做的就是找到最可能的这条路径，并不是很难。但麻烦的是这样的路径组合数非常多，会让序列状态数的增长呈指数式增长。汉语中每个无声调的拼音对应13个左右的国标汉字，假定句子长为10个字，那么这个组合数为1310∼5×10141310∼5×1014这个计算量就相当的大了。因此，需要一个最好能和状态数目成正比的算法，而这个算法在1967年首次提出，即维特比算法。
主要内容
维特比算法基础
1.如果概率最大的路径P（或者说是最短路径）经过某个点，比如下图中的x22x22的最短路径R代替Q，便构成了一条比P更短的路径，这就和之前的假设矛盾了。
2.从S到E路径必定经过第i时刻的某个状态，假定第i时刻有k个状态，那么如果记录了从S到i个状态的所有k个节点（所有时刻的所有状态）的最短路径，最终的最短路径必经过其中的一条。这样，在任何时刻，只要考虑非常有限条候选路径即可。
3.结合以上两点，假定当我们从状态i进入到i+1时，从S到i上各个节点的最短路径已经找到，并且记录到这些节点上，那么在计算出从起点S到第i+1状态的某个结点的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这k个节点到xi+1,jxi+1,j的距离即可。
维特比算法
1.从点S触发，对于第一个状态x1x1表示的是状态1的节点，因为只有一步，所以这些都是S到它们各自的最短路径。
2.（算法的关键）对于第二个状态x2x2种可能性，我们要一一计算，然后找出最小值。即
d(S,x2i)=minI=1,n1d(S,x1j)+d(x1j,x2i)d(S,x2i)=minI=1,n1d(S,x1j)+d(x1j,x2i)
这样对于第二个状态的每个节点，需要进行n1n1次计算。
接下来，类似地按照上述方法从第二个状态走到第三个状态，一直走到最好一个状态，就得到了整个网格从头到尾的最短路径。每一步计算的复杂度都和相邻两个状态SiSi.
回到最初的问题中，计算量基本上是13×13×10=1690≈10313×13×10=1690≈103,这样就降低了很大的计算量。