An efficient word lattice parsing algorithm for continuous speech recognition

An efficient word lattice parsing algorithm is introduced for continuous speech recognition. A word lattice is a set of hypothesized words with different starting and ending positions in the input signal. Parsing a word lattice involves much more search than typed natural language parsing, and a very efficient algorithm is desired. The algorithm is based on the context-free parsing algorithm recently developed by the author. Our algorithm (1) is fast due to utilization of LR parsing tables, (2) produces all possible parses in an efficient representation, and (3) processes an input word lattice in a strict left-to-right manner, which may allow the algorithm to pipeline with lower level processes (i.e. word hypothesizers). The algorithm has been implemented in the continuous speech recognition project at Carnegie-Mellon University, and is being tested against real speech data.