DAWG(4-3): MPHFライブラリ

前回までで最小完全ハッシュ関数(MPHF)の実装方法(の一つ)が分かったので、C++から使いやすくするためにライブラリ(と云う程の規模ではないけど)としてまとめておいた。
・mphf-0.0.1

実装の大枠は、前回のcommon lisp版のものと同様なので略*1。
ハッシュ関数の数は二個に固定*2。

例:

# ビルド
$ cd mphf-0.0.1
$ make

# データ: wikipediaの各国語タイトル
$ ls -lh wiki.title
-rw-r--r-- 1 user user 103M 2010-06-23 01:10 wiki.title

$ wc -l wiki.title
5340378 wiki.title  # 約530万語

# MPHF生成
$ time ./mkmphf mphf.wiki.idx ~/dev/cc/louds/wiki.title 
= Initialize
  == key count: 5340378          # キー数
  == hash value limit: 11161390  # ハッシュ値の上限 (キー数*2.09)
DONE
= Mapping Step: 
 == loop: 1/32   # Mapping Stepのグラフ生成/チェックループ        
 == loop: 2/32   # ハッシュ値計算方法がいいかげんなためか期待値(三割前後)よりも成功率が低い
 == loop: 3/32
 == loop: 4/32
 == loop: 5/32
 == loop: 6/32
 == loop: 7/32
 == loop: 8/32
 == loop: 9/32
Done
= Assigning Step: 
Done
= Ranking Step: 
Done
= Save: mphf.wiki.idx
Done

real	0m31.833s
user	0m31.346s
sys	0m0.488s

$ ls -lh mphf.wiki.idx
-rw-r--r-- 1 user user 2237164 2010-07-21 03:56 mphf.wiki.idx  # 2.2MB: キー1つにつき約3.4bit

# ハッシュ値計算
$ head wiki.title 
!
!!
!!!
!!!Fuck_You!!!
!!!_(album)
!=
!?
!Avast
!Kwi
!LOUD!

$ head wiki.title | ./mphf mphf.wiki.idx
3459282
5311644
984391
2303434
5104951
450980
450982
3505548
2184885
1526653

$ ./mphf mphf.wiki.idx < wiki.title | sort -n | head
0
1
2
3
4
5
6
7
8
9

$ ./mphf mphf.wiki.idx < wiki.title | sort -n | tail
5340368
5340369
5340370
5340371
5340372
5340373
5340374
5340375
5340376
5340377

$ ./mphf mphf.wiki.idx < wiki.title | sort -n | uniq | wc -l
5340378

*1:本質的に差異があるのは次の二点のみ:
1] phfからmphfへの変換方法:
　　- 上のライブラリでは『Simple and Space-Efficient Minimal Perfect Hash Functions』の4.1節(「Imporveing the space」)の最後で示唆されている方法を採用している。
　　- 使用ハッシュ関数を決定してからrankしていたのを、rankしてから使用ハッシュ関数を決めるように。
　　- 若干処理は多くなるが、省スペース。詳細は省略。

2] Mapping Stepでのグラフの循環チェック(and Assigning Step用の並び替え):
　　- 前回は、各頂点(ハッシュ値)が接続する全ての枝をリストとして保持する配列をチェックのために用意していた。
　　　-- 循環性のチェックは、枝リストのサイズが一の頂点の削除を繰り返すことで行う。
　　　-- 処理ステップ的には効率が良さそうな気がするけど、結構スペースを消費する。
　　　-- オリジナルのグラフ(キーごとのハッシュ値セット) + リストの配列 + 削除順に並び替えを行ったグラフ分の領域が必要。
　　　-- Mapping Stepが全体を通して一番スペースを要する。
　　- 今回(?)は、チェック用に補助的なデータ構造は用意しない。
　　　-- 枝の片方の頂点でソート、ユニークな頂点を持つ枝(= 末端の枝)の除去(実際には先頭との入れ替え)、除去分を除いてもう片方の頂点でソート、... を繰り返すことでチェック(and 並び替え)を行う。
　　　-- 全て削除できたのなら非循環。
　　　-- 複数回ソート及び走査を行う必要があるが、作業領域はグラフ一個分 = キーセットのサイズ x sizeof(unsigned) x Nで済む。※ Nはハッシュ関数の数、ハッシュ値の型はunsigned intと仮定

*2:二個の方が実装が簡単になるため。ハッシュ関数を三個にした方が非循環グラフの生成は容易(Mapping Stepでのループ回数を減らせる)で、最終的なデータサイズも節約できるので、いつか変更するかもしれない。