DO++

博論終わったので仕事の合間にfujimapというライブラリを作ってみました。

fujimap project

fujimapは作業領域が非常に小さい連想配列で、文字列からなるKeyを利用して、整数値もしくは文字列からなるValueを登録・参照することができるライブラリです。

今巷では大規模なKey Value Stroe (KVS)が流行っていますがFujimapは一台のマシンのメモリ上で動作することを想定して作成されています．Fujimapの特徴は必要な作業領域量が非常に小さいことです．キー自体を明示的に保存しないため、作業領域は値を格納するのに必要なサイズと、許容するfalse positive（後述）にのみ依存します。

例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、false positiveを気にしないなら、一キーワードあたり約4bit（全部で7MB、もともと136MB)で格納できます。C++ std::mapの約1/100です。メモリが10GBある場合、同じようなデータなら200億 Key/Valuesぐらいを高速に操作できます。

fujimapではKeyを明示的に格納しません。それでも登録したKeyに対しては正しい値を常に返します．それに対して、登録されていないKeyに対してはユーザーが設定した確率で誤り、NOTFOUNDが返らずにランダムな値が返ってきてしまいます（false positive rate, 偽陽率）．Bloom Filterのようにfalse positive側のみにエラーをゆるし情報理論的限界を破っています．

fujimapが必要とするサイズと偽陽率はトレードオフの関係にありfpLenと呼ばれるパラメータで設定できます．1KeyあたりfpLen bitのオーバーヘッドで偽陽率は2^{-fpLen}となります．例えば、1keyあたり10bitのオーバーヘッドで2^{10}分の1、つまり約0.1%の確率で登録されていないKeyに対しても、NOTFOUNDではなく、何らかの値が返ってしまいます．

これはKeyがどのような文字列からなる場合でも同様になりたちます．例えば，Keyの長さが1KBのように長い場合でも、その格納に必要なBit数はfpLenと値のみで決まります．

いくつかの実験結果は先ほどのページに乗せてあります．
先ほどのGoogle N-gramの例では

1keyあたりに必要なbit数
std::map 573 bit
tx 35.4 bit (keyの保存に29.4 bit , 値の保存に6bit）
fujimap 4.4 bit

であり、構築時間、参照時間はstd::mapとほぼ同じです

これらの実験結果やAPIなど詳細についてはプロジェクトページをみてください。

説明や使用例、アプリケーションなどは随時追加していきます。

注意点として、fujimapでは一応、動的な追加、変更が一応C++ APIではサポートされているのですが、それらの命令を使った途端に先ほどの偽陽率や登録したキーには必ず正しい結果が返ってくるという保障がなくなります。このあたりについてはきれいに説明できないので使う必要がないなら極力使わないようにしてください。どうしたらきれいに外から使えるかまだ考え中です。

--
Fujimapの内部はいくつかの研究を元にしたものに実装的な工夫を追加しています．
Fujimapの基本的なアイディアは最小完全ハッシュ関数と同様のもので、N個のKeyに対し衝突しない[0,N-1]の値を割り当てる手法を値を格納する方法に拡張しています．

まず、FujimapでKey kを格納する場合R個（R=2,3など）のハッシュ関数での値h1(k), h2(k),... hr(k)を求めます．次に、ビット配列Bから、これらの排他的論理輪の値を求めます v = B[h1(k)...] ^ B[h2(k)...] ^ B[hr(k)...];　このvがkに対応する値です．

値は擬陽性をチェックする部分（fpLen bit）と、それ以降の実際の値を格納する部分からなります．キーkに対し、先ほどのハッシュ関数とは異なるハッシュ関数でkに対するsignatureを求めておき、先ほどのvの先頭fpLen bitがsignaretueと一致する場合は、それが実際の値、そうでない場合は登録されていないKeyということでNOTFOUNDを返すようにします。

fpLen bit以降の値は実際の値を固定bit長のBinary符号、もしくはGamma符号で格納しています．

登録されている全てのキーに対し、上のように操作して正しく動作するようにB中ビット値を決定する問題は連立方程式の問題となります．この問題は最小完全ハッシュ関数を決定するのと同様に、キー集合とそれらの依存関係からハイパーグラフを構築し、そのハイパーグラフ中から次数が１である頂点とそれにつながっている枝を順にのぞいていき、次にこの順番と逆に各bitの値をgreedyに決定していくことによりキーに比例する時間で決定できます。

非常に大規模なキー集合を扱う場合、構築に必要な作業領域が大きくくなってしまう問題が生じます．そのため、Fujimapでは最初にKeyの集合を簡単なハッシュ関数を利用していくつかのブロックにわけておきます。そして各ブロック内部で先ほどの手法を利用してキーと値を結び付けます．各ブロックのサイズをディスクの１ブロックと同程度にすることにより、ディスクアクセスを生じる場合でもシーク回数が一回でできるようなデコードも実現可能です．

--
fujimapの開発にあたり、開発環境をいろいろ変えています

ビルドシステムにautomakeから変更しwafを使っています（隣の隣の席の田中さんによるwaf解説)
ものすごく速くて色がついて怪しいautomakeの黒魔術を使わなくて便利です。まだいまいちわかっていなくて例をちょっと変えたものしかつかっていないけど。

