Universal Compression of Infinite Alphabets with Applications to Language Modeling

在许多数据压缩应用程序中，底层分布是未知的。在这些应用中，人们通常假设分布属于一大类自然分布，并试图设计出对类中的所有分布都执行得很好的压缩算法。对于有限字母表上的分布，很多都是已知的。例如，证明了当分布已知时，任何平稳的遍历序列都可以被压缩。然而，在许多实际应用中，例如文本和图像压缩，与字符串长度相比，字母表很大，甚至是无限的。不幸的是，研究表明，对于大字母表，通用压缩是无法实现的，并且随着字母表大小的增长，冗余度，即不知道分布的惩罚，增加到无穷大。最近，我们对大字母表上的字符串压缩采取了不同的方法。对任何字母表上的任何字符串的描述可以分解为两个部分：词典的描述，即出现在字符串中的符号；以及它们的模式的描述，即它们出现的顺序。模式和词典的描述可以看作是两个独立的问题。模式与字符串的高级结构有关，而词典与符号的组成有关。在语音识别的语言建模等许多应用中，这种模式更加重要。我们已经证明，根据独立的同分布随机变量提取的字符串模式可以被压缩，就好像该分布是预先已知的一样。我们现在研究这一结果的扩展，如果得到证实，将使其更加强大和实用。我们正在研究一次一个符号地压缩序列的顺序压缩算法，每个符号可以使用较少操作来执行的实用算法，以及将这些结果扩展到有记忆的分布；这样的分布模拟了几个实际应用。我们还在努力提高可以达到的最佳压缩比的上限和下限。

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.