其編碼我有一種特殊的需要，最重要的擔憂是：算法：巨大的數量非常稀少位陣列，使用
- 內存
- 非常低內存佔用
- 速度
這是我的「問題」：我需要在內存中存儲大量非常稀疏的位數組。這些bitset是「僅附加」，主要用於交叉點。巨大的，我的意思是高達20萬位陣列。
每個位集的範圍應在[0 ... 16 000 000]之間。
我進行了一些測試前與「唯一」包含一些實際的數據我有10個673比特串，得到了以下結果：
1% of the bit arrays ( 106 bit arrays) Hamming weight: at most 1 bit set
5% of the bit arrays ( 534 bit arrays) Hamming weight: at most 4 bits set
10% of the bit arrays (1068 bit arrays) Hamming weight: at most 8 bits set
15% of the bit arrays (1603 bit arrays) Hamming weight: at most 12 bits set
20% of the bit arrays (2137 bit arrays) Hamming weight: at most 17 bits set
25% of the bit arrays (2671 bit arrays) Hamming weight: at most 22 bits set
30% of the bit arrays (3206 bit arrays) Hamming weight: at most 28 bits set
35% of the bit arrays (3740 bit arrays) Hamming weight: at most 35 bits set
40% of the bit arrays (4274 bit arrays) Hamming weight: at most 44 bits set
45% of the bit arrays (4809 bit arrays) Hamming weight: at most 55 bits set
50% of the bit arrays (5343 bit arrays) Hamming weight: at most 67 bits set
55% of the bit arrays (5877 bit arrays) Hamming weight: at most 83 bits set
60% of the bit arrays (6412 bit arrays) Hamming weight: at most 103 bits set
65% of the bit arrays (6946 bit arrays) Hamming weight: at most 128 bits set
70% of the bit arrays (7480 bit arrays) Hamming weight: at most 161 bits set
75% of the bit arrays (8015 bit arrays) Hamming weight: at most 206 bits set
80% of the bit arrays (8549 bit arrays) Hamming weight: at most 275 bits set
85% of the bit arrays (9083 bit arrays) Hamming weight: at most 395 bits set
90% of the bit arrays (9618 bit arrays) Hamming weight: at most 640 bits set
95% of the bit arrays (10152 bit arrays) Hamming weight: at most 1453 bits set
96% of the bit arrays (10259 bit arrays) Hamming weight: at most 1843 bits set
97% of the bit arrays (10366 bit arrays) Hamming weight: at most 2601 bits set
98% of the bit arrays (10473 bit arrays) Hamming weight: at most 3544 bits set
99% of the bit arrays (10580 bit arrays) Hamming weight: at most 4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set
看涉及的人數，我顯然需要使用壓縮這不是一個問題：它應該容易處理，看到位陣列是「僅附加」的。
打開的位陣列位有點分組，但不完全。所以你會傾向於在同一區域有幾個位（但通常不是一個接一個，因此RLE對於位不是很好）。
我的問題是使用什麼樣的壓縮？
現在我不知道我是應該在這裏還是在回答我自己的問題。
基本上我使用一個非常啞編碼想象「最壞情況」的場景：
1比特：如果上，下面的5個比特確定需要多少位來計算「跳過」，如果關閉，優化：以下5位決定了字面上的字節數（即「開」或「關」），而不會跳過[只有在確定比其他表示更高效時纔會切換到此位當它開始運行時，它總是一個優化（size-wise）]
5位：我們可以在下一個bi之前跳過多少位噸上
x比特：跳過
下面是一個例子：比特陣列具有3比特組，第一位是在3 098 137中，第二，在3 098 141和3中的第三098 143.
+-- now we won't skip
|
| +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
| | +--- 3 098 141 is on
22 3 098 137 | 3 | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc.
首先打開告訴我們要跳過位。 5個位（總是5）告訴我們需要多少位來告訴我們將跳過多少位 22位告訴跳到3 098 137 一位關閉告訴我們現在不在跳過位 5 next bits（始終5）告訴我們有多少位會讀「原樣」 6位：關，關，關，開，關，就意味着3 098 141和3 098 143上 等
看到了驚人的這些位陣列的稀疏性，這似乎相當大的效率。所以使用這種編碼，我拿走了我的樣本數據，並計算了一個「最壞情況」的情況（我還沒有寫出算法，我寧願從這裏輸入一些數據）：基本上我認爲不是隻有「大小優化」永遠不會踢和，也即5位總是被設置爲它們的最大值（24位），這當然是不可能發生的。
我這樣做只是擁有的「最壞最壞的」情況可能是什麼一個非常粗略的近似。
我感到很驚喜：
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
的數據是實際的數據，所有的數據是相似的，我知道，如果損壞程度嚴重，我可以存儲我的200個000位陣列，約240 MB，這很好。
我敢肯定，實際的編碼將涉及到比那少，但我還沒有實際寫入它，我只能（很容易）計算「最壞情況」這就是爲什麼我只能說明一。對於如何使這種尺寸效率更高的任何提示/想法（記住這些是超級稀疏的位數組，它們應該有成千上萬的數組，它們必須在內存中，並且它們應該是「僅追加「）？
關於我的「追加，只有」的情況下
基本上我有一個不斷增長的「遼闊」（範圍，但「無垠」是實際刑期按我的理解）和很多位陣列都有一些位集。當範圍從0到1 000 000時，所有的位數從0到1 000 000到。當範圍增長到1 000 001時，所有的位陣列也都在增長，一點一點地增長。但是，大多數這些位陣列將有一個「0」附加在其端部，而所述位陣列的約4至8將具有「1」所附在其端部。但是，我無法預測哪個位數組會附加0或1。所以我有很多位數組都有相同的大小，都非常稀疏（< 0.5％的位設置），並且隨着範圍增長「都在增長」（所以它們「總是以同樣的速度增長）。
Judy arrays很好。但幾年前我就讀過他們，那些東西「超出我的頭腦」。朱迪陣列是C-only 20KLOC庫，我絕對不會重新實現它。但他們很棒。
所以我想我需要補充，我想這一切都留比較簡單，這是不是牽強看到的特殊的「只追加」我非常稀疏比特串的財產。
注意有關重新發明輪子的意見可發送到*的/ dev/null的*：如果只爲它背後的數學/挑戰我想自己實現這一點。無論如何，我會很驚訝地發現一個能夠處理內存中200 000個「僅追加」位陣列的輪子。但是如果你有一個，它後面的機制讓我感興趣:) – SyntaxT3rr0r 2010-11-01 23:28:12
有理論對編碼密度的限制：對於N個元素的陣列，其中n個被設置，要編碼的最小位數將是-n * log2（n/N） - （Nn）* log（1-n/N）。對於其中設置了16M的53153的陣列，這將是514k位，並且對於4992位設置 - 65kits。讓你的記憶更接近這個極限，你必須選擇更復雜的編碼。 – Vovanium 2010-11-02 19:25:58
@Vovanium，我認爲你爲你的理論極限排除了一些必要的上下文（比如，關於比特分佈設置的某種統計假設？） – comingstorm 2010-11-04 16:57:23