はじめに
ブルームフィルターというアルゴリズムを最近知りました。
集合の中に特定の要素が含まれているかどうかを高速に判定できるというものです。
とても面白かったのでまとめてみようと思います。
例えばこんな時
100万冊の本が収蔵されている図書館で、目的の本があるかどうかを調べるとします。
単純に調べると、100万冊の本を一冊一冊、目的の本かどうか確認する必要があります。
とても時間がかかりそうですね。
そこで、入口に本の有無を高速で判定できるチェック装置を置きます。
この装置は、調べたい本について「無い」か「あるかも」のどちらかを返します。
「無い」と出たら、その本は確実に無いので探さなくてかまいません。
「あるかも」と出たら、ある可能性があるので、図書館内を探します。
これがあれば、入口で「無い」と判定された本については、館内で調べる必要がありません。
100万冊の確認作業をする回数が減るので、毎回すべてを探すよりずっと効率的になりそうです。
この「チェック装置」が「ブルームフィルター」と呼ばれるものです。
仕組み
ブルームフィルターを使うには、まず長さ $m$ のビット配列を用意します。
各マスには最初すべて $0$ が入っていて、あとから必要な場所だけ $1$ にしていきます。
さらに、要素を受け取って $0$ から $m - 1$ までの数値を返すハッシュ関数を $k$ 個用意します。
この $m$ や $k$ は規模や求める精度によって調整します。
事前準備として、集合に入っている要素をひとつずつハッシュ関数に通し、対応する位置のビットを $1$ にしておく必要があります。
同じ位置が何度選ばれてもかまいません。すでに $1$ ならそのままです。
具体的に見てみましょう。
例えば、長さ 10 のビット配列と、3 個のハッシュ関数で考えます。
最初は 0000000000 です。
ここに、たとえば cat を入れるとします。
3 個のハッシュ関数がそれぞれ 1、4、8 を返したら、その位置を $1$ にするので、配列は 0100100010 になります。
次に dog を入れて、今度は 2、4、9 が返ったとします。
4 はすでに $1$ ですが、そのままでよく、全体としては 0110100011 のようになります。
この時、cat が入っているかを調べたいとします。
同じ 3 個のハッシュ関数に cat を通し、1、4、8 のビットを見ます。
もしこの 3 か所がすべて $1$ なら、「入っているかもしれない」と判定します。
では、まだ入れていない fish を調べたらどうなるでしょうか。
ハッシュ関数の結果が 1、3、7 だったとします。
このとき配列 0110100011 のうち 1 は $1$ ですが、3 と 7 は $0$ です。
ひとつでも $0$ が見つかった時点で、fish は入っていないと確実に分かります。
一方で、まだ入れていない fox を調べたときに、たまたま 1、2、8 が返ったとします。
この 3 か所は cat と dog を入れた結果、すべて $1$ になっています。
するとブルームフィルターは fox についても「入っているかもしれない」と判定します。
でも実際には fox を登録したことはありません。
これがブルームフィルターの性質です。
「無い」は確実に言えますが、「ある」は確実には言えません。
たまたま別の要素が同じ位置を $1$ にしてしまい、本当は入っていないのに「あるかも」と判定されることがあります。
このような性質は「偽陽性」と呼ばれます。
最初の例の場合
では、100 万冊の本を扱うとしたら、どのくらいの大きさのブルームフィルターを用意すればよいのでしょうか。
ここでは、長さ1500万のビット配列を使うとします。
1500万ビットはざっくり 1.8 MB くらいです。
100万冊ぶんの本の情報そのものを抱えるのに比べるとかなり小さくなります。
要素数を $n$、ビット配列の長さを $m$ とすると、ちょうどよいハッシュ関数の個数 $k$ は
$$
k \approx \frac{m}{n} \ln 2
$$
あたりになるそうです。
今回はだいたい 10 個くらいのハッシュ関数を使うのがよさそうだと見積もれます。
このとき偽陽性率は、おおよそ
$$
\left(1 - e^{-kn/m}\right)^k
$$
となっています。
実際に $n = 10^6$、$m = 1.5 \times 10^7$、$k = 10$ を代入すると、偽陽性率は約0.00075、0.075% ほどです。
10000 回問い合わせたら 7 回か 8 回くらいは「本当は無いのに、あるかもと出る」計算になります。
たった10回の計算で、「無い」は100%確実にわかり、「あるかも」も99%の精度で絞り込めるのはすごいですよね。
さらに面白いのは、蔵書が100万冊から200万冊に増えたとしても、1回の問い合わせでやること自体は変わらないことです。
使うビット配列の長さ $m$ とハッシュ関数の個数 $k$ をそのままにしている限り、毎回やるのは10回のハッシュ計算と、対応する10か所のビット確認だけです。
1回の問い合わせにかかる計算量は要素数に依存せず固定ということになります。（すごい）
ただし、要素数だけが200万に増えると、ビット配列に多くの情報を詰め込むことになるので、偽陽性率は上がります。
さきほどの式で、$m = 1.5 \times 10^7$、$k = 10$ のまま、要素数$n$だけを $2.0 \times 10^6$ にすると、偽陽性率は約4.7% まで上がります。
計算量は変わらない一方で、精度のほうが悪化していくわけです。
欠点とその補い方
1. 偽陽性がある
ブルームフィルターは、本当は入っていない要素についても「あるかも」と判定してしまうことがあります。
そのため、ブルームフィルターは最終的な判定としてではなく、前段のふるいとして使うのが基本です。
「無い」と出たものは捨て、「あるかも」と出たものだけ元のデータに問い合わせます。
また、許容したい偽陽性率に応じて、ビット配列を大きくしたり、ハッシュ関数の個数を調整したりして設計することも重要です。
2. フィルターからの削除ができない
これはさきほどの例で考えてみましょう。
cat を入れたとき、ハッシュ関数は 1、4、8 を返していました。
では cat をフィルターから消したいからといって、1、4、8 のビットを単純に $0$ に戻してよいかというと、そうはいきません。
たとえば別の要素が 4 と 8 を使っているかもしれませんし、さらに別の要素が 1 を使っているかもしれません。
ブルームフィルターは「どの要素がそのビットを立てたのか」を記録していないので、その $1$ が cat だけのものなのか、ほかの要素と共有しているのかを区別できません。
そのため、cat を消すつもりで 1、4、8 を $0$ に戻してしまうと、本当はまだ入っている別の要素まで「無い」と判定されるおそれがあります。
削除が発生する場面でブルームフィルターを使いたい場合は、派生形を使うという手があります。
代表的なのは Counting Bloom Filter で、各マスを0と1ではなくカウンタにしておき、追加で増やし、削除で減らします。
そのかわり、普通のブルームフィルターより多くのメモリが必要になります。
3. 要素数が増えると精度が悪くなる
ビット配列の大きさが固定のまま要素だけが増えると、配列全体がだんだん1に近づいていき、精度が悪化し、最終的には全ての判定が「あるかも」になります。
これを避けるには、最初にある程度の件数を見積もって設計するのが基本です。
件数の予想が難しいなら、拡張可能な派生形（Scalable Bloom Filters など）を使って段階的にビット配列を足していく方法もあります。
実際の使われ方
ブルームフィルターが活躍するのは、「正確な確認はコストが高いので、その前に無いものを安く弾けるとかなり得になる」場面です。
本番の重い処理に入る前で、候補をふるいにかける用途に向いています。
たとえばデータベースやストレージでは、実際に問い合わせを行う前に「ここにはたぶん無い」と分かれば、無駄なアクセスを減らせます。
キャッシュでも、「そのキーは入っていなさそうだ」と先に分かれば、不要な問い合わせを避けられます。
分散システムやネットワーク越しの探索でも、「その相手に聞きに行ってもたぶん無い」と先に絞れれば、通信回数を減らせます。
ブルームフィルターは、探索範囲を小さくする仕組みとして使われることが多いようです。
特に、ディスクアクセスやネットワーク越しの問い合わせのように、一回一回が手間のかかる場面で効果が大きくなります。
おわりに
「ブルームって花咲く（bloom）ってこと？バブルソート的な命名で花が咲くようなフィルター？何それかわいい！」というモチベーションで調べ始めましたが、ブルームフィルターのブルームは発明者のブルームさんの名前から取ったものだそうです。
きっかけは勘違いでしたが、仕組みから破綻の仕方まできれいでとても好きになりました。なんかうまいこと使う方法を模索中です。