已排序整数的压缩算法

Question

已排序整数的压缩算法

algorithmcompression

13

我有一个由小到大排序的随机整数序列，其中数字从1位开始，接近45位。在列表的开头，我有一些非常接近的数字：4、20、23、40和66。但是随着数字的增加，它们之间的距离也会略微增加（实际上它们之间的距离是随机的）。没有重复的数字。

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

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

谢谢。

- Frederico Schardong

我不明白。你能画一个（可能是ASCII）序列的图片或其他什么吗？ - keyser

@Keyser 1、23、33、34、39、80、122、125、169、168、203，以此类推。 - Frederico Schardong

5

你可以将这个列表表示为相邻数字之间的距离 -- 22, 10, 1, 5, 41, 42, 3...（如果我的算术没错的话）。由于这些数字比较短，你可以更紧密地将它们打包在一起。（请注意，在生成初始数字1时，你应该在序列开头添加一个虚拟零，或以其他方式记录开始数字。）你甚至可以尝试对差值再做一次差分来得到有符号的数字 -- -12, -9, 4, 36, 1, -39... 这可能会更加紧凑（取决于数字分布情况）。 - Hot Licks

请注意，您可以使用多种可变长度的记法。例如，以11b开头的数字是一个3字节（22位）的数字，以10b开头的数字是一个2字节（14位）的数字，以0b开头的数字是一个1字节（7位）的数字。您可以将此方案与位打包结合使用，以得到最适合您需求的数字大小。 - Hot Licks

@HotLicks 我不理解你的最后一个想法："例如，以11b开头的数字是一个3字节（22位）的数字。" 而且我不需要随机访问它们，我将从开头逐个访问它们。 - Frederico Schardong

显示剩余3条评论

6个回答

10

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

关键在于准确预测。首先，你应该压缩数字之间的距离，因为这样可以让你做出统计推断。如果直接压缩数字，你会很难对它们进行建模，因为它们只出现了一次。

其次，你可以尝试构建一个非常简单的模型来预测下一个距离。保留所有之前看到的距离的直方图，并从频率中计算概率。

你可能需要考虑丢失的值(显然不能将它们分配为0的概率，因为那是不可表达的)，但你可以使用启发式方法，比如逐位编码下一个距离并逐位预测。你几乎不需要支付高阶位数的代价，因为它们几乎总是0，而熵编码会将它们优化掉。

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

- usr

有一个概率。我从1位计数到接近43位，但每个数字都存储在不同的文件中，这是随机的。这就是为什么每个文件都有随机但排序的数字。共有256个文件，因此下一个数字进入文件而不是另一个文件的概率为1/256。 - Frederico Schardong

这意味着距离遵循一个完全已知的分布吗？如果是，你在上一段中得到了答案。 - usr

1

你也可以只使用一个文件，对于每个数字存储一个8位整数来表示它属于哪个文件。这样可以获得最佳压缩效果（因为文件是均匀分布的），每个数字只需要8位即可。 - usr

抱歉，它们并不是均匀分布的。我正在使用哈希函数来确定每个数字应该放在哪个文件中，因此并没有100%的1/256分布。 - Frederico Schardong

1

这是几乎完美的分布。如果值到文件的分配由哈希函数控制，则此方案是您可以做的最好的选择。对于每个数字，您实际上正在生成一个随机的8位值。 - usr

我已经实现了它并且发现了有趣的结果。随着生成的数字变得越来越大（如99999999），它们之间的距离也在增加。我不知道为什么我有一个数字X，其右边紧接着另一个数字X + 268。这意味着它们之间生成了267个数字，并被存储在15个不同的文件中。看起来散列函数并不像预期的那样随机。 - Frederico Schardong

6

过去我使用过的一种很好的方法是将64位整数存储为8个不同的8位值列表。首先存储数字的高8位，然后是接下来的8位，以此类推。例如，假设您有以下32位数字：

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

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

我随后将其通过deflate压缩器运行。

我不记得我能够使用这种方法实现什么压缩比，但它比直接压缩数字本身要好得多。

- Jim Mischel

5

我希望能提供一种最简单的解决方案：

按照之前讨论的方法将数字转换为增量
使用7-zip LZMA2算法进行压缩。它甚至支持多核处理器。

我认为这在您的情况下将会得到几乎完美的结果，因为距离具有简单的分布规律。7-zip将能够处理它。

- usr

我尝试了LZMA和LZMA2，但是zpaq的结果稍微好一些，无论如何还是谢谢。 - Frederico Schardong

Nanozip也值得一试。它是顶级压缩器之一，而且速度仍然很快。 - usr

4

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

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

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

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

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

将一个数字分成两部分。例如，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之间，即使有很多数字。因此，它们可以通过像哈夫曼这样的熵编码进行有效压缩。

- Loki

3

如果您的序列由伪随机数组成，例如典型数字计算机生成的随机数，则我认为任何压缩方案都无法超过简单地存储生成器代码以及定义其初始状态所需的参数来实现表示的简洁性。

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

- High Performance Mark

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

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

这是一种增量编码的类型（即每个数字都表示为与前一个数字的距离），由以下两种代码向量组成：

- 单个1位，表示要添加到下一个代码中的2^k的增量。 - 0位后面跟随k位增量，表示下一个数字是前一个数字指定的增量。

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

00011 1 1 00000 1 00001

编码三个数字。第一个四位编码（3）是从初始值0获取的第一个增量，因此第一个数字是3。接下来的两个独立的1累积到32的增量，然后将其添加到后面的增量0000中，总共为32。因此第二个数字是3 + 32 = 35。最后，最后一个增量为单个2^4加1，总共17，第三个数字为35 + 17 = 52。

1位表示下一个增量应该增加2^k（或更普遍地说，每个增量都增加了2^k乘以其立即前面的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。

我快速验证了该算法的概念，没有担心优化。它仍然非常快；对随机样本进行排序比压缩/解压缩要花费更多时间。我尝试了几个不同的种子和向量大小，从1640万到3100万，值范围为[0，4000000000)。使用的位数范围从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·2^k，其中a是紧随后缀代码的连续1位数目，可以为0。索引由位向量中每N^th个1位的位置以及相应的后缀向量索引（即与位向量中下一个0对应的后缀索引）组成。