最好的位圖壓縮，用於隨機設置位

Question

我在尋找位圖壓縮算法，它可以讓我通過設置隨機位來生成位圖，並且我關心的是RAM中的空間位圖的數量。

用於存儲1073741824位（大約10億位）的未壓縮位圖需要大約128 MB的空間，我根本沒有那麼多的空間。我想盡可能少地佔用空間（RAM）。

我在其他人看過WAH，EWAH等（還沒有仔細閱讀過論文），但看起來他們是流式壓縮和隨機設置位壓縮格式的位圖（同時創建它）是不可能的（非常昂貴操作）例如如果想要設置第100，第200，第300，這是可行的，但如果要求設置第100，第200，第105，第3000，第1999，那麼這是不可能的。

在我的情況下，所有比特只能隨機獲得哪些比特被設置和哪些未被設置的信息，例如，如果我正在做1073741824次操作，我需要根據操作結果設置任意位，並且它們不會按遞增順序排列。

這是正確的，有替代品嗎？

摘要：隨機設置位時創建壓縮位圖的算法。沒有可用的熵/模式信息。分配可以是任何東西。

目的：最佳的算法來節省內存。 通過設置隨機位來減少位圖佔用的內存。

Answer 1

如果沒有模式是預先知道的，你已經很少工作記憶，下面應該做的罰款：

平鋪圖像小段（線或長方形磚）。這些部分應該足夠小，以便可以快速解壓縮，設置位和壓縮。它們應該足夠大，以便爲編碼器提供足夠的數據以實際編碼（64KB？）。你可以像使用Deflate或LZMA（7-zip）一樣使用任何壓縮算法。

將傳入位暫時放入列表中。一旦該列表填滿（可能佔用1MB空間？），您需要將這些位複製到位圖的各個部分。這樣做後，你可以清除列表。該列表只是一個臨時緩衝區，允許將每個部分的許多更新分批到一個解壓縮壓縮循環。

在寫出位之前，按部分和位置對它們進行排序。這允許您清除重複項並僅處理所有部分一次。

請注意，無法保證，甚至可以進行壓縮。如果沒有可壓縮模式，則不可能壓縮。

Answer 2

我們通過Roaring位圖獲得了不錯的結果：http://roaringbitmap.org/