簡潔ビットベクトルライブラリを書いてみた - WebService::Blog->new( user => ’hide_o

簡潔データ構造の勉強がてら、各種簡潔データ構造の核となる簡潔ビットベクトルを扱うC++ライブラリを書いてみました。

GitHub - hideo55/cpp-HSDS: Succinct Data Structure Library Collection.Includes bit-vector/wavelet-matrix/trie.

簡潔データ構造とは？

簡潔データ構造とは、データ構造を最適に近いサイズで保存しつつ、インデックスを利用して高速な操作を実現するデータ構造のことです。

簡潔ビットベクトルとは？

完備辞書(Fully Indexable Dictionary, FID)とも呼ばれます*1。
簡潔ビットベクトルはビットベクトルに対する簡潔データ構造で、ビットベクトルに対して以下の操作が可能なデータ構造のことを指します。

access(i): ビットベクトルのi番目の値を返す
rank(i): 先頭からi番目までの1(または0)の数を返す
select(i): i番目に出現する1(または0)の位置を返す

簡潔ビットベクトルは他の簡潔データ構造の基礎となるものなので、簡潔ビットベクトルの性能が簡潔データ構造の性能を左右します。

作ったライブラリについて

marisa-trie における rank/select の実装 - やた＠はてな日記

この辺を見て作ったので、rank辞書、select辞書も持ち方などmarisa-trieの簡潔ビットベクトルと似た実装になっています。
大きな違いは以下の通りです。

CMake

ビルドツールとしてAutotoolsではなくCMakeを使用しています。

64-bit整数を使用

marisa-trieの簡潔ビットベクトルでは32-bit 環境における性能の劣化を防ぐために64-bit 整数を使用してしませんが、自分で使う環境は64-bit環境なので64bit整数を使っています。

std::vectorを使用

marisa-trieの簡潔ビットベクトルでは独自のベクトル型コンテナクラスを使っていますが、HSDSで必要とする機能にはstd::vectorで十分だったため、std::vectorを使っています。

値のセット方法

marisa-trieでは、値のセットはpush_back()で末尾に追加する形になりますが、HSDSではset()によって任意の位置に値をセットできます。

mmap非対応

marisa-trieはmapper()というインタフェースでファイルに保存した簡潔ビットベクトルにmmapによるアクセスができるようになっていますが、HSDSは現在は対応していません。

使用方法

インストール

$ git clone git://github.com/hideo55/cpp-HSDS.git
$ cd cpp-HSDS
$ cmake .
$ make && make install

コード

#include "hsds/bit-vector.hpp"

using namespace hsds;

void main(){
    BitVector bv;
    bv.set(0, true);
    bv.set(100, true);

    bv.build();

    uint64_t pos = bv.select1(0)// 0;
    pos = bv.select1(1)// 100;
    pos = bv.select0(0)// 1;
}

ビルド

$ g++ foo.cpp -o foo -lhsds-bitvector

APIに関しては、以下のDoxygenで生成されたドキュメントを参照下さい。
APIドキュメント

ベンチマーク

ux-trie、marisa-trieと共にベンチマークを行った結果は以下にまとめてあります。

簡潔ビットベクトル-ベンチマーク結果

HSDSとmarisa-trieのrank、selectはほぼ同等の速度でした。getはmarisa-trieが桁違いに速いですが、marisa-trieこれはデバッグビルド以外では引数のチェックをしないようになっているためで、HSDSでも引数チェックをコメントアウトして試してみたところ、marisa-trieと同等の速度になりました。

*1:高速文字列検索の世界等で