ブルームフィルタ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ブルームフィルタ（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 になる。

しかし、要素数があまり大きくないと想定され、ビット配列のビット数より小さければ、ブルームフィルタを修正して、各ビットが厳密にひとつのビットで表されるようにできる。この場合もハッシュ関数の性質がよければ時間的にも空間的にも有利である。ただし、コリジョン発生率が無視できるくらい小さく、各エントリには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（ハッシュ関数の個数）は次のようになる。

$\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 になる。この特性の別の結果として、要素の追加は決して失敗しない。それは単にデータ構造を徐々に 1 で埋めていくだけである。ただし、それによって偽陽性発生率も上がっていく。

同じサイズのデータ構造と同じハッシュ関数群を持つ2つのブルームフィルタの論理和と論理積は、それぞれビット単位の OR と AND で実現できる。

[編集] 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 で紹介された。

要素の追加は各配列要素のインクリメントになり、参照は各配列要素がゼロでないことを確認することになる。削除する場合、対応する配列要素のカウンタをデクリメントすればよい。

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

[編集] Bloomier filter

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

単純な Bloomier filter で動作を説明する。まず可能な値が 0 と 1 だけの連想配列を想定する。2つのブルームフィルタ A₀ と B₀ を作成する。A₀ にキー値を追加した場合、その値は 0 であり、B₀ にキー値を追加した場合、その値は 1 であるとする。あるキー値にマッピングされた値を求めるとき、両方のフィルタを参照する。もしどちらにもそのキー値が追加されていない場合、そのキー値には値がマッピングされていない。A₀ にあって B₀ にない場合、そのキー値にマッピングされた値は 1 ではなく、高い確率で 0 であると言える。逆に B₀ にあって A₀ にないキー値なら、その値は 0 ではなく、高い確率で 1 であると言える。

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

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

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

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

[編集] 外部リンク

"http://ja.wikipedia.org../../../%E3%83%96/%E3%83%AB/%E3%83%BC/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF.html" より作成

カテゴリ: データ構造