我有一個信息檢索應用程序，它創建了10萬位數量級的位數組。陣列中「置位」位的數量差別很大，從所有清除到所有設置。目前，我正在使用一個簡單的位陣列（java.util.BitSet），因此我的每個位陣列都需要幾兆字節。什麼是位陣列的一些替代方案？
我的計劃是看第一個位的基數，然後決定剩下的數據結構。顯然有些數據結構對於非常稀疏的位數組更好，而另外一些數據結構對大約一半的位進行設置（當設置了大多數位時，我可以使用否定將其視爲稀疏零集）。
這裏有一些約束或提示：
對開源Java實現有幫助，但並非絕對必要。我對基本面更感興趣。
除非數據是真正隨機和具有對稱分佈1/0，那麼這簡單地成爲無損數據壓縮的問題，是非常類似於CCITT第3組壓縮用於黑白（即：二進制）傳真圖像。 CCITT Group 3使用霍夫曼編碼方案。在傳真的情況下，他們使用一組固定的霍夫曼編碼，但對於給定的數據組，您可以爲每個數據組生成一組特定的編碼，以提高所實現的壓縮比。只要您只需按順序訪問這些位，就像您所暗示的那樣，這將是一個非常有效的方法。隨機訪問會產生一些額外的挑戰，但是您可能會爲數組中的各個偏移點生成一個二叉搜索樹索引，以便您可以靠近期望的位置，然後從那裏進入。
注：霍夫曼方案仍然運作良好，即使數據是隨機的，只要1/0的分佈並非完全均勻。也就是說，分佈越不均勻，壓縮比越好。
最後，如果這些比特是真正的隨機均勻分佈，那麼，根據先生克勞德香農，你將無法使用任何方案壓縮它的任何重要數額。
直接向前無損壓縮是要走的路。爲了使其可搜索，您必須壓縮相對較小的塊併爲塊的數組創建索引。該索引可以包含每個塊中起始位的位偏移量。
快速組合學證明你真的不能節省多少空間：
假設你有設置爲1，n個比特總數的N/2位的任意子集。你有（n選擇n/2）的可能性。使用Stirling's formula，這大致爲2^n/sqrt（n）* sqrt（2/pi）。如果每種可能性都是相同的可能性，那麼就沒有辦法讓更短的選擇更短的選擇。所以我們需要log_2（n選擇n/2）位，大約是n - （1/2）log（n）位。
這不是很好的節省內存。例如，如果您使用n = 2^20（1 meg），那麼您只能保存大約10位。這是不值得的。說了這麼多，任何真正有用的數據真的是隨機的似乎也不太可能。如果您的數據有更多結構，則可能會有更樂觀的答案。
感謝您的答案。這是我要嘗試動態選擇正確的方法：
我會收集所有的第一個N命中傳統的位陣列，並選擇三種方法之一，基於對稱性這個樣本。
不對稱，中度和對稱區域之間的邊界將取決於通過針對他們所需要的空間，在那裏的時間與空間中的相對值將是一個可調節的參數平衡的各種算法所需的時間。霍夫曼編碼所需的空間是對稱性的函數，我將通過測試進行分析。另外，我會測試所有三種方法來確定我實現的時間要求。
這是可能的（實際上我希望）中間壓縮方法總是比列表或位列陣或兩者都好。也許我可以通過選擇一組適用於更高或更低對稱性的霍夫曼編碼來鼓勵這一點。然後，我可以簡化系統，並使用兩種方法。
還有一個壓縮的思考：
如果該位陣列是不是瘋了多久，你可以嘗試使用任何重複編碼，如Huffman之前應用Burrows-Wheeler transform。一個幼稚的實現會在（解壓縮）和O（n^2 log n）時間內解壓縮到O（n^2）內存 - 幾乎可以確定有快捷方式。但是如果你的數據有任何順序結構，這應該可以幫助Huffman編碼。
您也可以將該想法一次應用於一個塊，以保持時間/內存使用更實用。如果按順序讀取/寫入，在時間使用一個塊可以讓您始終保持大部分數據結構壓縮。
我會強烈考慮使用範圍編碼來代替霍夫曼編碼。一般來說，範圍編碼可以比霍夫曼編碼更有效地利用不對稱性，但是當字母大小非常小時尤其如此。事實上，當「本地字母表」僅僅是0和1時，霍夫曼可以完全壓縮的唯一方法就是將這些符號組合起來 - 這更符合範圍編碼的要求。
謝謝Antaeus，我實際上已經研究過範圍編碼，因爲接受的答案引用了霍夫曼編碼作爲無損壓縮的一個例子。不過，霍夫曼很容易實現，並且在適度不對稱的輸入上運行良好。對於高度不對稱的輸入，遊程長度方法很好。 – erickson 2008-09-18 05:02:21
對你而言可能已經太遲了，但是對於基於try的稀疏位數組（無損）和其他數據類型，有一個非常快速和高效的內存庫。看看Judy arrays
謝謝比爾。我記得以前聽說過Judy陣列，但我完全忘記了它們。我會再看看他們。 – erickson 2009-06-17 18:03:04
美麗的解決方案。它可能甚至會很快，因爲今天的內存負載如此昂貴。 – 2008-10-05 15:16:15