Bep: 大規模コレクション向けの連想配列

概要

Bepは大規模なコレクションからなる連想配列を扱うためのライブラリです．連想配列は文字列からなるキーを利用して任意のオブジェクトを登録・参照できるデータ構造です．C++ではSTL map, hash_mapなどが知られていますが，数千万から数億個のコレクションを処理する場合，使用メモリ量が非常に大きくなってしまう問題点がありました．Bepは内部に最小完全ハッシュ関数を利用し，従来の実装に比べ少ない作業領域量でコレクションを保持します．キー自体を除けば，1keyあたりの作業領域量は約3bitです（全体では，(keyを全てつなげた長さ) + (3/8*key種類数)バイト必要です）

ダウンロード

Bepはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます.

bep-0.01.tar.gz: HTTP

更新情報

2007-10-27: Bep 0.01
- 0.01をリリースしました

使い方

ソースコードで配布しています。上記をダウンロードからダウンロード後、次の通りにするとインストールできます．xxには適切なバージョン番号を入れて下さい．make install時に管理者権限が必要な場合があります．その場合はsudo make install などしてください．

% tar xvzf bep-0.xx.tar.gz
% cd bep-0.xx
% ./configure
% make
% make install

ライブラリのみ使いたい場合は#include をプログラムにつけ-lbepオプションをつけてコンパイルしてください。

ライブラリとして使う例は、bep_driver.cpp bhash_driver.cppを参照してください．

サンプルプログラムの説明

bep_driver

% ./bep_driver wordlist index

各行にキーが書かれたwordlistファイルから読み込みBepを構築します．各キーには0から順に通し番号をつけます．また，indexに保存、またそこから読み込み，正しく書き込み，読み込みがされているかをチェックします．

bhash_driver

% ./bhash_driver wordlist index

各行にキーがかかれたwordlistファイルから読み込み，indexに保存します．bhash::lookup_wocheck, bhash::lookup, tr1::unordered_mapの速度比較を行います．

使用例

% cat wordlist
1999年のオールスターゲーム
1999年のコンピュータゲーム
1999年のサッカー
1999年のシングル
...
% wc wordlist
  3775712   3805231 224432799 wordlist
  
% ./bep_driver wordlist index
n:1048576 bn:1363146
n:2097152 bn:2726295
n:3145728 bn:4089444
n:3775712 bn:4908423
read 3775712 keys
3.3642 0.8910 usec

% ./bhash_driver wordlist index
n:3775712 bn:4908423
read 3775712 keys
lookup_wo 1.713607 key:0.453850 usec
lookup    3.365828 key:0.891442 usec
tr1umap   2.279891 key:0.603831 usec

メソッドの説明

bep_tool::bep (連想配列)

int bep_tool::bep::build(vector<string>& keys, vector<valType>& vals)
第一引数のkeysに各valsが対応するような連想配列を構築します．構築に成功した場合は0を返し，構築に失敗した場合は-1を返します．これらのキーは必ずしもソートされている必要はありません。既に連想配列を保持している場合は，その連想配列は破棄されます．構築に失敗する場合としては，キーに重複キーが含まれている場合，また完全ハッシュ関数の構築に失敗した場合です（その場合はダミーキーを加えるなどしてもう一度構築してみてください）．

int bep_tool::bep::save(const char* fileName, valType*& vals)
現在保持している連想配列をfileNameに書き込みます．成功した場合は0を返し，失敗した場合は-1を返します．
注意: bep::saveは値は保存しません．値が任意の型をとれるため，bepが値をどのように保存すればよいか分からないからです．そのため，bepが保持していた値はvalsで返します．返された個数はbep::size()で得られます．bepのユーザーはvalsを自分で保存する必要があります（loadも同様)

int bep_tool::bep::load(const char* fileName, valType*& vals)
bep::saveでfileNameに保存してある連想配列を読み込みます．成功した場合は0を返し，失敗した場合は-1が返ります．
注意: bep::loadは値を読み込みません．値が任意の型をとれるため，bepがどのように保存すればよいか分からないからです．そのため，save時に返されてきたvalsを引数で渡す必要があります．この時，valsの中での順番が守られている必要があります．

