数据压缩的历史原理及常用算法.doc

压缩，是为了减少存储空间而把数据转换成比原始格式更紧凑形式的过程。数据压缩的概念相当古老，可以追溯到发明了摩尔斯码的19世纪中期。 摩尔斯码的发明，是为了使电报员能够通过电报系统，利用一系列可听到的脉冲信号传递字母信息，从而实现文字消息的传输。摩尔斯码的发明者意识到，某些字母比其他字母使用地更频繁（例如E比X更常见），因此决定使用短的脉冲信号来表示常用字母，而使用较长的脉冲信号表示非常用字母。这个基本的压缩方案有效地改善了系统的整体效率，因为它使电报员在更短的时间内传输了更多的信息。 虽然现代的压缩流程比摩尔斯码要复杂地多，但是它们仍然使用着相同的基本原理，也就是我们这篇文章中将要讲述的内容。这些概念对我们如今的计算机世界高效运行至关重要——互联网上从本地与云端存储到数据流的一切东西都严重依赖压缩算法，离开了它很可能会变得非常低效。 压缩管道 下图展示了压缩方案的通用流程。原始的输入数据包含我们需要压缩或减小尺寸的符号序列。这些符号被压缩器编码，输出结果是编码过的数据。需要注意的是，虽然通常编码后的数据要比原始输入数据小，但是也有例外情况（我们后面会讲到）。 通常在之后的某个时间，编码后的数据会被输入到一个解压缩器，在这里数据被解码、重建，并以符号序列的形式输出原始数据。注意，本文我们会交替地使用“序列”和“串”来指一个符号序列集。 如果输出数据和输入数据始终完全相同，那么这个压缩方案被称为无损的，也称无损编码器。否则，它就是一个有损的压缩方案。 无损压缩方案通常被用来压缩文本，可执行程序，或者其他任何需要完全重建数据的地方。有损压缩方案在图像，音频，视频，或者其他为了提高压缩效率而可以接受某些程度信息丢失的场合很有用处。 数据模型 信息的定义是度量一个数据片段复杂度的量。一个数据集拥有越多的信息，它就越难被压缩。稀有的概念和信息的概念是相关的，因为稀有符号的出现比常见符号的出现提供了更多的信息。 例如，“日本的一次地震”的出现比“月球的一次地震”提供的信息号少，因为月球上的地震很不常见。我们可以预期，大多数压缩算法在压缩一个符号时，能够仔细地考虑它出现的频率或几率。 我们把压缩算法降低信息负载的有效性，称为它的效率。一个效率更高的压缩算法相比效率低的压缩算法，能够更多地降低特定数据集的大小。 概率模型 设计一个压缩方案的最重要一步，是为数据创建一个概率模型。这个模型允许我们测量数据的特征，达到有效的适应压缩算法的目的。为了使它更加清晰一些，让我们浏览一下建模过程的部分环节。 假设我们有一个字母表G，它由数据集中所有可能出现的字符组成。在我们的例子中，G包含4个字符：从A到D。 我们还有一个概率统计函数P，它定义了在输入数据串中，G中每个字符出现的概率。在输入数据串中，概率高的符号比概率低的符号更有可能出现。 在这个例子中，我们假定符号是独立同分布的。在源数据串中，一个符号的出现与其他任何符号没有相关性。 最小编码率 B是最常见的符号，出现的概率是40%；而C是最不常见的符号，它的出现概率只有10%。我们的目标是设计一个压缩方案，它对于常见符号使所需存储空间最小化，同时它支持使用更多的必要空间来存储不常见符号。这个折衷是压缩的基本原理，并且已经存在于几乎所有的压缩算法中。 有了字母表，我们可以小试身手，来定义一个基本的压缩方案。如果我们简单地把一个符号编码为8比特的ASCII值，那么我们的压缩效率，即编码率，将是8比特/符号。假定我们对只包含4个符号的字母表改进这个方案。如果我们为每个符号分配2个比特，我们仍然能够完全重建编码过的数据串，而只需要1/4的空间。 这时候，我们已经显著地提升了编码率（从8到2比特/符号），但是完全忽视了我们的概率模型。正如前面提到的，我们可以结合模型发明一个策略，通过对常见符号（B和D）使用更少的比特，对不常见符号（A和C）使用更多的比特，以提高编码效率。 这提出了一个在香农开创性论文中描述的重要观点——我们可以简单地基于符号（或事件）的概率，定义它的理论最小存储空间。我们如下定义一个符号的最小编码率： 例如，如果一个符号出现的概率是50%，那么它绝对最少需要一个字节来存储。 熵和冗余 更进一步，如果我们为字母表中的字符计算最小编码率的加权平均值，我们得到一个被称作香农熵的值，简单地称作模型的熵。熵被定义为给定模型的最小编码率。它建立在字母表和它的概率模型之上，如下描述。  正如你预料的一样，拥有更多罕见符号的模型，比拥有较少并且常见符号的模型的熵要高。更进一步，熵值更高的模型比熵值低的模型更难压缩。 在我们当前的例子中，我们模型的熵值是1.85比特/符号。编码率（2）和熵值（1.85）的差值被称作压缩方案的冗余。 在众多诸如加密和人工智能等不同的子领域，熵都是一个非常有用的话题