ITRW on Non-Linear Speech Processing (NOLISP 07) Paris, France May 22-25, 2007

Efficient Viterbi Algorithms for Lexical Tree Based Models

S. España-Boquera, M.J. Castro-Bleda, F. Zamora-Mart´ýnez, J. Gorbe-Moya

Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, Spain

In this paper we propose a family of Viterbi algorithms specialized for lexical tree based FSA and HMM acoustic models. Two algorithms to decode a tree lexicon with left-to-right models with or without skips and other algorithm which takes a directed acyclic graph as input and performs error correcting decoding are presented. They store the set of active states topologically sorted in contiguous memory queues. The number of basic operations needed to update each hypothesis is reduced and also more locality in memory is obtained reducing the expected number of cache misses and achieving a speed-up over other implementations.

Full Paper

Bibliographic reference.  España-Boquera, S. / Castro-Bleda, M.J. / Zamora-Mart´ýnez, F. / Gorbe-Moya, J. (2007): "Efficient Viterbi algorithms for lexical tree based models", In NOLISP-2007, 92-95.