EFFICIENT WORD LATTICE PARSING ALGORITHM FOR CONTINUOUS SPECH RECOGNITION.

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