AN AUGMENTED CHART DATA STRUCTURE WITH EFFICIENT WORD LATTICE PARSING SCHEME IN SPEECH RECOGNITION APPLICATIONS

This paper proposes an augmented chart data structure with an efficient word lattice parsing scheme in speech recognition. The augmented chart and the associated parsing algorithm can represent and very efficiently parse, without changing the fundamental principles of chart parsing, a lattice of lexically highly ambiguous word hypotheses in speech recognition. Every word lattice can be mapped to the augmented chart, with the ordering and link between the word hypotheses being well preserved in the augmented chart. A jump edge is defined in order to link edges representing word hypotheses physically separate, but connectable from a practical point of view. Preliminary experimental results show that with augmented chart parsing, all the possible constituents of the input word lattice can be constructed and no constituent needs to be built more than once. This significantly reduces computational complexity, especially when serious lexical ambiguity exists in the input word lattice as in the case of many speech recognition problems. This augmented chart parsing is thus very a useful and efficient approach to language processing problems in speech recognition. © 1991.