KenLM: Faster and Smaller Language Model Queries

Proceedings of the 6th Workshop on Statistical Machine Translation, pages 187–197, Edinburgh, Scotland, UK, July 30–31, 2011. c⃝2011 Association for Computational Linguistics KenLM: Faster and Smaller Language Model Queries Kenneth Heafield Carnegie Mellon University 5000 Forbes Ave Pittsburgh, PA 15213 USA heafield@cs.cmu.edu Abstract We present KenLM, a library that imple- ments two data structures for efficient lan- guage model queries, reducing both time and memory costs. The PROBING data structure uses linear probing hash tables and is de- signed for speed. Compared with the widely- used SRILM, our PROBING model is 2.4 times as fast while using 57% of the mem- ory. The TRIE data structure is a trie with bit-level packing, sorted records, interpola- tion search, and optional quantization aimed at lower memory consumption. TRIE simul- taneously uses less memory than the small- est lossless baseline and less CPU than the fastest baseline. Our code is open-source1, thread-safe, and integrated into the Moses, cdec, and Joshua translation systems. This paper describes the several performance tech- niques used and presents benchmarks against alternative implementations. 1 Introduction Language models are widely applied in natural lan- guage processing, and applications such as machine translation make very frequent queries. This pa- per presents methods to query N-gram language models, minimizing time and space costs. Queries take the form p(wn|wn−1 1 ) where wn 1 is an n-gram. Backoff-smoothed models estimate this probability based on the observed entry with longest matching 1http://kheafield.com/code/kenlm history wn f , returning p(wn|wn−1 1 ) = p(wn|wn−1 f ) f−1 � i=1 b(wn−1 i ). (1) where the probability p(wn|wn−1 f ) and backoff penalties b(wn−1 i ) are given by an already-estimated model. The problem is to store these two values for a large and sparse set of n-grams in a way that makes queries efficient. Many packages perform language model queries. Throughout this paper we compare with several packages: SRILM 1.5.12 (Stolcke, 2002) is a popular toolkit based on tries used in several decoders. IRSTLM 5.60.02 (Federico et al., 2008) is a sorted trie implementation designed for lower mem- ory consumption. MITLM 0.4 (Hsu and Glass, 2008) is mostly de- signed for accurate model estimation, but can also compute perplexity. RandLM 0.2 (Talbot and Osborne, 2007) stores large-scale models in less memory using ran- domized data structures. BerkeleyLM revision 152 (Pauls and Klein, 2011) implements tries based on hash tables and sorted arrays in Java with lossy quantization. Sheffield Guthrie and Hepple (2010) explore sev- eral randomized compression techniques, but did not release code. TPT Germann et al. (2009) describe tries with bet- ter locality properties, but did not release code. These packages are further described in Section 3. We substantially outperform all of them on query 187 speed and offer lower memory consumption than lossless alternatives. Performance improvements transfer to the Moses (Koehn et al., 2007), cdec (Dyer et al., 2010), and Joshua (Li et al., 2009) translation systems where our code has been inte- grated. Our open-source (LGPL) implementation is also available for download as …

Content truncated to 500 words