我需要帮助来分析这种编程技术来压缩数组

Question

我希望读者能够意识到shannon的信息理论，它指出与概率为p（a）的事件a相关的信息内容是-log（p（a））。通俗地说，如果您需要表示0-7范围内的数字，那么您至少需要-log（1/8）= log（8）（其中base为2）即3位。

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

例：原始阵列 - > 231，3，45，0，23，32，78

排序阵列 - > 0,3,23,32,45,78,231

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

发送第一个数字和连续的delta后，顺序，即因为有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位

total-> 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（如果它是那么的话） d数（3 + 76（说））将大于78明显违反我们的排序假设。

如果你明白这个想法到现在我有一个进一步的改进方案，以使用二进制搜索的想法，以进一步降低动态范围，并把这种技术类固醇。 这里是排序后的数组

0，3，23，32，45，78，231

观察到排序后的数组是具有7号和中间的一个是32。所以，现在我们将编码本32与8位，然后我们将发送三角洲预先订购。即32之后的下一个数字将是3，其将被编码为29（即32-3），并且下一个数字将被编码为46（78-32），然后0编码为3（3-0），然后23编码为20 （23-3），然后45编码为33（78-45），然后编码为153的最后一个231（231-78）。

如果你现在看到的，我们可以决定多少位为每个数字逐情形使用上的情况。我们将发送排序的数组为32（范围0-255所以8位），29（范围0-32所以6位），46（范围32-255所以8位），3（范围0-32所以8位），3（范围0-32所以6位） 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个位置值，每个总共43 + 21 = 64更多我们的计划还在扩大。

我们可以做这是21位的位置编号什么改善。由于每次我们发送位置信息，如果我们有7个位置发送，则位数减1，那么位数是log（7）+ log（6）+ log（5）....这就是log（事实（7））位，其中所有的对数是基体2

观察到我已经使用式日志（一）+日志（b）=日志（AB）

这是等于其与添加时12.299 43等于55.299，比56低一点。但这不实际。我们至少需要3（范围7）+3（范围6）+3（范围5）+2（范围4）+2（范围3）+1（范围2）+0（范围1）= 14，有43个给出了57个扩展。

这一工作的目的是实现在数据大小至少1位的减少。如果我们将56位压缩成55而没有任何关于数据的假设，那么我们可以将55位的输出再次压缩到54位，并且很快。这看起来不可能，这个想法与永久机器类似。现在的任务是查看阻止我们压缩更多的东西。

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

允许再次借此3,1,4,5,2,6,0作为排序的数组，并观察该序列中的一个50个从0到6的7个数字的排列。我们可以将其表示为13位数（理论表明为12.299）。

我需要知道的是，可以更压缩该阵列。

Answer 1

如果我们将56位压缩成55而没有任何关于数据的假设，那么我们可以获取55位的输出并将其再次压缩为54位，并且很快。这看起来不可能，这个想法与永久机器类似。现在的任务是查看阻止我们压缩更多的东西。

不可能有一个无损压缩算法，没有任何有关数据的假设，保证减少所有可能的数据值的大小。只需通过pigeon hole principle我们可以看到以下内容。当您使用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是数组中数字对数的上限的总和。

Answer 2

这项工作的目标是实现数据至少减少1比特的大小。

这是不可能的所有输入。当你真正需要做的是计算有多少个案例时，你可以浪费大量的精力来试图正确地计算各种表示中的位数，犯错误，修复它们等。

有2^k个可能的输入，其中k是输入中的位数。假设您相信您有每个输入的k-1位表示。然后有2 ^（k-1）个可能的表示。然后，如果你将这2 ^（k-1）个表示中的每一个表达给你的解压缩器，你显然只会得到2 ^（k-1）个结果。其他2 ^（k-1）个可能的输入在行动中失踪。没有办法从您的表示中生成缺少的输入，这意味着实际上您的表示不能涵盖所有可能的2^k输入。至少有一半没有被覆盖。