First International Conference on Spoken Language Processing (ICSLP 90)

Kobe, Japan
November 18-22, 1990

A One-Pass Search Algorithm for Continuous Speech Recognition Directed by Context-Free Phrase Structure Grammar

Michio Okada

NTT Basic Research Laboratories, Musashino-shi, Tokyo, Japan

This paper presents an efficient parsing algorithm for integrating the search problems both in speech and language processing in general use for speech understanding systems. The parsing algorithm we propose is regarded as an extension of the finite-state-network-directed, one-pass search algorithm to the one directed by a context-free grammar with retention of the time-synchronous procedure. Our attempt is to embed an active chart parser in the one-pass search algorithm for top-down prediction. Extended formalization of the chart parser makes it possible to incrementally generate both new vertices and multiple lexical edges based on a data-driven beam search technique. Moreover, some extensions of the algorithm are discussed. This paper shows that the one-pass search algorithm proposed can be extended to a time-synchronous Viterbi-style beam search procedure that is guaranteed to find the N most likely sentences under the constraints of a unification-based phrase structure grammar.

Full Paper

Bibliographic reference.  Okada, Michio (1990): "A one-pass search algorithm for continuous speech recognition directed by context-free phrase structure grammar", In ICSLP-1990, 1229-1232.