1

私はいくつかのブルーム フィルター バリアントの実装に取り​​組んでいます。このための非常に便利なデータ構造は、コンパクトなマルチビット配列です。つまり、各要素が約 4 ビットのコンパクトな整数である配列です。

ここではスペース効率が最も重要なので、単純な整数配列で必要な機能が得られますが、必要以上に大きくなります。

ビット演算を使用してこの機能を自分で実装しようとする前に、そのようなデータ構造を既に提供しているライブラリを誰かが知っているかどうか疑問に思っていました。

編集：静的サイズは問題ありません。理想的なケースは、セルあたりのビット数に関して柔軟な実装です。ただし、それは少し期待できるかもしれません（しゃれた意図はありませんか？）。

4

2 に答える 2

1

http://code.google.com/p/javaewah/が提供する圧縮された BitSet を見てください。ビットを自由に設定でき、圧縮アルゴリズムを使用してメモリを効率的に使用できます。

つまり、次のようなもの

        EWAHCompressedBitmap32 set = new EWAHCompressedBitmap32();
        set.set(0);
        set.set(1000000);

Java BitSetのように1 MBではなく、数バイトしか占有しません...

それに応じてインデックスを BitSet に乗算することにより、4 ビット整数を BitSet にマップできるはずです。

于 2015-07-10T11:38:59.160 に答える