Compressing Trigram Language Models With Golomb Coding

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 199–207, Prague, June 2007. c⃝2007 Association for Computational Linguistics Compressing Trigram Language Models With Golomb Coding Ken Church Microsoft One Microsoft Way Redmond, WA, USA Ted Hart Microsoft One Microsoft Way Redmond, WA, USA Jianfeng Gao Microsoft One Microsoft Way Redmond, WA, USA {church,tedhar,jfgao}@microsoft.com Abstract Trigram language models are compressed using a Golomb coding method inspired by the original Unix spell program. Compression methods trade off space, time and accuracy (loss). The proposed HashTBO method optimizes space at the expense of time and accuracy. Trigram language models are normally considered memory hogs, but with HashTBO, it is possible to squeeze a trigram language model into a few megabytes or less. HashTBO made it possible to ship a trigram contextual speller in Microsoft Office 2007. 1 Introduction This paper will describe two methods of com- pressing trigram language models: HashTBO and ZipTBO. ZipTBO is a baseline compression me- thod that is commonly used in many applications such as the Microsoft IME (Input Method Editor) systems that convert Pinyin to Chinese and Kana to Japanese. Trigram language models have been so success- ful that they are beginning to be rolled out to appli- cations with millions and millions of users: speech recognition, handwriting recognition, spelling cor- rection, IME, machine translation and more. The EMNLP community should be excited to see their technology having so much influence and visibility with so many people. Walter Mossberg of the Wall Street Journal called out the contextual spel- ler (the blue squiggles) as one of the most notable features in Office 2007: There are other nice additions. In Word, Out- look and PowerPoint, there is now contextual spell checking, which points to a wrong word, even if the spelling is in the dictionary. For example, if you type “their” instead of “they're,” Office catches the mistake. It really works. 1 The use of contextual language models in spel- ling correction has been discussed elsewhere: (Church and Gale, 1991), (Mays et al, 1991), (Ku- kich, 1992) and (Golding and Schabes, 1996). This paper will focus on how to deploy such me- thods to millions and millions of users. Depending on the particular application and requirements, we need to make different tradeoffs among: 1. Space (for compressed language model), 2. Runtime (for n-gram lookup), and 3. Accuracy (losses for n-gram estimates). HashTBO optimizes space at the expense of the other two. We recommend HashTBO when space concerns dominate the other concerns; otherwise, use ZipTBO. There are many applications where space is ex- tremely tight, especially on cell phones. HashTBO was developed for contextual spelling in Microsoft Office 2007, where space was the key challenge. The contextual speller probably would not have shipped without HashTBO compression. We normally think of trigram language models as memory hogs, but with HashTBO, a few mega- bytes are more than enough to do interesting things with trigrams. Of course, more memory is always better, …

Content truncated to 500 words