5

我希望读者知道香农的信息论，它说与概率为 p(a) 的事件 a 相关的信息内容是 -log(p(a))。用外行的话来说，如果您需要表示 0-7 范围内的数字，那么您至少需要 -log(1/8)=log(8) （其中基数为 2），即 3 位。

假设有一个整数数组，范围从 0 到 255。我不会将数组存储为 8 位数字，而是先按升序对数组进行排序（当然保留备份）。我不会将每个数组元素编码为 8 位整数，而是输出其在排序数组中的位置。现在的问题是让解码器或接收器知道这个排序后的数组。我将输出第一个（最小）整数值作为 8 位数字，然后很快将增量添加到该数字。首先是所有排序后的数组，然后是元素的顺序，即位置值。

例如：原始数组-> 231 , 3 , 45 , 0 , 23 , 32 , 78

排序数组-> 0,3,23,32,45,78,231

编码信息是 0（排序数组的第一个元素为 8 位 num），然后是 3（这是 0 的增量），然后是 20，然后是 9，然后是 13，然后是 33，然后是 153。

在发送第一个数字和连续的增量之后，我将发送订单，即因为这里有 7 个整数，我需要一个三位数字作为订单，3（原始数组中 0 的位置）然后 1（3 的位置）然后 4 （23 的位置）然后 5（32 的位置）然后 2（45 的位置）然后 6（78 的位置）然后 0（231 的位置）。

即位置值现在是 3 , 1 , 4 , 5 , 2 , 6 , 0

分析看这个方案会不会压缩：

第一个数字-> 8 位（实际上可能需要更少的位，因为它是最小的）

接下来 6 个数字 -> 5 位（问题是我们可以用 5 位编码 0、3、20、9、13，但不能将 33 和 153 编码为 31（最多 5 位））

7 个位置，每个 3 位->21 位

总计-> 8+6*5+21=59。这比我们编码 7 个 8 位数字所需的 56 位要多，而且我们实现了扩展而不是压缩，而且我们的方案是有损的，因为我们无法正确表示一些大数字。

让我们为这个方案增加一些复杂性。

我将第一个 0 编码为 8 位数字，紧随其后的是最后一个数字 231 的代码。然后我将发送代码为 3 的下一个增量超过 0 然后编码为 153 的减量超过 231 然后 20 然后 33、9,13

即我以不同的顺序发送-> 而不是 0,3,20,9,13,33,153 我将发送为 3,153,20,33,9,13

我得到的是动态范围的连续减小你观察到我们已经发送了 0 然后 231 然后 3 然后 153 到这个时候值的范围减小了我的意思是下一个增量到 3 将是 20 不能大于倒数第二个数字即 78 和数字 20 不能超过 75（如果超过，那么第三个数字（3+76（比如说））将大于 78，这显然违反了我们的排序假设。

如果你到目前为止已经理解了这个想法，我有一个进一步改进的方案来使用二进制搜索的想法来进一步减少动态范围并将这种技术放在类固醇上。这是排序后的数组

0 , 3 , 23 , 32 , 45 , 78 , 231

观察排序后的数组有 7 个数字，中间的数字是 32。所以现在我们将这个 32 编码为 8 位，然后我们将按顺序发送增量。即32之后的下一个数字将是3，它将被编码为29（即32-3），下一个将是78，编码为46（78-32），然后0编码为3（3-0），然后23编码为20 (23-3) 然后 45 编码为 33(78-45) 然后最后一个 231 编码为 153(231-78)。

如果您现在看到，我们可以根据具体情况决定每个数字使用多少位。

我们将把排序后的数组发送为 32（范围 0-255，所以 8 位），29（范围 0-32，所以 6 位），46（范围 32-255，所以 8 位），3（范围 0-3，所以 2 位） ) ,20(范围 3-32 所以 5 位),33(范围 32-78 所以 6 位),153(范围 78-255 所以 8 位)

所以总共 8+6+8+2+5+6+8=43 这是无损的，并且比我们最初估计的 38（8 位 + 5*6 位）多，所以这加上了 7 个位置值，每个位置值是 3 位总共 43+21=64 大于 56。我们的方案还在扩展中。

我们可以对 21 位的位置编号做哪些改进。因为每次我们发送位置信息时，如果我们有 7 个位置要发送，那么位置的数量就会减少 1，那么比特数就是 log(7)+log(6)+log(5).... 然后就是 log(fact (7)) 所有对数都以 2 为底的位。

