5

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

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

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

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

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

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

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

4

2 回答 2

4

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

于 2014-08-13T02:13:43.437 回答
0

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

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

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

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

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

于 2013-10-12T12:46:10.747 回答