放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

维特比算法通俗理解

维特比算法说白了就是动态规划实现最短路径,只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法

维特比算法是一个特殊但应用最广的动态规划算法,利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图(Lattice )的最短路径问题而提出的。 它之所以重要,是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码,包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。——《数学之美》 ps 多处摘录此书,不再赘述。

篱笆网络有向图的特点是同一列节点有多个,并且和上一列节点交错地连接起来。同一列节点代表同一个时间点上不同的状态的并列,大概因为这种一列一列整齐的节点和交错的边很像篱笆而得名。

假设上图每一列分别有n1……nn个节点,如果不使用动态的话,那么计算复杂度就是O(n1*n2……nn)。

而维特比算法的精髓就是,既然知道到第i列所有节点Xi{j=123…}的最短路径,那么到第i+1列节点的最短路径就等于到第i列j个节点的最短路径+第i列j个节点到第i+1列各个节点的距离的最小值。

这是一句大白话,所谓中文伪码。

分析一下复杂度,假设整个篱笆有向图中每一列节点最多有D个(也就是图的宽度为D),并且图一共有N列,那么,每次计算至多计算D*D次(从i列的D个节点中挑一个计算到i+1列D个节点的距离)。至多计算N次。那么复杂度骤减为O(ND2),远远小于穷举O(DN)。

如果你需要一段开箱即用的维特比算法代码,请参考《通用维特比算法的Java实现》。

转载须注明:码农场 » 维特比算法通俗理解

分享到:更多 ()
  1. 这个帖子虽然短小,但是刻画了这个算法的精髓。 不过有一点与viterbi实际使用的时候不同在于: 使用的时候还考虑了Prob(hidden tag | observe). 也就是除了路径有长度外,路径上的节点也有本身来自于observe data的omission probability. 或者说每个每个节点不是等概率存在的。 多谢作者!

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机