7th International Conference on Spoken Language Processing

September 16-20, 2002
Denver, Colorado, USA

An Efficient Algorithm for the N-Best-Strings Problem

Mehryar Mohri, Michael Riley

AT&T Labs - Research, USA

We present an efficient algorithm for solving the n-best-strings problem in a weighted automaton. This problem arises commonly in speech recognition applications when a ranked list of unique recognizer hypotheses is desired. We believe this is the first n-best algorithm to remove redundant hypotheses before rather than after the n-best determination. We give a detailed description of the algorithm and demonstrate its correctness. We report experimental results showing its efficiency and practicality even for large n in a 40,000-word vocabulary North American Business News (NAB) task. In particular, we show that 1000-best generation in this task requires negligible added time over recognizer lattice generation.


Full Paper

Bibliographic reference.  Mohri, Mehryar / Riley, Michael (2002): "An efficient algorithm for the n-best-strings problem", In ICSLP-2002, 1313-1316.