4th International Conference on Spoken Language Processing
Philadelphia, PA, USA
In this paper, we introduce an efficient algorithm for the exhaustive search of N best sentence hypotheses in a word graph. The search procedure is based on a two-pass algorithm. In the first pass, a word graph is constructed with standard time-synchronous beam search. The actual extraction of N best word sequences from the word graph takes place during the second pass. With our implementation of a tree-organized N-Best list, the search is performed directly on the resulting word graph. Therefore, the parallel bookkeeping of N hypotheses at each processing step during the search is not necessary. It is important to point out that the proposed N-Best search algorithm produces an exact N-Best list as defined by the word graph structure. Possible errors can only result from pruning during the construction of the word graph. In a postprocessing step, the N candidates can be rescored with a more complex language model with highly reduced computational cost. This algorithm is also applied in speech understanding to select the most likely sentence hypothesis that satisfies some additional constraints.
Bibliographic reference. Tran, Bach-Hiep / Seide, Frank / Steinbiss, Volker (1996): "A word graph based n-best search in continuous speech recognition", In ICSLP-1996, 2127-2130.