- 参考サイト

感想ですが、予想以上にシンプルでした。

動作イメージ(だけ)は誰でもイメージできます(実装も簡単)。
上の参考サイトも、英語に気後れせず、図だけでも見てください。動作は想像できるはずです。そして、たぶん、その想像は当たっています。

参考サイトを読めば分かることを日本語で改めて説明するのも気がひけますが、どうしても英語を読みたくない人のために、簡単に説明してみます。

動作イメージ

あ る入力文書が与えられたとして、後で、その文書に、ある単語fooが存在するかを高速にチェックしたい、という問題を想定するのが理解しやすいと思いま す。入力文書に対する前処理をしていいとします(「珠玉のプログラミング」のsuffix arrayの例題を思い出しますね)。

k個(個数はあらかじめ決めておく)のハッシュ関数を用意します。例えば、Perlの実装だと、ハッシュ関数にSHA1を使い、k個のsaltを適当に生成するようです。

単語群から最初の単語を取り出し、k個のハッシュ関数に通します。
最初の単語を「以前」とします。=>の後ろがハッシュ値です。

- SHA1-1("以前") => 51
- SHA1-2("以前") => 102
- ...
- SHA1-k("以前") => 7

あらかじめ、Bloom filterに使うビット数mを決めておきます。
ハッシュ値がm以下になるようにします。Perlの実装だと、mの剰余にしているようです。
上の例の51,102,...,7は、0からmの範囲に収まるように計算された後だとします(以降、ハッシュ関数は暗黙にこの丸め計算を含んでいるとします)。

mビットの配列は、最初、すべてゼロで初期化します。
51,102,...,7番目のビットを立てます(「珠玉のプログラミング」の第1章を思い出しますね)。
最初の単語で、mビットの配列のうち、k個のビットが立ちます。

次の単語にも同様にk個のハッシュ関数を通して、k個のビットを立てます(ビットが既に立っている場合、そのままです)。
全ての単語に対して同じ処理を行います。

ビット数mが小さすぎたり、ハッシュ関数の個数kが多すぎたり、入力単語が多すぎたりすると、全部のビットが立ってしまいます。そうなると、Bloom filterは意味をなしません。適度に疎になる程度に、mとkを選択する必要があります。

これで前処理は終わりです。

調 べたい単語が「珠玉」だとします。「珠玉」をk個のハッシュ関数に通して、ハッシュ値を得ます。Bloom filter(: mビットの配列)のビット値(ハッシュ値の位置)を調べます。k個のビットがすべて立っていれば、「珠玉」は入力文書にあった*かもしれない*と言えま す。k個のビットのうち、ひとつでも立っていないビットがあれば、「珠玉」は入力文字列に*確実に無かった*と言えます。

「あったかもしれない」と判定しながら、実際に存在しないケースが起こりうることは、自明だと思うので説明しません。
Bloom filterは、この「あったかもしれない」誤判定を許容することで、少ないビット数で存在チェックをするアルゴリズムです。

ハッシュ関数はひとつでも良いのではないか(つまりk==1)、という疑問が当然あると思います。
ひ とつのハッシュ関数のビットのチェックより、沢山のハッシュ関数のビットをチェックした方が信頼性が高いのでは、と思うのは早計です(kが増えると、立つ ビットも多くなります)。まあ、Bloom filterを使うだけなら、kとエラー率が理論的に計算されているので、それを調べれば良いだけです。

応用編

Bloom filterには、以下の特性があります。
- 少ないデータを転送するだけで、存在チェックのヒントを相手に渡せる
- Bloom filterの和は、ビット和を取るだけでできる
- 秘密を保ったまま、自分の手札をさらせる
- Bloom filterを比較(同じビットが立っているか否か。つまりXOR演算)することで、近さの判定ができる

最初の特性は、squidのcache digestで利用されているようです。上流のsquidに転送することで、要求の転送のフィルタリングができます。
同様の志向で、P2Pのqueryコマンド転送でも、その先のノードに探索リソースがあるか無いかをあらかじめチェックできます。
2番目の特性により、上流に向かってフィルタを転送するには、ビット和を取りながら送るだけで済みます。最終的に全ビットが立つかもしれませんが、それは全パスを意味するので、何もしなかった場合と同じで害はありません。
(上流という概念がある時点で、ツリー構造っぽいので、P2Pのような動的トポロジ形成の場合、スパニングツリーアルゴリズムなどで局所的にでもツリー構造を作る必要があるかもしれません。)

3番目の特性は、SNS的なLOAFに見られます。名前がFOAFと似ているのは偶然ではなく、狙った名前でしょう。自分のアドレス帳の秘密を保ったまま、自分のアドレス帳に誰かがいるかどうかの情報を交換可能です(誤検知もありますが)。
4番目の特性で、アドレス帳のBloom filter同士を比較することで、アドレス帳の近さ判定ができます(秘密は保たれたままです)。