performance - 随机设置位的最佳位图压缩

Question

我正在寻找位图压缩算法，它可以让我通过设置随机位来生成位图，我担心位图在 RAM 中占用的空间量，例如

存储 1073741824 位（大约 10 亿位）的未压缩位图需要大约 128 MB 的空间，而我根本没有那么多空间。我想在尽可能少的空间（RAM）中做到这一点。

我在其他人那里查看了 WAH、EWAH 等（还没有仔细阅读论文），但看起来它们是流压缩，并且在位图的压缩格式中随机设置位（在创建它时）是不可能的（非常昂贵的操作），例如，如果想设置第 100、第 200、第 300 是可行的，但如果要求设置第 100、第 200、第 105、第 3000、第 1999，那么这是不可能的。

在我的情况下，对于所有位，只能随机获取设置了哪些位和未设置的信息，例如，如果我正在执行一些操作 1073741824 次，我需要根据操作结果设置任何位，它们不会以递增的顺序。

这是正确的吗？还有其他选择吗？

摘要：在随机设置位时创建压缩位图的算法。没有可用的熵/模式信息。分发可以是任何东西。

目标：节省内存的最佳算法。通过设置随机位来减少位图在创建时占用的内存。

Answer 1

我们使用 Roaring 位图获得了不错的效果：http ://roaringbitmap.org/

Answer 2

如果事先不知道任何模式，并且您的工作记忆很少，那么以下应该可以正常工作：

将图像平铺成小部分（线条或矩形平铺）。这些部分应该足够小，以便您可以快速解压缩、设置位和压缩。它们应该足够大，以便为编码器提供足够的数据来实际编码（64KB？）。您可以使用任何压缩算法，例如 Deflate 或 LZMA (7-zip)。

将传入的位临时放入列表中。一旦该列表填满（可能占用了 1MB 的空间？），您需要将这些位复制到位图的各个部分。完成后，您可以清除列表。该列表只是一个临时缓冲区，允许将每个部分的许多更新批处理到一个解压缩循环中。

在写出这些位之前，按部分和位置对它们进行排序。这使您可以清除重复项并只处理一次所有部分。

请注意，不能保证压缩甚至是可能的。如果没有可压缩的模式，就不可能压缩。