Compact, Efficient and Unlimited Capacity: Language Modeling with Compressed Suffix Trees

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2409–2418, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Compact, Efficient and Unlimited Capacity: Language Modeling with Compressed Suffix Trees Ehsan Shareghi,♭ Matthias Petri,♮ Gholamreza Haffari♭ and Trevor Cohn♮ ♭ Faculty of Information Technology, Monash University ♮ Computing and Information Systems, The University of Melbourne first.last@{monash.edu,unimelb.edu.au} Abstract Efficient methods for storing and querying language models are critical for scaling to large corpora and high Markov orders. In this paper we propose methods for mod- eling extremely large corpora without im- posing a Markov condition. At its core, our approach uses a succinct index – a compressed suffix tree – which provides near optimal compression while support- ing efficient search. We present algorithms for on-the-fly computation of probabilities under a Kneser-Ney language model. Our technique is exact and although slower than leading LM toolkits, it shows promis- ing scaling properties, which we demon- strate through ∞-order modeling over the full Wikipedia collection. 1 Introduction Language models (LMs) are critical components in many modern NLP systems, including machine translation (Koehn, 2010) and automatic speech recognition (Rabiner and Juang, 1993). The most widely used LMs are mgram models (Chen and Goodman, 1996), based on explicit storage of mgrams and their counts, which have proved highly accurate when trained on large datasets. To be useful, LMs need to be not only accurate but also fast and compact. Depending on the order and the training corpus size, a typical mgram LM may contain as many as several hundred billions of mgrams (Brants et al., 2007), raising challenges of efficient stor- age and retrieval. As always, there is a trade-off between accuracy, space, and time, with recent papers considering small but approximate lossy LMs (Chazelle et al., 2004; Talbot and Osborne, 2007; Guthrie and Hepple, 2010), or loss-less LMs backed by tries (Stolcke et al., 2011), or re- lated compressed structures (Germann et al., 2009; Heafield, 2011; Pauls and Klein, 2011; Sorensen and Allauzen, 2011; Watanabe et al., 2009). How- ever, none of these approaches scale well to very high-order m or very large corpora, due to their high memory and time requirements. An impor- tant exception is Kennington et al. (2012), who also propose a language model based on a suffix tree which scales well with m but poorly with the corpus size (requiring memory of about 20× the training corpus). In contrast, we1 make use of recent advances in compressed suffix trees (CSTs) (Sadakane, 2007) to build compact indices with much more mod- est memory requirements (≈ the size of the cor- pus). We present methods for extracting frequency and unique context count statistics for mgram queries from CSTs, and two algorithms for com- puting Kneser-Ney LM probabilities on the fly us- ing these statistics. The first method uses two CSTs (over the corpus and the reversed corpus), which allow for efficient computation of the num- ber of unique contexts to the left and right of an mgram, but …

Content truncated to 500 words