转载自 通俗理解维特比算法
本文假定读者有一定的隐马模型基础！或者大家可以参考这两篇文章。
隐马尔科夫模型-基本模型与三个基本问题和隐马尔科夫模型-前向算法
维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法
维特比算法之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。——《数学之美》
下面我通过一个例子来解释讲解一下维特比算法！
词性标注问题
首先介绍一下什么是词性标注问题，比如我们有一句已经分词好的句子。
dog chase mouse
那么我们就可以进行词性标注为：
其中nn为名词，vv为动词。通过上面例子，我们就很容易看出词性标注的任务。
那么我们来了一句话之后，比如我们的词性字典中有nn,vv,prp(代词)，我们怎么能够找到dog
chase mouse 所对应的词性标注呢，如果每一个单词有nn，vv，prp三种可能，那么将会有3*3*3=27种可能，我们如何去挑选呢？
如下图：
我们总共有27条路径，那么如何得到我们Dog chase mouse的最优路径呢？
我们至少可以遍历每一条路径，求出各自的概率值，然后挑选最大的即可，比如我们求第一条路径的时候，可以这么表示：
所求的路径对应如下图红色线条所示：
求第27条路径的时候，我们可以这么表示：
所求的路径对应如下图红色线条所示：
那么我们从上面可以知道，要求一个句子的最优词性标注，我们至少可以遍历所有的路径，然后挑选概率值最大的那条路径即可！！！
但是问题来了！
给定模型，求给定长度为T的观测序列(这里指的就是Dog Chase Mouse)的概率，直接计算法的思路是枚举所有的长度T（例子中是三个，Dog，Chase，Mouse总共三个单词）的状态序列，计算该状态序列与观测序列的联合概率（隐状态发射到观测），对所有的枚举项求和即可。
在状态种类为N(例子中就是三个，NN，VV,PRP)的情况下，一共有 N^T种排列组合，每种组合计算联合概率的计算量为T，总的复杂度为0(TN^T)，这并不可取。
于是维特比算法隆重登场了！！
维特比算法
好了，到现在为止，我们假定我们已经训练好了一个隐马尔可夫模型了（训练好的意思，也就是单词到词性的发射概率，词性与词性的转移概率都已经在训练数据中学习得到了），来了一句话，Dog Chase Mouse，我如何得到它的词性标注序列？
首先先上一个维特比算法流程图：
是不是非常晕，好吧，我下面争取按自己的话帮助大家理解一遍，再附上相应逻辑的代码！
解释如下：
实现代码如下：
