« 調子に乗って | メイン | Bloom filter »
2006年01月07日
Bloom filter
最近 Bloom filter というアルゴリズムを知りました。1970年に考案された古いアルゴリズムです。
http://en.wikipedia.org/wiki/Bloom_filter
http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html#SECTION00053000000000000000
http://www.perl.com/pub/a/2004/04/08/bloom_filters.html
Bloom filter は、キー(通常は文字列)の存在のみをコンパクトなデータ構造で高速に判定するためのアルゴリズムです。キーの存在のチェックでしたら通常の hash でいいのですが、コンパクトになるとは限りません。
Bloom filter は "false positive"、つまり「キーが存在していないのに存在している」という判定を確率的に許しつつデータをコンパクトにします。確率値はパラメータになっていて、データサイズとのトレードオフをコントロールすることができます。
アルゴリズムそのものはいたって簡単です。用意するものは
- k 個の異なった hash 関数. ただし hash 関数は 0 ～ m - 1 の値を返す
- m bit の bit vector
だけです。入力キーに対し、k 個の hash 関数に代入し, k 個の 0 ～ m-1 の範囲の値を得ます。
各値を h_1,h_2,...h_k とすると、bit vector の h_1, h_2, ... h_k bit 目を 1 にします。
key があるかどうかは、同様の操作を行ってすべての bit が 1 になってるかどうかで確認できます。
少なくとも 1 つの bit が 0 の場合は、確実に「無い」ということがいえますが、すべて 1 だからといって確実に「在る」といえないのが Bloom filter の特徴です。
また、m と k はキーのサイズに応じて適切に決めなければなりません。m が少なすぎてもだめですし、k が多すぎてもだめです。false positive の確率を厳密に求めることが可能なので、これらの適切な値は簡単に求めることができます。
投稿者 taku : 2006年01月07日 03:59
トラックバック
このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/183