最佳位图压缩方式，用于随机设置位

Question

我正在寻找一种位图压缩算法，可以通过设置随机位来生成位图，并且我很关心位图在RAM中所占用的空间。未压缩的位图存储1073741824位（约10亿位），需要大约128MB的空间，而我根本没有那么多的空间。我希望尽可能地节省空间（RAM）。

我查看了WAH、EWAH等压缩算法（尚未仔细阅读论文），但这些算法似乎都是流式压缩，无法在生成位图时以压缩格式随机设置其中的位（非常昂贵的操作）。例如，如果要设置第100、200、300个位，则可以实现，但如果需求是设置第100、200、105、3000、1999个位，则不能实现。

在我的情况下，所有位的设置信息都只能随机获得，例如，如果我进行某个操作1073741824次，则需要基于操作结果设置任何位，并且它们不会按顺序递增。

请问以上理解是否正确？还有其他替代方案吗？

总结：创建压缩位图的算法，同时随机设置位。不存在熵/模式信息，分布可以是任意的。目标：最佳算法以节省内存。减少生成位图时设置随机位所占用的内存。

- user648129

---

会设置多少位？这决定了总熵和最小存储要求。比特可以被多次设置吗？那会发生多少次？ - usr

位可以随机设置，但只能设置一次。 - user648129

如果50%的位是随机设置的，那么你根本无法进行压缩。那么你该怎么办呢？ :) 你必须将问题限制在少于128 MB的范围内。 - usr

是的，如果50%均匀分布（而且我们没有使用模式压缩），并且我们正在使用运行列表排序的流压缩，那将是最坏情况。实际上，我们无法确定位是否会形成任何模式，因为它们是随机获取的。 - user648129

@harold 在你的评论后，我更新了问题，四叉树仍然满足更少的内存和随机设置位吗？我会检查一下并看看它是否有用。 - user648129

只有在非常稀疏或非常密集的情况下才行。四叉树非常擅长不存储大均匀区域，但非常不擅长存储50%的噪声。所以简而言之...不行，其他任何东西也无法做到这一点。 - harold

Answer 1

我们正在使用 Roaring bitmaps 取得良好的结果：http://roaringbitmap.org/。

- Daniel Lemire

---

Jar文件可在Maven存储库或直接在GitHub上获取：https://github.com/lemire/RoaringBitmap/releases。 - Daniel Lemire

对不起，@Danel，但我只能看到源代码下载链接...我使用Eclipse，您能给我一个.jar下载链接吗？ - Animesh Mangla

通常情况下，您不会自己获取JAR文件，而是使用专门的工具来完成。当然，用于构建Java项目的标准工具是maven，但所有IDE也都支持它。例如，在Eclipse中，您只需转到“添加库”，然后选择“Maven托管依赖项”。IntelliJ也是一样的。如果您必须手动操作，请浏览项目的README.md文件，链接已提供。 - Daniel Lemire

Answer 2

如果事先不知道模式，而且你的工作记忆很小，那么以下方法应该可以胜任：

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

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

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

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

- usr