valType& bep_tool::bep::operator [](const string& key)
keyで結び付けられた値を返します．もし，連想配列にkeyが含まれていない場合は，新しいキー，要素のペアを作ります（STL mapと同様）

bool bep_tool::bep::exist(const string& key)
keyで結び付けられた値があるかを調べます．ある場合はtrue，無い場合はfalseを返します．

size_t bep_tool::bep::size() const
登録されているキーの数を返します．

bep_tool::bhash (最小完全ハッシュ関数)

bhashはbep内部で使われている最小完全ハッシュ関数を操作するクラスであり直接使うことも可能です．最小完全ハッシュ関数は，(1)（登録した）キーは衝突しない，(2)返されるハッシュ値は[0...キー種類数-1]が保障されているような関数です．あらかじめ使うキーを用意し構築することが必要です．

int bep_tool::bep::build(const vector& keys)
keysに対する最小完全ハッシュ関数を構築します．構築に成功したら0、失敗したら-1が返されます．keysはソートされている必要がありませんが、重複がある場合は構築に失敗します（前もって除いておいてください）

int bep_tool::bhash::save(const char* fileName) const
現在保持しているハッシュ関数をfileNameに保存します．成功した場合は0を返し，失敗した場合は-1を返します．

int bep_tool::bhash::load(const char* fileName);
ハッシュ関数をfileNameから読み込みます．成功した場合は0を返し，失敗した場合は-1を返します．

bep_tool::ub4 bep_tool::bhash::lookup(const string& key) const;
keyに対するハッシュ値を返します．全てのハッシュ値が衝突しないことが保障されており，返される値は[0...bhash::size()-1]のどれかになります．もし構築時に無かったキーが渡された場合はbep_tool::NOTFOUNDが返されます．

ub4 bep_tool::bhash::lookup_wocheck(const string& key) const;
keyに対するハッシュ値を返します．登録済みのキーに対するハッシュ値が衝突しないことが保障されており，返される値は[0...bhash::size()-1]のどれかになります．構築時に無かったキーが渡された場合も[0...bhash::size()-1]のどれかの値が返されます．キーチェックがlookupと比べ少ないので高速に処理を行うことができます．

bool bep_tool::bhash::lookupKey(const size_t i, string& key) const;
もしi < bhash::size() ならばハッシュ値iを持つキーをkeyに渡しtrueを返します．もしi>=bhash::size()ならばfalseが返されます．

ub4 size() const;
現在登録済みのキーの数を返します．

性能評価

TODO

注意

Bepは(キー, 値）のペアをまとめて登録する(bep::build)場合に最適化されており，一個ずつ新しいキー/値を登録するのは単純につくっています（一定個数までmapで保存しておいて、たまに一から全部作り直す）．パフォーマンス重視の場合はできる限りbep::buildを使うようにしてください．

TODO

ポータビリティ向上（今の実装は64bi Intel系でしか動かない)
インターフェースをきちんと作る
性能評価（クエリに関する速度評価）
ソースにコメント書く
解説文書の充実
高速化、省メモリ化
hatena keywordなどのアプリケーション例を充実させる

その他

別府で作ったので、その名前がついています。

参考文献, リンク

Bep, Txの内部で使われている技術についての解説発表です (pdf|ppt)
キー自体に対し共通接頭辞探索など高度な命令を利用する場合には，Trieからなるデータ構造を試してください（tx, darts ）
Botelho, F.C., Pagh, R. and Ziviani, N. "Simple and Space-Efficient Minimal Perfect Hash Functions" 10th International Workshop on Algorithms and Data Structures (WADS07) August 2007, 139-150. pdf
Darts: Trieではよく使われている実装でDouble Arrayを用いてTrieを構築します。
Bob's Hash 実際に利用した64bit版のコード

連絡先

コメントやバグ報告などありましたらこちらまで
Daisuke Okanohara (hillbig ＠ is.s.u-tokyo.ac.jp) (全角＠を半角@に直してください）

Bep: Associative Arrays for Very Large Collections

概要