整数のスパース セット (実際には C メモリ アドレス) をコンパクトで高速な方法で表現する良い方法は何ですか。ビットベクトルやランレングス エンコーディングなどの明らかなことについては、すでに知っています。しかし、セット要素ごとに 1 つの単語よりもはるかにコンパクトなものが必要です。要素を追加および削除し、メンバーシップをテストする必要があります。ユニオンのような他のセット操作は必要ありません。
何年も前にそのような図書館について読みましたが、その名前を忘れてしまいました。HPによってオープンソースとしてリリースされ、女性の名前が付けられたと思います。
あなたはジュディアレイについて言及しています。HP企画でした。Rubyで使用され、cで利用できると思います。非常に興味深いデータ構造。割り当てが (少なくとも) 単語にアラインされているという事実を利用して、密な範囲と疎な範囲に別々の構造を持っています。
非常にコンパクトなデータ構造は、ブルーム フィルター、おそらく削除をサポートするカウンティング ブルーム フィルターになります。
http://en.wikipedia.org/wiki/Bloom_filter
1970 年に Burton H. Bloom によって考案されたブルーム フィルターは、要素がセットのメンバーであるかどうかをテストするために使用されるスペース効率の高い確率的データ構造です。偽陽性は可能ですが、偽陰性はそうではありません。要素をセットに追加することはできますが、削除することはできません (ただし、これはカウント フィルターで対処できます)
挿入、削除、およびメンバーシップのテストだけが必要な場合は、ハッシュ テーブルが適しています。32 ビット整数をハッシュするための優れたハッシュ関数をいくつか見つけることができます。
構造をデータセットよりも小さくしたい場合は、おそらくある種のツリー配置を検討する必要があります。4 ウェイ ツリーの各レベルを上限から 2 ビットでキーオフすると、かなりうまく圧縮される可能性があります (ポインターにある程度の空間的局所性がある場合)。トリックは、それを十分にコンパクトにエンコードすることです（ノードの配列へのインデックス？配列マップツリー？）。