An efficient algorithm for the TV-best-strings problem

Mehryar Mohri, Michael Riley

Research output: Contribution to conferencePaperpeer-review

Abstract

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.

Original languageEnglish (US)
Pages1313-1316
Number of pages4
StatePublished - 2002
Event7th International Conference on Spoken Language Processing, ICSLP 2002 - Denver, United States
Duration: Sep 16 2002Sep 20 2002

Other

Other7th International Conference on Spoken Language Processing, ICSLP 2002
CountryUnited States
CityDenver
Period9/16/029/20/02

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language

Fingerprint Dive into the research topics of 'An efficient algorithm for the TV-best-strings problem'. Together they form a unique fingerprint.

Cite this