Fourth European Conference on Speech Communication and Technology

Madrid, Spain
September 18-21, 1995

A Comparison of Two Exact Algorithms for Finding the N-Best Sentence Hypotheses in Continuous Speech Recognition

V. M. Jimenez (1), A. Marzal (2), J. Monné (3)

(1) Depto. Sist. Informaticos y Computation, Univ. Politecnica de Valencia, Spain
(2) Depto. de Informatica, Univ. Jaume I de Castello, Spain
(3) France Telecom, CNET LAA/TSS/RCP, Lannion, France

Two efficient and exact algorithms for computing the N best sentence hypotheses in continuous speech recognition are studied and compared. Both procedures are first stated as algorithmic solutions to the N shortest paths problem in graphs. The first algorithm is based on the general A* search strategy. The second one is based on a recursive procedure that enumerates shortest paths ending at a given node and is referred to as the Recursive Enumeration Algorithm.

Full Paper

Bibliographic reference.  Jimenez, V. M. / Marzal, A. / Monné, J. (1995): "A comparison of two exact algorithms for finding the n-best sentence hypotheses in continuous speech recognition", In EUROSPEECH-1995, 1071-1074.