Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 262–272, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval David Guthrie Computer Science Department University of Sheffield D.Guthrie@dcs.shef.ac.uk Mark Hepple Computer Science Department University of Sheffield M.Hepple@dcs.shef.ac.uk Abstract We present three novel methods of compactly storing very large n-gram language models. These methods use substantially less space than all known approaches and allow n-gram probabilities or counts to be retrieved in con- stant time, at speeds comparable to modern language modeling toolkits. Our basic ap- proach generates an explicit minimal perfect hash function, that maps all n-grams in a model to distinct integers to enable storage of associated values. Extensions of this approach exploit distributional characteristics of n-gram data to reduce storage costs, including variable length coding of values and the use of tiered structures that partition the data for more effi- cient storage. We apply our approach to stor- ing the full Google Web1T n-gram set and all 1-to-5 grams of the Gigaword newswire cor- pus. For the 1.5 billion n-grams of Gigaword, for example, we can store full count informa- tion at a cost of 1.66 bytes per n-gram (around 30% of the cost when using the current state- of-the-art approach), or quantized counts for 1.41 bytes per n-gram. For applications that are tolerant of a certain class of relatively in- nocuous errors (where unseen n-grams may be accepted as rare n-grams), we can reduce the latter cost to below 1 byte per n-gram. 1 Introduction The availability of very large text collections, such as the Gigaword corpus of newswire (Graff, 2003), and the Google Web1T 1-5gram corpus (Brants and Franz, 2006), have made it possible to build mod- els incorporating counts of billions of n-grams. The storage of these language models, however, presents serious problems, given both their size and the need to provide rapid access. A prevalent approach for language model storage is the use of compact trie structures, but these structures do not scale well and require space proportional to both to the number of n-grams and the vocabulary size. Recent ad- vances (Talbot and Brants, 2008; Talbot and Os- borne, 2007b) involve the development of Bloom fil- ter based models, which allow a considerable reduc- tion in the space required to store a model, at the cost of allowing some limited extent of false positives when the model is queried with previously unseen n-grams. The aim is to achieve sufficiently compact representation that even very large language models can be stored totally within memory, avoiding the latencies of disk access. These Bloom filter based models exploit the idea that it is not actually neces- sary to store the n-grams of the model, as long as, when queried with an n-gram, the model returns the correct count or probability for it. These techniques allow the storage of language models that no longer depend on the size …

Content truncated to 500 words