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

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

Java

密なビットベクトル、疎なビットベクトル、偏りのあるビットベクトルのそれぞれに対して完備辞書をJavaで作って公開している。

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

今後、改良する点もあるかと思うが、現在の実装でrankとselectの性能を測定した結果を報告しておこうと思う。
現在の最新バージョンは、0.0.2.6だ。

まず、各ビルドタイプは、以下のような対応となっている。

  • 密なビットベクトル(BuildType.SIMPLE)
  • 疎なビットベクトル(BuildType.SPARSE)
  • 偏りのあるビットベクトル(CS_RRR)

ここで、それぞれの特徴について軽く述べておく。完備辞書は、次の2種類に分けられる。PlainタイプとCompressedタイプだ。この2つの違いは、Plainタイプが元のビットベクトルを保持しているのに対して、Compressedタイプが元のビットベクトルを保持していないことである。Plainタイプは、補助データ構造を利用してaccessとrankとselectを高速に実行することができるが、元のビットベクトルを保持していることから、1の数が疎な場合に、無駄な領域が多く発生する。一方、Compressedタイプは、元のビットベクトルを保持しておらず、補助データ構造のみで、accessとrankとselectを実行する。このため、Plainタイプよりも遅くなる。しかし、1の数が疎であったり、偏りがあったりすると、元のビットベクトルのサイズよりも小さいサイズを実現できる。この2種類の観点で分類すると、BuildType.SIMPLEはPlainタイプであり、BuildType.SPARSEとBuildType.CS_RRRは、Compressedタイプである。

さて、密なビットベクトルと疎なビットベクトルについては、なんとなく用途も想像がつくと思う。ただ、偏りのあるビットベクトルは、どこで使うのか?なぜ重要なのか?が最初はわからなかった。しかし、BWTしたテキストをウェーブレット木(行列でもいいよ)で扱った時(つまり、FM-Index)に、理解できた。BWTしたテキストというのは、以下のような感じである。

原文:
Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, 'and what is the use of a book,' thought Alice 'without pictures or conversation?'
BWT:
',etf,esea,grrootefyksdttndgeddr:ssedtoserrfnos'yggreterd?,  tkgkon _ hhe 'bwwhssh      inii  iieaneana chhhscchcrprpbethhtvvvrrgooonnnnn ue  w ttst  tttglwlpp tvhndg ttt ss  wsonoAAioooaaiiiiinai  oioottntd   oo i iccbb   nhhe   ooeeeoe iuueeeaneeairru    iihiauueiss   o itaa   nicc ott bonn a   t'br

こんな感じで、明らかに文字が偏って出現する。なので、ウェーブレット行列の各高さのビットベクトルを偏りのあるビットベクトルの完備辞書で保持すれば、Plainタイプの完備辞書よりかなり小さくなる(やってみればわかる)。これは、Implicit Compression Boostingと呼ばれている方法であり、BWT後の文字列をBとすると、nH0(B)の0次経験エントロピーよりも小さいnHk(B)のk次経験エントロピーで格納できる(だったはず)。以下が、参考文献です。

http://www.dcc.uchile.cl/~gnavarro/ps/spire07.3.pdf

とまぁ、こんな感じで、完備辞書は、簡潔データ構造の基礎なので、何種類か実装を理解しておくと、ウェーブレット木やFM-Indexを扱う時に楽になる。

本題ですが、私の環境で測定した結果を書いておきます。まず、測定環境です。

CPU    : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
Memory : 16GB
OS     : Windows 7 64bit

次に測定条件です。

ビットベクトルサイズ          : 2^28
rank & select実行回数(random) : 1000万回

最後に測定結果です。まず、rankの性能です。

# 1の割合 SIMPLE CS_RRR SPARSE
1 0.01 1.542154762 3.751962903 3.737345081
2 0.03 1.373564948 4.519035638 4.59353391
3 0.05 1.54800724 4.74587686 5.069132826
4 0.1 1.496778307 5.054930195 6.687485811
5 0.2 1.545209135 5.305062216 7.065308719
6 0.25 1.434685995 5.692176377 8.212223089
7 0.5 1.581052065 5.970882537 8.594491492
8 0.75 1.478702739 6.076322934 7.16602154
9 0.9 1.471521029 5.99340702 7.229551626

※単位は、secです。

次に、selectの性能です。

# 1の割合 SIMPLE CS_RRR SPARSE
1 0.01 3.94232768 4.652050295 1.977224225
2 0.03 3.862746976 4.968211322 2.600507869
3 0.05 4.036338049 5.16257779 2.850900824
4 0.1 3.941578471 5.342181198 4.142645526
5 0.2 3.987266552 5.745070116 4.592851567
6 0.25 3.918262793 5.785488852 5.084727825
7 0.5 3.903043798 6.089801238 5.347104083
8 0.75 3.924702758 6.320591592 4.189356501
9 0.9 3.891973291 6.24452959 4.201911433

※単位は、secです。

測定方法によっても変わると思うので、参考程度でお願いします。