fujimap: 簡潔な連想配列 - DO++

博論終わったので仕事の合間にfujimapというライブラリを作ってみました。 fujimap project fujimapは作業領域が非常に小さい連想配列で、文字列からなるKeyを利用して、整数値もしくは文字列からなるValueを登録・参照することができるライブラリです。 今巷では大規模なKey Value Stroe (KVS)が流行っていますがFujimapは一台のマシンのメモリ上で動作することを想定して作成されています．Fujimapの特徴は必要な作業領域量が非常に小さいことです．キー自体を明示的に保存しないため、作業領域は値を格納するのに必要なサイズと、許容するfalse positive（後述）にのみ依存します。 例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、false positiveを気にしないなら、一キーワー

[fcicq]

Perfect Hash + Bloom filter-like storage, fujimap. http://code.google.com/p/fujimap/

[takahi-i]

fujimap

[toton]

Fujimapの特徴は必要な作業領域量が非常に小さいこと。「例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、一キーワードあたり約4bit（全部で7MB、もともと136MB)で格納できます。」

[TAKESAKO]

こういうの欲しかった。すばらしいです → fujimap: 簡潔な連想配列

[ang65]

ちょっと試してみたい

[tacroe]

N個のKeyに対し衝突しない[0,N-1]の値を割り当てる手法を値を格納する方法に拡張

[tettsyun]

false positive を許して情報理論的限界を破ることで作業領域を改善

[tinsep19]

Bloom Filterのようにfalse positive側のみにエラーをゆるし情報理論的限界を破っています

[tasukuchan]

鴨せいろ（大）が好き。ほうれん草のごまあえ付けて。

[zu2]

どういう用途に使えるんだろ

[sett-4]

fujimapではKeyを明示的に格納しません。それでも登録したKeyに対しては正しい値を常に返します．それに対して、登録されていないKeyに対してはユーザーが設定した確率で誤り、NOTFOUNDが返らずにランダムな値が返ってきてし