An efficient A* stack decoder algorithm for continuous speech recognition with a stochastic language model

The stack decoder is an attractive algorithm for controlling the acoustic and language model matching in a continuous speech recognizer. The author previously described a near-optimal admissible Viterbi A * search algorithm for use with non-crossword acoustic models and no-grammar language models (1991). This algorithm is extended to include unigram language models, and a modified version of the algorithm which includes the full (forward) decoder, cross-word acoustic models and longer-span language models is described. The resultant algorithm is not admissible, but has been demonstrated to have a low probability of search error and to be very efficient