あと、google code projectをフル活用。あとdoxygenからgoogle project wikiに変換するやつがうまく動けば、いいんだけど、どうも動く動かない

--
ちなみにライブラリの名前は博論書きの時にお世話になった富士そばに由来しています。天玉が好きです。

いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。

"Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf)

扱っているのは次のような問題です（説明のため本来のと言い換えています）

n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています．
この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。

簡単に思いつくのは，各節点に適当な個数(d)の答えをあらかじめ前計算したものを持っておくというアプローチですが、この場合保存に必要なスペースは
節点数がO(n)のため、O(nd)bitsとなる上、d < kの場合は途端に計算量が爆発します．

この問題は全文検索と非常に強い関係があります．検索対象D個の文書に対し接尾辞木や接尾辞配列で索引を作る場合、それらをつなげた長さnの入力文を作成します。
次に、それに対する接尾辞木（一般接尾辞木）を構築します。検索のときは普通の接尾辞木のよう検索を行い、ヒット位置集合を求めた後に、それらの位置が元々どの文書に所属していたかを求めます．
ヒット件数を求めるのはO(|q|)と高速に行うことができるのに対し、ヒット文書集合、ヒット文書数を求めるのはヒット位置数がoccの時、O(occ log D)時間かかってしまいます。
各位置に対してそれがもともとどの文書に対応していたかを調べるにはO(log D)時間かかるため。
ヒット位置数が数億などで、それらの中からクエリに特に関係する数十程度の文書を求めるのに非常に大きな時間がかかってしまいます。

これに対する解法はいくつか提案されていますが補助データ構造のサイズが非常に大きいなどの問題がありました

論文では、この問題をO(k log k + dep)時間で正確な結果を求めることができ、O(n log n)bitsで保存可能なデータ構造を提案しています。depは節点の深さです。
これはかなりまじめにやった場合で、ヒット位置数が大きい場合節点に対して保存することにより、データ構造のサイズはいくらでも小さくなりえて、結構現実的です。

まず、木中の節点（葉も子の数が０の節点とする）に対し行きがけ順（preorder）で番号をつけておきます。これは深さ優先探索をして、辿った順です。
この番号のつけ方だと、ある節点以下の部分木は全て連番になっているという特徴があります。

