Universal Compression of Infinite Alphabets with Applications to Language Modeling

University Of California-San Diego, La Jolla CA

Investigators

Abstract

In many data-compression applications the underlying distribution is not known. In these applications one typically assumes that the distribution belongs to a large class of natural distributions and tries to devise compression algorithms that perform well for all distributions in the class. For distributions over finite alphabets a lot is known. For example, it was shown that any stationary ergodic sequence can be compressed as well as when the distribution is known in advance. However in many real applications, such as text and image compression, the alphabet is large compared to the string length, often even infinite. Unfortunately, it has been shown that for large alphabets, universal compression cannot be achieved, and as the size of the alphabet grows, the redundancy, namely, the penalty for not knowing the distribution, increases to infinity. Recently, we took a different approach to the compression of strings over large alphabets. The description of any string, over any alphabet, can be decomposed into two parts: description of the dictionary, namely the symbols appearing in the string, and of their pattern, namely the order in which they appear. The descriptions of the pattern and the dictionary can be viewed as two separate problems. The pattern is related to the high-level structure of the string whereas the dictionary relates to the composition of the symbols. In many applications such as language modeling for speech recognition, the pattern is more significant. We have shown that patterns of strings drawn according to independent and identically distributed random variables can be compressed as if the distribution were known in advance. We now study extensions of this result that, if proven, will render it more powerful and practical. We are studying sequential compression algorithms that compress the sequence one symbol at a time, practical algorithms that can be performed using few operations per symbol, and extensions of these results to distributions with memory; such distributions model several practical applications. We are also trying to improve the upper and lower bounds on the best compression rate that can be achieved.