总结

本文将阐述通用源编码的基础知识。我们定义了极小极大遗憾数据压缩，并证明通用性的描述成本是包含所有源分布的相对熵球的信息半径。极小极大定理表明，该半径是由源分布给定的相关信道的信道容量。算术编码允许使用动态学习的源分布。最后，我们定义了单个序列的压缩，并通过一系列Lempel-Ziv解析算法实现。

在第五章中，我们介绍了寻找源的最短表示的问题，并证明了熵是任何唯一可解码表示的预期长度的根本下限。我们还证明了，如果我们知道源的概率分布，我们就可以使用哈夫曼算法为该分布构造最优（最小预期长度）编码。

然而，在许多实际情况中，源的概率分布可能是未知的，我们不能直接应用第五章的方法。相反，我们所知道的只是一类分布。一种可能的方法是等到我们看到所有数据后，根据数据估计分布，使用该分布构建最佳代码，然后回到开头并使用该代码压缩数据。这种两遍程序用于一些需要压缩数据量相当小的应用中。但在许多情况下，对数据进行两遍是不可行的，因此希望有一种一遍（或在线）算法来压缩数据，该算法“学习”数据的概率分布并使用它来压缩输入的符号。我们证明了存在这样的算法，它们对一类分布中的任何分布都表现良好。