8th European Conference on Speech Communication and Technology

Geneva, Switzerland
September 1-4, 2003


Exploiting Order-Preserving Perfect Hashing to Speedup N-Gram Language Model Lookahead

Xiaolong Li, Yunxin Zhao

University of Missouri-Columbia, USA

Minimum Perfect Hashing (MPH) has recently been shown successful in reducing Language Model (LM) lookahead time in LVCSR decoding. In this paper we propose to exploit the order-preserving (OP) property of a string-key based MPH function to further reduce hashing operation and speed up LM lookahead. A subtree structure is proposed for LM lookahead and an order-preserving MPH is integrated into the structure design. Subtrees are generated on demand and stored in caches. Experiments were performed on Switchboard data. By using the proposed method of OP MPH and subtree cache structure for both trigrams and backoff bigrams, the LM lookahead time was reduced by a factor of 2.9 in comparison with the baseline case of using MPH alone.

Full Paper

Bibliographic reference.  Li, Xiaolong / Zhao, Yunxin (2003): "Exploiting order-preserving perfect hashing to speedup n-gram language model lookahead", In EUROSPEECH-2003, 2281-2284.