13

我有一大串从最低到最高排序的随机整数。数字从 1 位开始，到 45 位附近结束。在列表的开头，我的数字非常接近：4、20、23、40、66。但是当数字开始变大时，它们之间的距离也有点高（实际上它们之间的距离是偶然的）。没有重复的数字。

我正在使用位包装来节省一些空间。尽管如此，这个文件可能会变得非常大。

我想知道在这种情况下可以使用哪种压缩算法，或者任何其他技术来尽可能多地节省空间。

谢谢你。

4

6 回答 6

10

如果您知道数据的真实分布，则可以进行最佳压缩。如果您可以为每个整数提供概率分布，您可以使用算术编码或其他熵编码技术来压缩到理论上的最小大小。

诀窍在于准确预测。

首先，您可能应该压缩数字之间的距离，因为这可以让您进行统计报表。如果您要直接压缩数字，您将很难对它们进行建模，因为它们只出现一次。

接下来，您可以尝试构建一个非常简单的模型来预测下一个距离。保留所有先前看到的距离的直方图并根据频率计算概率。

您可能需要考虑缺失值（您显然不能为它们分配 0 概率，因为那是不可表达的）但是您可以为此使用启发式方法，例如逐位编码下一个距离并单独预测每个位。您几乎不需要为高位支付任何费用，因为它们几乎总是 0，并且熵编码会将它们优化掉。

如果您知道分布，所有这一切都会简单得多。示例：您正在压缩所有素数的列表，您知道距离的理论分布，因为有公式。所以你已经有了一个完美的模型。

于 2012-09-30T20:09:17.650 回答
9

有一种非常简单且相当有效的压缩技术，可用于已知范围内的排序整数。像大多数压缩方案一样，它针对串行访问进行了优化，但如果需要，您可以构建索引来加速随机访问。

它是一种增量编码（即每个数字由与前一个数字的距离表示），由一个代码向量组成，这些代码要么是

  • 单个 1 位，表示 2 k的增量，在以下代码中添加到增量中，或

  • 一个 0 位后跟一个 k 位增量，表示下一个数字是前一个数字的指定增量。

例如，如果 k 为 4，则序列：

00011 1 1 00000 1 00001

编码三个数字。第一个四位编码 (3) 是第一个 delta，取自初始值 0，因此第一个数字是 3。接下来的两个单独的 1 累加为 2·2 4或 32 的 delta，相加到以下 0000 的增量，总共 32。所以第二个数字是 3+32=35。最后最后一个delta是单2 4加1，一共17个，第三个数是35+17=52。

1 位表示下一个增量应该增加2k（或者，更一般地，每个增量增加2k乘以紧接在前的 1 位的数量。）

另一种可能更好的思考方式是将每个增量编码为可变长度位序列： 1 i 0(1|0) k，表示 i·2 k +[k 位后缀]的增量。但是第一个演示文稿与最优性证明更好地对齐。

由于每个“1”代码代表 2 k的增量，因此它们的数量不能超过 m/2 k，其中 m 是要压缩的集合中的最大数字。其余代码均对应数字，总长度为 n·(k + 1)，其中 n 是集合的大小。k 的最佳值大约为 log 2 m/n，在您的情况下为 7 或 8。

我对算法的概念做了一个快速的证明，而不用担心优化。它仍然很快；对随机样本进行排序比压缩/解压缩它需要更长的时间。我尝试了一些不同的种子和向量大小，从 16,400,000 到 31,000,000，值范围为 [0, 4,000,000,000)。每个数据值使用的位范围从 8.59 (n=31000000) 到 9.45 (n=16400000)。所有的测试都是用 7 位后缀完成的；log 2 m/n 从 7.01 (n=31000000) 到 7.93 (n=16400000) 不等。我尝试使用 6 位和 8 位后缀；除了在 n=31000000 的情况下，6 位后缀略小，7 位后缀总是最好的。所以我猜想最优 k 并不完全是 floor(log 2 m/n)，但也不远了。

压缩代码：

