読者です 読者をやめる 読者になる 読者になる

Javaで簡潔ビットベクトル(32)

Java

RRRの完備辞書を実装した。

https://code.google.com/p/sbvj/

境界付近は相変わらず怪しいかもしれないですが、ある程度は動くはずです。

文字列本のp.52-54を参考にしつつ、以下の論文の方法で実装しました。

Fast, Small, Simple Rank/Select on Bitmaps
Gozalo Navarro, Eliana Providel, SEA'12, 2012.

めっちゃでかいブロックを使って絞り込んで、必要な部分のビット列は、要求時に復元すると良いみたいです(テーブルを使わない)。そうすると、サイズをかなり小さく抑えつつ、まぁまぁ高速にrank操作とselect操作を実行できるようです。

実際、疎な完備辞書とRRRの完備辞書は、元のビット列が不要なので、かなり圧縮できます。

あぁ、眠い。