7th International Conference on Spoken Language Processing

September 16-20, 2002
Denver, Colorado, USA

Fast Hierarchical Grammar Optimization Algorithm Toward Time and Space Efficiency

Jing Zheng, Horacio Franco

SRI International, USA

We present an algorithm for hierarchical grammar optimization achieving time and space efficiency in Automatic Speech Recognition (ASR). The algorithm includes two parts: a selective grammar expansion algorithm and a graph reduction algorithm. The latter algorithm includes a node-merging procedure and an arc-sharing procedure. The algorithm is general so as to handle all types of grammar used in ASR; it is efficient so as to process dynamically generated grammars online; it is flexible and accepts several parameters controlling tradeoff between time and space complexity in favor of various different application requirements. We used this algorithm to optimize a grammar representing a class-based trigram language model, and obtained significant grammar size reduction and a 140% recognition speedup.

Full Paper

Bibliographic reference.  Zheng, Jing / Franco, Horacio (2002): "Fast hierarchical grammar optimization algorithm toward time and space efficiency", In ICSLP-2002, 393-396.