An Efficient Language Model Using Double-Array Structures

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 222–232, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics An Efficient Language Model Using Double-Array Structures Makoto Yasuhara Toru Tanaka †Jun-ya Norimatsu Mikio Yamamoto Department of Computer Science University of Tsukuba, Japan †norimatsu@mibel.cs.tsukuba.ac.jp Abstract Ngram language models tend to increase in size with inflating the corpus size, and con- sume considerable resources. In this pa- per, we propose an efficient method for im- plementing ngram models based on double- array structures. First, we propose a method for representing backwards suffix trees using double-array structures and demonstrate its ef- ficiency. Next, we propose two optimization methods for improving the efficiency of data representation in the double-array structures. Embedding probabilities into unused spaces in double-array structures reduces the model size. Moreover, tuning the word IDs in the language model makes the model smaller and faster. We also show that our method can be used for building large language models using the division method. Lastly, we show that our method outperforms methods based on recent related works from the viewpoints of model size and query speed when both optimization methods are used. 1 Introduction Ngram language models (F. Jelinek, 1990) are widely used as probabilistic models of sentence in natural language processing. The wide use of the Internet has entailed a dramatic increase in size of the available corpora, which can be harnessed to ob- tain a significant improvement in model quality. In particular, Brants et al. (2007) have shown that the performance of statistical machine translation sys- tems is monotonically improved with the increas- ing size of training corpora for the language model. However, models using larger corpora also consume more resources. In recent years, many methods for improving the efficiency of language models have been proposed to tackle this problem (Pauls and Klein, 2011; Kenneth Heafield, 2011). Such meth- ods not only reduce the required memory size but also raise query speed. In this paper, we propose the double-array lan- guage model (DALM) which uses double-array structures (Aoe, 1989). Double-array structures are widely used in text processing, especially for Japanese. They are known to provide a compact representation of tries (Fredkin, 1960) and fast tran- sitions between trie nodes. The ability to store and manipulate tries efficiently is expected to increase the performance of language models (i.e., improving query speed and reducing the model size in terms of memory) because tries are one of the most common representations of data structures in language mod- els. We use double-array structures to implement a language model since we can utilize their speed and compactness when querying the model about an ngram. In order to utilize of double-array structures as language models, we modify them to be able to store probabilities and backoff weights. We also propose two optimization methods: embedding and ordering. These methods reduce model size and increase query speed. Embedding is an ef- ficient method for storing ngram probabilities and backoff weights, whereby we find …

Content truncated to 500 words