Bloom Filter and Lossy Dictionary Based Language Models
Abby Levenberg · 2007
Language models are probability distributions over a set of unilingual natural language text used in many natural language processing tasks such as statistical machine trans-lation, information retrieval, and speech processing. Since more well-formed training data means a better model and the increased availability of text via the Internet, the size of language modelling n-gram data sets have grown exponentially the past few years. The latest data sets available can no longer fit on a single computer. A recent investi-gation reported first known use of a probabilistic data structure to create a randomised language model capable of storing probability information for massive n-gram sets in a fraction of the space normally needed. We report and compare the properties of lossy language models using two probabilistic data structures: the Bloom filter and lossy dictionary. The Bloom filter has exceptional space requirements and only one-sided, false positive error returns but it is computationally slow in scale which is a potential drawback for a structure being queried millions of times per sentence. Lossy dictionar-ies have low space requirements and are very fast but with two-sided error that returns