viterbi,维特比算法通俗理解 男娘i 2022-07-20 12:11 137阅读 0赞 维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法 > 维特比算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图（Lattice )的最短路径问题而提出的。 它之所以重要，是因为凡是使用隐含马尔可夫模型(Hidden Markov Model，HMM)描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。——《数学之美》 ps 多处摘录此书，不再赘述。 篱笆网络有向图的特点是同一列节点有多个，并且和上一列节点交错地连接起来。同一列节点代表同一个时间点上不同的状态的并列，大概因为这种一列一列整齐的节点和交错的边很像篱笆而得名。 ![6cbb8645gw1eeof28kfz7j20gv0cbgmx.jpg][] 假设上图每一列分别有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实现][Java]》。 [6cbb8645gw1eeof28kfz7j20gv0cbgmx.jpg]: /images/20220719/2ab1364c1c69417d8576da740abd9aa7.png [Java]: http://www.hankcs.com/nlp/general-java-implementation-of-the-viterbi-algorithm.html
还没有评论，来说两句吧...