【名前】
- mphf


【概要】
- 最小完全ハッシュ関数(Minimal Perfect Hash Function)のライブラリ
- 数百万から一億個程度のキーに対して、一意なIDを手軽に付与することが目的


【バージョン】
- 0.0.3


【ビルド方法】
$ make


【ビルド環境】
- gcc-4.2.4
- linux(POSIX)


【コマンド】
== mkmphf: 
    - MPHF生成コマンド
$ mkmphf [--mapping-loop-limit=<N>] [--hash-code-scale=<D>] [--hash-seed=<N>] <index> <keyset>
--mapping-loop-limit=<N> := マッピングステップの試行回数。 デフォルトは32
--hash-code-scale=<D>    := ハッシュ値の最大値を算出するためのスケール。 デフォルトは2.09  ※ D > 2.0 である必要がある
--hash-seed=<N>          := ハッシュ関数生成時に用いられる乱数のシード。 省略された場合はtime(NULL)の値が用いられる。
index                    := 生成されるMPHFインデックス
keyset                   := 入力キーセット。改行区切り


== mphf: 
    - ハッシュ値計算コマンド
    - 標準入力よりキーを読み込み、標準出力にそのハッシュ値を出力する
$ mphf <index>
index := mkmphfコマンドが生成したMPHFインデックス


== test_mphf: 
    - テストコマンド
    - 標準入力よりキーリストを読み込み、それらに対して一意なハッシュ値を生成しているかどうかをテストする 
$ test_mphf <index>
index := mkmphfコマンドが生成したMPHFインデックス


【API】
class MPHF::Generator;
class MPHF::Hash;
# TODO:


【備考】
- mkmphfコマンドの使用メモリ量: keyset.size*8 + max_hash_code + α byte => 約 keyset.size * 10byte  ※1
- MPHFインデックスサイズ: keyset.size + max_hash_code + max_hash_code/8 bit => 約 keyset.size * 3.4 bit

※1: max_hash_code = keyset.size * hash-code-scale


【参考】
- Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani、『Simple and Space-Efficient Minimal Perfect Hash Functions』、Springer LNCS(volume. 4619)、2007、p139-150
- http://d.hatena.ne.jp/sile/20100716/1279313240
- http://d.hatena.ne.jp/sile/20100720/1279653068

【TODO】
- 文字列に対するハッシュ値計算方法改善 (hash_impl.hh)