First International Conference on Spoken Language Processing (ICSLP 90)

Kobe, Japan
November 18-22, 1990

A Tree-Trellis Based Fast Search for Finding the N Best Sentence Hypotheses in Continuous Speech Recognition

Frank K. Soong, Eng-Fong Huang

AT&T Bell Laboratories, Murray Hill, New Jersey, USA

In this paper a new, tree-trellis based fast search for finding the N best sentence hypotheses in continuous speech recognition is proposed. The search consists of a forward, time-synchronous, trellis search and a backward, time asynchronous, tree search. The well known Viterbi algorithm is used for finding the best hypothesis in a trellis and for recording the scores of all partial paths time synchronously. A backward A* algorithm based tree search is used to grow partial paths time asynchronously. Each partial path in the backward tree search is rank ordered in a stack by the corresponding full path score, which is computed by adding the partial path score with the best possible score of the remaining path obtained from the trellis path map. In each path growing cycle, the current best partial path, which is at the top of the stack, is extended by one arc (word). The new tree-trellis search is different from the traditional time synchronous Viterbi search in its ability for finding not just the best but the N best paths of different word content. The new search is also different from the A* algorithm, or the stack algorithm, in its capability for providing an exact, full path score estimate of any given partial (i.e., incomplete) path before its completion. When compared with the best candidate Viterbi search, the search complexities for finding the N best strings are rather low, i.e., only a fraction more computation is needed.

Full Paper

Bibliographic reference.  Soong, Frank K. / Huang, Eng-Fong (1990): "A tree-trellis based fast search for finding the n best sentence hypotheses in continuous speech recognition", In ICSLP-1990, 709-712.