注意我使用了公式 log(a)+log(b)=log(ab)

这等于 12.299，加上 43 等于 55.299，略低于 56。但这不切实际。我们至少需要 3(range 7)+3(range 6)+3(range 5)+2(range 4)+2(range 3)+1(range 2)+0(range 1)=14 当添加时与 43 给出 57 这是扩展。

这项工作的目标是使数据大小至少减少 1 位。如果我们在不假设数据的情况下将 56 位压缩为 55 位，那么我们可以将 55 位的输出再次压缩为 54 位，并且很快。这看起来是不可能的，这个想法类似于永动机。现在的任务是看看是什么阻止我们压缩更多。

我需要分析一个更大的数组的例子，看看排序数组的 43 位是否可以小于 43。另外，将数组分成许多部分并分别编码每个部分有什么好处。还有一个目标是找到计算表示排序数组所需的位数的公式是什么。即给定数组大小和数组元素范围如何找到像 43 这样的数字。

让我们再次把这个 3,1,4,5,2,6,0 作为一个未排序的数组，观察这个序列是从 0 到 6 的七个数字的 5040 个排列之一。我们可以将其表示为一个 13 位数字（12.299正如理论所暗示的那样）。

我需要知道是否可以进一步压缩这个数组。

4

2 回答 2

2

这项工作的目标是使数据大小至少减少 1 位。

这在所有输入上都是不可能的。您可能会浪费大量精力来尝试正确计算各种表示中的位、犯错误、修复它们等，而您真正需要做的只是计算有多少个案例。

有 2^k 个可能的输入，其中 k 是输入中的位数。假设您相信每个输入都有 k-1 位表示。然后有 2^(k-1) 种可能的表示。然后，如果您将这 2^(k-1) 个表示中的每一个都提供给您的解压缩器，那么您显然只会得到 2^(k-1) 个结果。其他 2^(k-1) 个可能的输入在操作中丢失。无法从您的表示中生成那些缺失的输入，这意味着实际上您的表示无法涵盖所有​​可能的 2^k 输入。其中至少有一半没有被覆盖。

于 2012-04-07T20:26:33.177 回答
2

如果我们在不假设数据的情况下将 56 位压缩为 55 位，那么我们可以将 55 位的输出再次压缩为 54 位，并且很快。这看起来是不可能的，这个想法类似于永动机。现在的任务是看看是什么阻止我们压缩更多。

如果不对保证减小所有可能数据值大小的数据做任何假设，就不可能有无损压缩算法。简单的鸽子洞原理我们可以看到以下内容。当您使用 n 位时，您可以表示 2^n 个值。使用 n-1 位，您只能表示 2^(n-1) 个值。因此，如果您对一半的原始值进行编码，则必须使用与已编码值之一相同的位对下一个值进行编码，因此您会丢失信息。当然，如果在原始数据中您只使用少于 2^(n-1) 个不同的值，您可以将该数据的大小减小一点（或更多），但这已经是对数据的假设。此外，您将无法使用该方法递归地减小数据的大小而不会造成任何损失。

因此，您可能会找到某种方式将数组压缩一点，但前提是当前的压缩方式最多使用一半可能的位模式。虽然这可能是压缩数组的一些模糊方式，但肯定会使用一些 k 位的一半以上的位模式。这个 k 将是您的阈值，您将无法再减小大小。

将数组分成许多部分并分别编码每个部分的好处是什么。

如果将数组拆分为更小的部分，则局部差异会更低，因此您可以使用更少的位来表示数字之间的差异。因此，在像 [1, 2, 3, 4, 2^30, 2^30+1, 2^30+2, 2^30+3] 这样的数组中，您可以节省一些空间。但是，您将不得不使用更多位来表示新的绝对值。它们再次可以表示为到某个任意绝对值的距离以节省一些空间。但我不确定在某些情况下是否真的值得你概述的所有努力来节省 1 位。

把它们加起来。如果你有一个像 [2^30, 2^30+1, 2^30+2, 2^30+3] 这样的数组，你显然可以通过取数字之间的差异来节省一些空间，但正如你在您的回答，在某些情况下，它会增加数据的大小。因此，您不能有一个压缩算法来存储任何（不做假设）使用少于 n 位的数字数组，其中 n 是数组中数字的对数的上限之和。

于 2012-04-07T10:22:28.670 回答