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

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

Java

疎なビットベクトルに対する完備辞書を作ってみました。以下で公開しています。

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

以下のようにして使えます。

public void test001() throws SuccinctBitVectorException {
    long sbvSize = 64;
    SuccinctBitVector sbv = new SuccinctBitVector(sbvSize);
    
    sbv.setBit(0, 1);
    sbv.setBit(6, 1);
    sbv.setBit(21, 1);
    sbv.setBit(23, 1);
    sbv.setBit(28, 1);
    sbv.setBit(41, 1);
    sbv.setBit(45, 1);
    sbv.setBit(60, 1);
    
    sbv.build(BuildType.SPARSE);
    
    long select = sbv.getSelect(0, 1);
    assertThat(select, is(0L));
    select = sbv.getSelect(1, 1);
    assertThat(select, is(6L));
    select = sbv.getSelect(2, 1);
    assertThat(select, is(21L));
    select = sbv.getSelect(3, 1);
    assertThat(select, is(23L));
    select = sbv.getSelect(4, 1);
    assertThat(select, is(28L));
    select = sbv.getSelect(5, 1);
    assertThat(select, is(41L));
    select = sbv.getSelect(6, 1);
    assertThat(select, is(45L));
    select = sbv.getSelect(7, 1);
    assertThat(select, is(60L));
}

参考にしたのは、いつものように以下の本です。

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

ステマみたいになってしまっているけど、実際に良い本なので、オススメです。
ただ、実装力がある程度ないとコードにするのは難しいかもしれません。

疎なビットベクトルの話は、p.49-p.52まであります。
ただ、rankの説明のtの記述は間違っていると思う。

テストケースは簡単なやつしか消化していないので、境界付近は怪しいかもしれません。
もうちょっとテストして、品質を上げてからまたアップロードします。

ウェーブレット行列やFM-Indexで使おうと思うと、最終的にファイルに保持したいと思うので、次は、Serializableインターフェースをサポートしたいと思います。