表示稀疏整數集？

Question

什麼是以緊湊和快速的方式表示稀疏整數集合（真正的C內存地址）的好方法。我已經知道比特向量和遊程編碼等明顯的東西。但我想要的東西比每個集合元素的一個詞更緊湊。我需要添加和刪除元素並測試成員資格。我不需要其他集合操作，比如聯合。

很多年前我讀過一個這樣的圖書館，但後來忘記了它的名字。我認爲它是由惠普公開發布的，並且有一個女人的名字。

Answer 1

您指的是judy數組。這是一個惠普項目。我認爲它們用於紅寶石，並且可以在c中找到。非常有趣的數據結構。利用分配（至少）字對齊的事實，具有密集和稀疏範圍的單獨結構。

http://judy.sourceforge.net/index.html

Answer 2

如果您只需要插入，刪除和測試成員資格，那麼散列表應該很適合您。你可以找到一些散列函數來散列32位整數here。

Answer 3

如果你想要的結構比數據集小，你應該看看某種樹排列。使每個級別的4位樹鍵從高位開始關閉2位，並且可能壓縮得相當好（如果指針具有任何空間局部性）。這個技巧將足夠緊湊地編碼（索引到節點數組中？一個數組映射樹？）。

Answer 4

一個非常緊湊的數據結構可能是bloom過濾器，也許是一個計數bloom過濾器來支持刪除。

http://en.wikipedia.org/wiki/Bloom_filter

布隆過濾器，通過伯頓布魯姆於1970年構思，是用於測試一個元素是否是一組的成員的空間效率的概率數據結構。假陽性是可能的，但是假陰性不是。可以將元素添加到集合中，但不能刪除（儘管可以使用計數過濾器來解決此問題）