void Compress(std::ostream& os,
              const std::vector<unsigned long>& v,
              unsigned long k = 0) {
  BitOut out(os);
  out.put(v.size(), 64);
  if (v.size()) {
    unsigned long twok;
    if (k == 0) {
      unsigned long ratio = v.back() / v.size();
      for (twok = 1; twok <= ratio / 2; ++k, twok *= 2) { }
    } else {
      twok = 1 << k;
    }
    out.put(k, 32);

    unsigned long prev = 0;
    for (unsigned long val : v) {
      while (val - prev >= twok) { out.put(1); prev += twok; }
      out.put(0);
      out.put(val - prev, k);
      prev = val;
    }
  }
  out.flush(1);
}

减压：

std::vector<unsigned long> Decompress(std::istream& is) {
  BitIn in(is);
  unsigned long size = in.get(64);
  if (size) {
    unsigned long k = in.get(32);
    unsigned long twok = 1 << k;

    std::vector<unsigned long> v;
    v.reserve(size);
    unsigned long prev = 0;
    for (; size; --size) {
      while (in.get()) prev += twok;
      prev += in.get(k);
      v.push_back(prev);
    }
  }
  return v;
}

使用可变长度编码可能有点尴尬；另一种方法是将每个代码（1 或 0）的第一位存储在一个位向量中，并将 k 位后缀存储在一个单独的向量中。如果 k 为 8，这将特别方便。

导致文件稍长但更容易为其构建索引的变体是仅使用 1 位作为增量。那么对于某个 a，可能为 0，增量总是 a·2 k，其中 a 是后缀代码之前的连续 1 位的数量。然后，该索引由位向量中每个第N个1位的位置以及到后缀向量中的相应索引（即与位向量中的下一个0对应的后缀的索引）组成。

于 2012-09-30T20:35:35.813 回答
5

过去对我来说效果很好的一个选项是将 64 位整数列表存储为 8 个不同的 8 位值列表。您存储数字的高 8 位，然后是接下来的 8 位，等等。例如，假设您有以下 32 位数字：

0x12345678
0x12349785
0x13111111
0x13444444

存储的数据将是（十六进制）：

12,12,13,13
34,34,11,44
56,97,11,44
78,85,11,44

然后我通过放气压缩机运行它。

我不记得我能用这个实现什么压缩比，但它比压缩数字本身要好得多。

于 2012-09-30T22:04:17.600 回答
5

我想用最简单的解决方案添加另一个答案：

  1. 如前所述，将数字转换为增量
  2. 通过 7-zip LZMA2 算法运行它。它甚至支持多核

我认为这将在您的情况下给出几乎完美的结果，因为距离分布简单。7-zip就能把它捡起来。

于 2012-09-30T22:09:42.133 回答
3

如果您的序列由伪随机数组成，例如可能由典型的数字计算机生成，那么我认为任何压缩方案都不会胜过，为了表示的简洁，只需存储生成器的代码和任何东西您需要定义其初始状态的参数。

如果您的序列由以某种非确定性方式生成的真正随机数组成，那么已经发布的其他答案提供了各种好的建议。

于 2012-10-01T06:10:41.607 回答
3

您可以简单地使用Delta Encoding和Protocol Buffers。

就像你的例子：4、20、23、40、66。

Delta 编码压缩：4、16、3、17、26。

然后，您将所有数字作为 varint 直接存储在 Protocol Buffers 中。0-127 之间的数字只需要 1 个字节。128-16384 之间的数字需要 2 个字节......这对于大多数场景来说已经足够了。

此外，您还可以使用熵编码（霍夫曼）来实现比 varint 更有效的压缩率。每个数字甚至少于 8 位。

将一个数除以 2 部分。比如 17=...0001 0001（二进制）=(5)0001。第一部分 (5) 是有效位数。后缀部分 (0001) 没有前导 1。

像这个例子：4、16、3、17、26 = (3)00 (5)0000 (2)1 (5)0001 (5)1010

即使有很多数字，第一部分也会在 0-45 之间。所以它们可以通过像霍夫曼这样的熵编码来有效地压缩。

于 2020-07-06T09:07:33.520 回答