An O(N√E¯) Viterbi algorithm

In continuous speech recognition, a significant amount of time is used every frame to evaluate interword transitions. In fact, if N is the size of the vocabulary and each word transitions on average to E¯ other words then O(NE¯) operations are required. Similarly when evaluating a partially connected HMM, the Viterbi algorithm requires O(NE¯) operations. This paper presents the first algorithm to break the O(NE¯) complexity requirement. The new algorithm has an average complexity of O(N√E¯). An algorithm was previously presented by the author for the special case of fully connected models, however, the new algorithm is general. It speeds up evaluations of both partial and fully connected HMM and language models. Unlike pruning, this paper does not use any heuristics which may sacrifice optimality, but fundamentally improves the basic evaluation of the time synchronous Viterbi algorithm