Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (4): 43-55.

• Original Articles • Previous Articles     Next Articles

Extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model

YE Fei1,2,*, WANG Yifei3   

  1. 1. School of Mathematics and Computer, Tongling University, Tongling 244000, Anhui, China; 2. Computational Experiment Center for Social Science, Nanjing University, Nanjing 210093, China; 3. Department of Mathematics, Shanghai University, Shanghai 200444, China
  • Online:2013-12-15 Published:2013-12-15

Abstract: Firstly, high-order hidden Markov model is transformed into an equivalent first-order vector-valued hidden Markov model by using Hadar's equivalent transformation method. Secondly, the Viterbi algorithm for the first-order vector-valued hidden Markov model is established according to the dynamic programming principle. Finally, the extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model is established by using the equivalence relation between high-order hidden Markov and the first-order vector-valued hidden Markov model. This study extends the related Viterbi algorithms discussed in almost all literatures of hidden Markov model, and then contributes to the algorithmic theory of high-order hidden Markov model.

Key words: high-order hidden Markov model, dynamic programming principle, Viterbi algorithm

CLC Number: