ブルームフィルタ

ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の可能性は増す。

使用例

例えば、ブルームフィルタを使って空間効率の良いスペルチェックを行うことができる。正しい単語を集めた辞書に対するブルームフィルタは、辞書に登録されている全単語を受容し、登録されていない単語はほとんど受容しない。つまり若干不正確ではあるが、それで十分な場合もある。偽陽性の発生率を考慮すると、単語当たり 1バイト程度でデータ構造を構築できる。

このスペルチェッカーの面白い特性として、そのデータ構造からは正しい単語のリストを取り出すことができないことが挙げられる。どんなに努力しても、正しい単語のリストとさらにおびただしい偽陽性の単語のリストが得られるだけである（そのうちのどれが正しいものであるかはわからない）。これを望ましい機能であるととらえるならば、たとえばディスク内に残っている重要な番号（クレジットカード番号など）を探し出すとか、大量の電子メールから特定の（他人に知られたくない）アドレスを含むものを探し出すといった用途が考えられる。これは完全に安全な方法ではないが、偽陽性は別の手段で取り除くことができるだろう。

アルゴリズム

空のブルームフィルタは全てのビットが 0 に設定された m ビットのビット配列である。また、同時に k 個のハッシュ関数が定義されており、それぞれがキー値を m 個の配列位置のいずれかにマッピングする。

幅広い出力をする良いハッシュ関数では、その生成するハッシュ値の各ビットの値は相互の関連がほとんどないはずなので、ハッシュ値を適当なビット位置で分割して複数の異なるハッシュ関数として使うことができる。あるいは、ハッシュ関数の内部で使われる初期値をk 個の異なる値（例えば 0, 1, …… k-1）にしたり、それらの値をキー値に加算（あるいは連結）することで k 種類のハッシュ関数としたりできる。

要素を追加するには、それを k 個のハッシュ関数に入力して k 個の配列インデックスを得る。そして、それらの位置のビットを全て 1 にする。

ある要素がその集合に含まれるかどうかを調べる（クエリ）には、それを k 個のハッシュ関数に入力して k 個の配列への添字を得る。それらの位置にあるビット群のどれかひとつでも 0 である場合は、その要素はその集合には含まれていない。逆にそれらの位置にある全てのビットが 1 であれば、その要素はその集合に含まれているか、またはそれらのビットは他の要素を追加したときにたまたま全部 1 になった（偽陽性）ものであると考えられる。

この単純なブルームフィルタからは要素を削除することはできない。要素は k 個のビットにマッピングされており、そのうちの一箇所でもビットを 0 にすれば削除できる。しかし、異なる要素についても同じビットが 1 になることで表されている可能性があるので、ビットを 0 にすると他の要素までも削除してしまうことになる。そうしていまのデータ構造だけからではそのような衝突が発生しているのかどうかは判定できない。したがって無理やり削除すると、本来であれば発生しないはずの偽陰性が発生してしまう。

それでも、キー値すべてを列挙するようなデータ構造を用いたのでは巨大になりすぎる場合にはブルームフィルターは役に立つ。要素を追加していって偽陽性発生率が高くなりすぎた場合には、ブルームフィルタを再生成する必要が生じるが、これは比較的まれな事象である。

空間的/時間的な優位性

偽陽性のリスクはあるが、ブルームフィルタは同様の集合的データ構造（平衡2分探索木、trie、ハッシュテーブル、単純な配列、線形リスト）に比べると遥かに空間効率が良い。それらのほとんどはどれも少なくとも要素のデータ自体を保持する必要があり、要素データが小さな整数ならば少なくて済むが、文字列のように任意長のデータであればそれなりのメモリ領域を必要とする（trie は例外である。trie ではたとえば文字列の同じ位置が同じ文字であればそれを共有することができる）。リンクを持つデータ構造はポインタを格納するための追加のメモリ領域を必要とする。これに対して、誤り率 1% で k の値が最適化されているブルームフィルタであれば、1要素当たり 9.6 ビットの格納領域があればよい。これは要素のデータそのもののサイズとは無関係な値である。この利点は配列を利用している点と確率的特徴から生じている。1% の偽陽性率が高いという場合には、要素ごとに 4.8 ビットの領域を追加するごとに、誤り率をさらに 10分の1 にできる。

しかし、取りうる要素の種類が少なく、その多くが集合に含まれている場合には、ブルームフィルタよりも確定的なビット配列の方が効率が良い。確定的なビット配列では、取りうる要素あたり１ビットにより表すことができるのだから。また、衝突の発生率を無視するならハッシュテーブル（ただし、配列には値が入っているか否かの情報のみを格納する）も時間的・空間的に有利であり、これは実質的に、k = 1 のブルームフィルタと同じものとなる。

ブルームフィルタの珍しい特徴は、要素の追加も要素の有無の質問も O(k)の固定時間しかかからず、格納されている要素数には全く影響されないことである。固定サイズのデータ構造でこのような特徴を持つデータ構造はないが、衝突のない疎なハッシュテーブルはブルームフィルタよりも高速である場合がある。ブルームフィルタをハードウェアで実装すると、k 個のハッシュ関数を論理回路化して並行動作できるため、高速化が容易である。

空間効率を理解するために、k = 1 のブルームフィルタの場合を考えて見よう。k = 1 のときに偽陽性発生率を十分低くするには、ビットが 1 となる割合を十分少なくしなければならない。つまり、ビット配列はかなり大きくなり、その内容のほとんどは 0 になる。このときの配列のもつ情報量もサイズに比較して低くなる。通常の（k が 1 より大きい）ブルームフィルタでは、1 となるビット数が増えても同程度の偽陽性発生率を維持できる。従って k と m というパラメータの組み合わせを適切にすれば、ほぼ半分程度のビットが 1 となるようにでき、ちょうど情報量を最大にして冗長性を最小にできる。

偽陽性確率

ハッシュ関数は配列上の各位置を同じ確率で選択するものとする。要素をひとつ追加する際、あるビットが特定のハッシュ関数で 1 にセットされない確率は次のようになる。

1-{\frac {1}{m}}

.

従って k 個のハッシュ関数のいずれによっても、1つのビットが 1 にセットされない確率は次のようになる。

\left(1-{\frac {1}{m}}\right)^{k}

.

n 個の要素を追加した状態で、あるビットがいまだに 0 である確率は次のようになる。

\left(1-{\frac {1}{m}}\right)^{kn}

;

したがって、逆に 1 となっている確率は次のとおり。

1-\left(1-{\frac {1}{m}}\right)^{kn}

.

ある要素ではないと分かっているデータに対してそれが集合の要素であるかどうかをテストしたとする。このときハッシュ関数で得られる k 個のビットそれぞれが 1 となっている確率は上記の通りである。全てが 1 となっている確率、すなわちブルームフィルタがそのデータが集合の要素であると誤って判定してしまう確率は次のようになる。

\left(1-\left(1-{\frac {1}{m}}\right)^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}

.

明らかに、m（配列のビット数）が大きければ偽陽性の発生率は低くなり、n（追加する要素数）が多くなれば偽陽性の発生率は高くなる。いま m と n が決まっているとき、偽陽性発生率を最小にする k（ハッシュ関数の個数）は次のようになる。

k={\frac {m}{n}}\ln 2\approx {\frac {9m}{13n}}\approx 0.7{\frac {m}{n}}

,

このときの偽陽性の発生確率は次の通り。

\left({\frac {1}{2}}\right)^{k}\approx {0.6185}^{m/n}

.

特性

ハッシュテーブルとは大きく異なり、長さが一定のブルームフィルタにより任意の要素数を持つ集合が表現できる。つまり要素をいくらでも追加できる。要素の追加は単にデータ構造を徐々に 1 で埋めていくだけであるので失敗することは無い。ただし要素数が増えるにつれて偽陽性の発生率も増加する。

2つの集合から、同じハッシュ関数群を使って同じサイズのブルームフィルタをそれぞれ作ったとしよう。それら2つのブルームフィルタのビットごとの OR で得られる m ビットの配列は、2つの集合の和集合を表現するブルームフィルタと一致する。いっぽうでこれら2つのブルームフィルタのビットごとの AND により、2つの集合の積集合を表すブルームフィルタ（のようなもの）を作ることができるが、そのようにして得られるものは、最初から積集合に対して作成されたブルームフィルタに比べれば偽陽性の確率が大きくなる。

Counting filter

Counting filter はブルームフィルタの実装の一種で、再生成をせずに要素の削除ができるものである。Counting filter では、配列の各要素はビットから n ビットのカウンタへと拡張されている。通常のブルームフィルタは Counting filter でカウンタのサイズが 1 ビットの場合であると見なせる。Counting filter は L. Fan, P. Cao, J. Almeida, and A. Broder. Summary cache: A scalable wide-area Web cache sharing protocol. In Proceeding of SIGCOMM ’98, 1998 で紹介された。

集合への要素の追加は各配列要素を1ずつ増やすことになり、参照は各配列要素がゼロではないことを確認することになる。要素の削除をおこなう場合には、対応する配列要素のカウンタを1つずつ減らせばよい。

カウンタのオーバフローが発生する問題が考えられるため、カウンタサイズ n はそのようなことがなるべく発生しないように十分大きくしなければならない。もしもオーバフローが発生したら、ブルームフィルタ本来の偽陽性発生がありうるという性質に基づいて、そのカウンタを要素の追加や削除で変更せずに、最大値のままにしておくのがよいとされている。

Bloomier filter

2004年、Bernard Chazelle、Joe Killian、Ronitt Rubinfeld、Ayellet Tal はブルームフィルタに追加した要素と関連させた値を持つ連想配列を設計した。ブルームフィルタと同様、このデータ構造も空間効率が良く、偽陽性発生の可能性がある。Bloomier filter での偽陽性は、キー値がマッピングされていないのに値が返される場合である。ただしマッピングされているキー値に対しては不正な値を返すことはない。

単純な Bloomier filter でその動作を説明しよう。まず取り得る値が 0 と 1 だけの連想配列を考える。2つのブルームフィルタ A₀ と B₀ を作成する。そうして値が 0 であるキーは A₀ に登録し、値が 0 であるキーはB₀ に登録する。あるキーに対応する値を求めるときには、両方のフィルタを参照する。もしどちらにもそのキーがない場合には、そのキーとそれに対応する値はない。キーが A₀ にあって B₀ にない場合には、そのキーに対応する値は 1 ではなくて、高い確率で 0 であると言える。逆にキーが B₀ にあって A₀ になければ、キーに対応する値は 0 ではなくて、高い確率で 1 であると言える。

ブルームフィルタで偽陽性が発生していて両方のフィルタにキーが存在すると判定された場合には問題が発生する。連想配列であるから、同じキーを両方のブルームフィルタには追加していない。しかし、どちらのフィルタが嘘をついているのかを、このままでは判別できない。このため、別の小さな2つのフィルタ A₁ と B₁ を用意する。そうして値が 0 でB₀ では偽陽性となるキーを A₁ に、また値が 1 でA₀ では偽陽性となるキーを B₁ に登録しておく。そうして A₀ にも B₀ にも存在するとされたキーについては、そのキーを A₁ と B₁ で検証する。

しかしこの段階でもまだ偽陽性が発生する可能性はある。これに対しても同じ解決策を再帰的に適用する。フィルタのペアは上位のペアの片方にマップされていてもう片方で偽陽性となるものだけを登録するので、登録すべきキーの数は劇的に減っていき、ある段階になると確率的ではないデータ構造に収めることのできる数になる。また、このフィルタの階層構造を下っていかなければならない場合の数は非常に少ないため、全体としての検索時間は線形時間になる。また、全体で必要な空間のほとんどは最初のフィルタペアのものであり、n には無関係である。

以上で、データ構造と検索アルゴリズムが与えられた。新たなキーと値のペアを格納する方法は次の通りである。このとき、プログラムは同じキーに両方の値を設定するような動作は絶対にしてはならない。いま値が 0 の場合には、キーをA₀ に追加し、そのキーをB₀ も持っていると（嘘を）答えるかどうかを調べる。もしも B₀ が（持っているという）偽陽性の結果を返すならば、そのキーを次のレベルの A₁ にも追加して、以下同様の処理をする。最終のレベルにまで到達したら、そのキーを単純に挿入する。あるいは値が 1 の場合であれば、この操作を A と B を入れ替えておこなえばよい。

さて、これでキーに対して値 0 または値 1 を正しくマッピングすることができるようになったが、任意の値を格納するにはどうすればよいであろうか？それは簡単である。値の各ビットを返すような Bloomier filter をビット幅の個数だけ作成すればよい。値のビット幅が大きい場合には、値そのものではなくて何らかのハッシュ値を Bloomier filter が返すようにする。n ビットの値を扱う Bloomier filter が必要とする空間量はブルームフィルタ 2n 個分よりも若干大きいだけである。

外部リンク