一、概述
维特比算法是安德鲁.维特比(Andrew Viterbi)于1967年为解决通信领域中的解码问题而提出的,它同样广泛用于解决自然语言处理中的解码问题,隐马尔可夫模型的解码是其中典型的代表。...在实际问题中,节点数和层数往往是大量的,因而采取遍历所有的路径计算其距离进行比较的方式是不可行的。维特比算法正是通过动态规划的方式高效求得这条最优路径。...三、隐马尔可夫模型的解码
1.问题描述
隐马尔可夫模型(HMM)的解码问题指,给定模型和输出序列,如何找出最有可能产生这个输出的状态序列。...算法叙述
假设 P(st,j)P(st,j)表示从起始时刻到st,jst,j的最优路径的概率,Pre(st,j)Pre(st,j)表示从起始时刻到 st,jst,j的最优路径上前一个节点,则隐马尔可夫模型的维特比解码算法为...:
输入:隐马尔可夫模型 λ=(π,A,B)λ=(π,A,B)和观测 O=(o1,o2,...