Accession Number:

ADA460351

Title:

Efficient, High-Performance Algorithms for N-Best Search

Descriptive Note:

Corporate Author:

BBN SYSTEMS AND TECHNOLOGIES CORP CAMBRIDGE MA

Personal Author(s):

Report Date:

1990-01-01

Pagination or Media Count:

7.0

Abstract:

We present two efficient search algorithms for real-time spoken language systems. The first called the Word-Dependent N-Best algorithm is an improved algorithm for finding the top N sentence hypotheses. The new algorithm is shown to perform as well as the Exact Sentence-Dependent algorithm presented previously but with an order of magnitude less computation. The second algorithm is a fast match scheme for continuous speech recognition called the Forward-Backward Search. This algorithm, which is directly motivated by the Baum-Welch Forward-Backward training algorithm, has been shown to reduce the computation of a time-synchronous beam search by a factor of 40 with no additional search errors.

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE