Generalization of the Viterbi algorithm

The Viterbi algorithm, derived using dynamic programming techniques, is a maximum a posteriori (MAP) decoding method which was developed in the electrical engineering literature to be used in the analysis of hidden Markov models (HMMs). Given a particular HMM, the original algorithm recovers the MAP state sequence underlying any observation sequence generated from that model. This paper introduces a generalization of the algorithm to recover, for arbitrary L, the top L most probable state sequences, with special reference to its use in the area of automatic speech recognition.