Hatena::ブログ(Diary)

WebService::Blog->new( user => ’hide_o_55’ )

2014-07-20

LOUDS Trie ライブラリを書いた

C++ で LOUDS Trie を扱うライブラリhsds::Trieを書きました。

no title

LOUDS Trieとは?

Level-Order Unary Degree Sequence という木構造を表現するデータ構造を利用したTrie木です。

Space-efficient Static Trees and Graphs

hsds::Trie の機能

現在は以下の機能をサポートしています。

  • 木のノードレベルでの探索(traverse)
  • 完全一致検索(exactMatchSearch)
  • 共通接頭辞検索(commonPrefixSearch)
  • クエリ文字列を接頭辞に含む全てのキーを列挙(predictiveSearch)
  • ノードIDからキー文字列の復元(decodeKey)
  • Trieのファイル書き出し、読み込み、mmap
  • TAIL配列の圧縮

特に、traverse は私のユースケースでは重要なのですが、tx-trie、ux-trie 等のLOUDS Trieの実装では提供されていませんでした。

なお、hsds::Trieでは内部で使用する簡潔ビットベクトルの実装として、以前作成した簡潔ビットベクトルライブラリを採用しています。

パフォーマンス

しっかりしたベンチマークはまだとっていませんが、ランダム文字列の共通接頭辞検索でux-trieの3倍以上の速さでした。

これは使用している簡潔ビットベクトルの速度の差によるものと考えています。

2013-05-28

簡潔ビットベクトルライブラリを書いてみた

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

no title

簡潔データ構造とは?

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

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

完備辞書(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と同等の速度になりました。