数据压缩领域的最前沿都是关于如何改变熵的。事实上，整个数据压缩科学界的人士都认为熵是互联网上的一大“谎言”。

真相是，实际上这句话可以从“理论”上来理解。，通过利用真实数据的两个性质，我们完全有可能将数据压缩得比熵定义的还要小。按照香农对熵的定义，他只考虑了符号出现的概率，完全没有考虑符号之间的排序。而对真实数据集来说，排序是一项基本的信息，符号之间的关系同样如此。

例如，排好序的[1,2,3,4] 和没有排序的[4,1,2,3] 这两个集合，按照香农的定义，两者的熵相同，但是凭直觉我们就能发现，其中的一个集合包含了额外的排序信息。我们再来看一个元素为字母的例子，[Q,U,A,R,K] 和[K,R,U,Q,A] 这两个集合有相同的熵，但[Q,U,A,R,K] 这个集合表示的是英语中一个有意义的单词，而且字母的出现也有一定的规则，比如字母Q后面通常会跟着字母U。

下面举几个例子来看一下如何利用数据的性质来突破熵。（请撸起袖子，我们将要压缩一些数据！）

突破熵的关键在于，通过利用数据集的结构信息将其转换为一种新的表示形式，而这种新表示形式的熵比源信息的熵小。

元素递增的集合[0,1,2,3,4,5,6,7] 称为集合。

现在，打乱集合中元素的顺序，得到集合。根据信息论的观点，这两个集合具有如下独特的性质：


•所有的符号都等可能地出现，并且没有重复的符号；

•集合和集合的熵相等，都等于 3。


因此，根据香农的定义，每个符号都需要用3个二进制位来编码，而每个集合则需要24个二进制位。然而最终的结果是，我们很容易就能突破熵的限制，用更少的二进制位对集合进行编码，具体方法如下。

集合实际上是数的一个线性递增序列。因此，无须对其中的每个数都进行编码，而是可以对整个数据流进行转换，将各个数编码为其与前一个数的差。所以，编码后的会是这样：

这一数据流的熵，结果还不错吧？

这样的转换一般称为增量编码（delta coding），也就是将一系列的数转换为其与上一个数的差后再编码如果这里不太理解，不用担心，第8章会深入讨论这一编码方法。。

下面来讨论集合。由于中的数并不是线性递增的，因此增量编码的方法不会起作用，这样操作之后我们会得到集合[1,–1,2,2,–1,2,2,–1]，其熵为2，乍一看这个结果还不错。然而，如果真的这样做，那么首先需要用16个二进制位将多重集合多重集合是指同一个元素可以多次出现的集合。编码为[01,00,10,10,00,10,10,00]。此外，还需要告诉解码器编码“00”表示的是符号–1，这就需要额外的空间来存储。因此，即使能节省空间，也节省不了多少。（实际上，对某些集合来说，与直接对数据进行编码相比，增量编码所需要的二进制位甚至要更多。）

顺序很重要

根据熵的定义，符号之间的顺序无关紧要，但增量编码证明事实并非如此。如果相邻的值之间高度相关，那么用增量编码的方法可以转换数据，使其熵变得更小。

假定你遇到了字符串“TOBEORNOTTOBEORTOBEORNOT”，它包含了不同符号的集合[O,T,B,E,R,N]，而熵。

任何人看一眼这个字符串，都能意识到其中含有重复的单词。因此，如果不是将单个的字母当成符号，而是把单词当成符号，情况又会如何呢？这样一来，我们有单词集合[TO,BE,OR,NOT]，其熵。

因此，对这样的数据流来说，用单词作为符号，得到的熵值会更小。那么，采用这种符号分组的方法，我们能走多远呢？再观察这个字符串，我们发现“TOBEORNOT”这个词组出现过多次，那么能否将词组当成一个符号呢？

下面试着计算一下：

，其熵当然，虽然从理论上来说这两种分组方法的结果不同，但实际上对这个小数据集来说，两种方法一样，即每个符号都需要2个二进制位，不过这里主要关心的是超越香农。

显然这个熵值更小！值得一提的是，关于符号分组，一般有最佳的分组方法，而且有一个专门的数据转换研究领域帮我们找出最佳的分组方法，通常被称为“字典编码器”（Dictionary Encoders），第7章会讨论这个话题。

字符分组很重要

上述字符分组的例子表明，如果数据集中存在连续值组合出现多次的情况，就可以利用这种情况来减小熵。一般来说，通过最佳符号分组预处理数据，会得到一个较小的熵值。

一件有趣的事是，示例1中的集合是集合打乱后的版本，或者说是的一个排列。

在数学中，排列这一概念是指重新安排或者改变一个集合的所有元素的次序或者顺序。

实际上，一个排列就是原来的集合打乱顺序后的一个版本，这里，我们会关注集合元素之间的顺序，并且确保没有重复元素。从经典的定义来看，只有同一组数的不同顺序才算排列，比如可以说[2,1,3,4] 是[1,2,3,4] 的一个排列，但[5,2,7,9] 就不是。

排列很难压缩是出了名的。（有些人甚至认为基本不可能，我们无法确定他们是否真的理解这个词的含义。）原因很简单，从熵的角度来看，一个排列是不可压缩的，因为排序本身并不包含什么信息（这是因为它已经不再是有序的）。由于每个值出现的可能性相同，因此需要相同数量的二进制位来表示。

