我怎样才能最好地压缩部分排序的 50000 字节

Question

我希望尽可能压缩 50000 字节，这些字节已部分排序。

这意味着像0,0,3,4,5,6,6,9,....,250.
这样的字节增加了256次
此外还有大约。 630000000 倒置。我已经使用 bubblesort 计算了反转并计算了递减对。
每个字节相等且经常出现。
runs.length相差20%

目前我使用 deltacompression 进行运行，使用 huffman 进行编码，我得到了 ca。 14000 字节输出。如何进一步压缩它？

示例Link：http://pastebin.com/raw/we57yZUw 列表中以逗号分隔的文件字节。无编码。

Answer 1

简答，您已经非常接近理论极限了。除非您有一些关于这些序列的信息，但您没有与我们分享，否则您不可能做得更好。而所谓“好得多”，你实际上不能达到14k，更不用说10k了。

让我们先看看可能有多少这样的序列。

我们可以将您的序列变成运行ge 0-65,535 中的 non-decreasing 序列，方法是将已完成的运行数的 256 倍添加到每个数字。也就是说，不是“环绕”，而是继续攀登。这是一个 one-to-one 对应关系，尽管不可否认，一些（实际上很多）递增序列与您要编码的序列不对应。请注意，我稍后会return。

在运行ge 0-65,535中长度为50,000的序列有多少个non-decreasing？好吧，这些序列与 115,535 位序列有 one-to-one 对应关系，其中 50,000 位为零。相应的是，您将每个 0 位替换为在它之前发生了多少个 1 位的计数，以从序列中获取数字。

115535位的序列数，其中50000位为0，即115535选50000。即 115535! / (50000! * 65535!)。这是一个相当大的数字，但我们可以使用 Stirling 的公式 log_2(n!) = n log_2(n) - n * log_2(e) + log_2(pi * n / 2) + O(log(n)) 来估计它的对数。为此：

log_2(115535) = 16.8179704401675
log_2(65535) = 15.9999779860527
log_2(50000) = 15.6096404744368
log_2(pi * 115535 / 2) = 17.4694665696399
log_2(pi * 65535 / 2) = 16.6514741155252
log_2(pi * 50000 / 2) = 16.2611366039092
log_2(e) = 1.44269504088896

现在，请仔细检查计算错误，

log_2(115535 choose 50000)
    = log_2(115535!) - log_2(65535!) - log_2(50000!)
    = 115535 * log_2(115535) - 115535 * log_2(e) + log_2(pi * 115535 / 2) + O(log(115535))
      - (65535 * log_2(65535) - 65535 * log_2(e) + log_2(pi * 65535 / 2) + O(log(65535)))
      - (50000 * log_2(50000) - 50000 * log_2(e) + log_2(pi * 50000 / 2) + O(log(50000)))
    = 115535 * 16.8179704401675 - 115535 * 1.44269504088896 + 17.4694665696399 + O(log(115535))
      - (65535 * 15.9999779860527 - 65535 * 1.44269504088896 + 16.6514741155252 + O(log(115535)))
      - (50000 * 15.6096404744368 - 50000 * 1.44269504088896 + 16.2611366039092 + O(log(115535)))
    = 1776399.91272222 - 954028.189285421 - 708363.532813996 + O(16.8179704401675)
    = 114008.190622803 + O(16.8179704401675)

如果您想展开斯特林级数的几项，您会发现 114008.190622803 与真实对数的偏差小于 1。

因此，您需要大约 114008 位来指定一个这样的序列，这需要 14251 个字节。这意味着如果你设法将它压缩到 14k 运行ge，你就非常接近理论极限了。除非您拥有比您提供的更多的关于序列的信息，否则您做得再好不过了。

但我在作弊。您指定运行的长度变化不超过大约 20%。我包括那些运行s 的长度不仅变化，而且甚至可以完全跳过某些运行s 的地方！这有什么大不了的？

好吧，从我刚刚运行的模拟来看，运行在超过 50% 的时间内都在中位数的 10% 以内。我们有 256 运行s。它们的长度实际上并不独立，但长运行与短运行相关，反之亦然，因此赔率优于 1/2^256，我们将运行完全满足长度要求。这意味着长度条件比理论最佳值节省了不超过 32 个字节。考虑到我们已经讨论了大约 14k 的数据，这并不是一个显着的改进。

我怎样才能最好地压缩部分排序的 50000 字节

How can i compress best possible 50000 bytes which are partly sorted

compression

arrays

sorting

algorithm

math