次に、各節点において(親へのポインタ:p 色:c）エントリの配列からなるN-structureというデータ構造を考えます。
まず、各葉では、自分の色からなるエントリのみをN-structureに保存します。
次に各内部節点では、二つ以上の子が色cの葉を子孫として持つ場合、色cのエントリを持つとします。そして色cのエントリ中のpは、同じ色cのエントリを保持する最も近い祖先の節点番号とします。
もし、そのような親が無い場合は-1をpとして記録しておきます。

先ほどの定義より、ある節点において、同じ親へのポインタを含むエントリを複数持つ場合はあります、が同じ文書番号を含むエントリは高々一つしか存在しません。

図では葉に色（a,b,cの文字ですが）がacbaaccbcとつけられている場合の例を示します
図中の青色の箱がN-structureの例です。例えば番号2の節点(-1, a), (1, c), (-1, b)の三つのエントリからなるN-structureが保存されています。番号3の節点のように一つもエントリが無い節点も存在します。

このとき全エントリの総数は高々2n個です。なぜなら、それぞれ葉の数がn個で子二つが持っている場合のみ内部節点にはエントリが存在するからです。

次に、N-structureの逆向きのI-structureというのを考えます。これは（子へのポインタ：p 色:c 頻度:f）を保存した配列です。例えば節点tにおいて(p, c)というエントリがN-structureに存在する場合、
節点pに(t, c, f)というエントリが存在します。fは節点tの子孫中の色cの個数です。
I-structure中では、エントリは子へのポインタの番号順にソートしておくことにします。頻度：fは対応する子でその色が何回出現しているかを記録したものです。
図のオレンジ色の箱がI-structureの例です。

このI-structureのエントリの総数もN-structureと一対一対応があるので高々2n個です。
検索時に保存するのはI-structureのみです。

では、これを利用して先ほどの問題を解いてみましょう。

クエリとして節点tと正整数kが与えられ、t以下の色で頻度が高い順にk個報告するのが目標です。

まず、t以下の節点、葉は行きがけ順で番号をつけたことから連続する番号がつけられています。これを[t, t']としましょう（t'はt中の最右の葉）

次にtの親から根方向に向かう各節点のI-structureにおいて、[t, t']内の値を子へのポインタとして持っている範囲を見つけます(*)。I-structureはポインタの番号順にソートされているので、この範囲は連続した区間に存在し
二分探索でその範囲を求めることができます。例えば、図の例でクエリで節点3が与えられた時 [t, t']=(3, 6)なので、節点2においては(4:a 1) (5:c 1) (6:b 1)が該当する範囲であり、節点1, -1ではこの範囲に該当するエントリは
ありません。

この範囲の集合に対し次の事実があります。

事実：tを根とする部分木中に出現している各色に関するエントリはこれらの範囲の集合内ではちょうど１回出現し、それの頻度fはt中の色cの出現頻度と一致する。

これは、ある部分木内に色cが出現している場合、この部分木から外に飛び出すポインタで色cに関するものはちょうど1個しかないこと、またそのポインタの子孫にのみ色cの葉が含まれていることからいえます。

さて、この事実を使えば、これらの範囲集合内で頻度が大きいものをk個とってくればいいだけになります。同じ文書番号を重複して数えてしまうとか、足さないといけないとか考える必要はありません。

それぞれの範囲内でRange Max Query (RMQ)を走らせ、各範囲内で最大値のものをk個ヒープに登録します。
そして、ヒープから一個ずつ一番高い値を取り出し、取り出した値に関する範囲を二個の部分範囲に分割し、それぞれの中からRMQを適用してまた最大値二個登録し、ヒープから最小の値を一個除きます。これを繰り返せば上位k個を取り出すことができます。
この時間はRMQはO(1)時間、O(n)bitsで実行でき、ヒープの操作時間合計はO(k log k)です。

(*)を求める時間は二分探索であることからO(log n)時間、predecessor用のデータ構造を使うとO(log logn)時間でとけますが、もうちょっと補助データ構造を使うと一つの節点あたりO(1)時間でとくことができます。

計算時間はクエリ節点から根への範囲の個数は高々dep個なので、まとめるとO(dep + k log k)時間でとけます。

さて、この話は頻度情報以外も扱えます。例えば文書にページランクのような固有のスコアが与えられている場合、fの代わりにそのスコアをいれておけば、同じように動きます。

アイディアは単純ですがとてもきれいな話だと思います。
この著者の人と昨年夏にあったとき、すごいのを思いついているのだが言えないといってたのが分かります。