放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

维特比算法通俗理解

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

维特比算法是一个特殊但应用最广的动态规划算法,利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图(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实现》。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 维特比算法通俗理解

分享到:更多 ()

评论 4

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    请问理解维比特算法博主有什么好的资料推荐么

    fancybug2年前 (2015-08-07)回复
  2. #1

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

    Wenpeng_Yin3年前 (2014-06-05)回复
    • 多谢 ,基本明白

      zhaowei020145@163.com2年前 (2015-06-29)回复

我的开源项目

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