集合编码后的大小等于个二进制位注2，可以将其大小的计算公式归纳为，请记住这个公式。当对数据压缩、信息论和熵有更多的了解时，这个值会一再出现，提醒我们在这个宇宙中我们是多么微不足道。

注2这里我们用来表示集合中的最大元素，即按递增排序后集合中的最后一个元素。

通过消除编码法压缩排列

还记得前面说过排列不可压缩吗？不好意思，我们说谎了。不过这个谎不大，而且有必要撒这个谎，这样你才明白形势的严峻。同时，我们也要对你说一声“抱歉”。事实上，排列是可以稍微压缩的，但这个过程没什么意思，也没多少实际价值。不过，我们还是准备看一看。

我们来看集合。

根据集合的元素值对它进行编码，由于最大值为7，因此每个元素都需要3个二进制位，编码后有：

一共是24个二进制位。

现在，换一种方法，通过索引来编码，具体步骤如下。（如果你喜欢传统的方法，不妨拿着纸和铅笔跟着做。）

第一轮操作

创建一个包含8个元素的空数组，每个下标为的元素保存的值为，如下图所示。

(1)从集合中的第一个元素开始，其值为5。

(2) 计算该数的空闲位置下标（Free-Slot-Index），即找出其值为5的元素的下标。在这个例子中，5的下标就是5。

(3) 计算出你需要多少二进制位才能对这一下标进行编码，这可以通过计算元素个数的LOG2得出。由于一共有8个元素，因此LOG2(8)=3，即3个二进制位。所以，可以用3个二进制位对5进行编码，即101。

(4) 将值为5的元素从数组中删除。

输出流为101，新的工作数组如下图所示。

第二轮操作

(1)从集合中取第二个元素，即7。

(2) 从数组中找出其值为7的元素下标。现在，7的下标为6。

(3) 数组中还有7个元素，而LOG2(7)=3，因此用3个二进制位对下标6编码并输出，得到110。

(4) 将值为7的元素从数组中删除。

输出流为101 110，新的工作数组如下图所示。

第三轮操作

(1)从集合中取第三个元素，即1。

(2) 从数组中找出其值为1的元素的下标。现在，1的下标为1。

(3) 数组中还有6个元素，而LOG2(6)=3，因此用3个二进制位对下标1编码并输出，得到001。

(4) 将值为1的元素从数组中删除。

输出流为101 110 001，新的工作数组如下图所示。

第四轮操作

(1)取集合的第四个元素，即4。

(2) 从数组中找出4对应的下标，即3。

(3) 数组中还有5个元素，而LOG2(5)=3，因此用3个二进制位对下标3编码并输出，得到011。

(4) 将值为4的元素从数组中删除。

输出流为101 110 001 011，新的工作数组如下图所示。

第五轮操作

现在，事情变得有趣起来。（我们已经从数组中取出了一半的元素，[5,7,1,4,6,3,2,0]。）

(1) 取第五个元素，即6。

(2) 从数组中找出6对应的下标，即3。

(3) 此时，数组中元素的个数变为4，而LOG2(4)=2,因此只需要2个二进制位就可以对下标进行编码。

(4) 用2个二进制位对下标3编码并输出，得到11。

(5) 将值为6的元素从数组中删除。

输出流为101 110 001 011 11，数组如下图所示。

最后的操作

(1) 下一个值为3。

(2) 其对应的下标为2。

(3) 用2个二进制位对下标2编码并输出，得到10。

(4) 将值为3的元素从数组中删除。

输出流为101 110 001 011 11 10，数组如下图所示。

(1) 下一个值为2，其对应的下标为1，用1个二进制位进行编码。

(2) 最后一个值为0，其对应的下标也为0，同样用1个二进制位进行编码。

最终的输出流为101 110 001 011 11 10 1 0，其长度为18个二进制位。

按上面的方法编码，最终节省了6个二进制位。下面通过下表来进行比较。

对数直接进行编码时，共需要24个二进制位，而对下标编码时，只需要18个二进制位，也就是节省了大约25% 的空间。好了，现在我们已经知道了这样做可以节省空间，但是……

为什么这样做能节省空间

我们知道，对于包含个整数，取值范围为不重复的全排列，一共有（称为的阶乘）种可能。因此，第一个值出现后，我们就知道它不会再次出现。也就是说，去掉第一个值后，就只剩下种可能；而去掉第二个值后，就只有种可能了，以此类推。在某个点时，的下标值与的下标值之差就能变成整数。因此，可以用更少的二进制位来确定还剩下哪些可能性。

无论排列的大小多大，这种方法都适用。通过这种方法来编码，总能确保最终所产生的数据流比通过熵计算的小。例如，如果你遇到的是包含从0到65535这些整数的一个排列，不管这些整数的顺序如何混乱，你总可以将这些数据压缩到原空间的90%。实际上，只节省这么少的空间通常不值得我们这样去做。

解码工作则以相反的方式进行。最开始时，我们有一个空的数组，然后从数据流中读出LOG2（# 没有赋值的元素个数）个二进制位，这表示的是该元素的下标，通过下标我们就知道它原来所代表的值。具体操作如下。

(1) 一共有8个没有赋值的元素，因此从输入流中读出前3个二进制位，这里是101。

(2) 二进制101对应的值为5，下标5对应的值为5，因此第一个数是5。现在，将5从数组中删除。

(3) 还有7个没有值的元素，我们需要读取接下来的LOG2(7)（即3）个二进制位，其值为110，对应的十进制下标为6，因此第二个数是7。

(4) 接下来，请按照上面的方法解码剩下的元素。

上一章目录下一章