Bloomier filter

ウィキペディア小見出し辞書

Bloomier filter

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/15 00:00 UTC 版)

「ブルームフィルタ」の記事における「Bloomier filter」の解説

2004年、Bernard Chazelle、Joe Killian、Ronitt Rubinfeld、Ayellet Tal はブルームフィルタに追加した要素と関連させた値を持つ連想配列を設計した。ブルームフィルタと同様、このデータ構造も空間効率が良く、偽陽性発生の可能性がある。Bloomier filter での偽陽性は、キー値がマッピングされていないのに値が返される場合である。ただしマッピングされているキー値に対しては不正な値を返すことはない。 単純な Bloomier filter でその動作を説明しよう。まず取り得る値が 0 と 1 だけの連想配列を考える。2つのブルームフィルタ A0 と B0 を作成する。そうして値が 0 であるキーは A0 に登録し、値が 0 であるキーはB0 に登録する。あるキーに対応する値を求めるときには、両方のフィルタを参照する。もしどちらにもそのキーがない場合には、そのキーとそれに対応する値はない。キーが A0 にあって B0 にない場合には、そのキーに対応する値は 1 ではなくて、高い確率で 0 であると言える。逆にキーが B0 にあって A0 になければ、キーに対応する値は 0 ではなくて、高い確率で 1 であると言える。 ブルームフィルタで偽陽性が発生していて両方のフィルタにキーが存在すると判定された場合には問題が発生する。連想配列であるから、同じキーを両方のブルームフィルタには追加していない。しかし、どちらのフィルタが嘘をついているのかを、このままでは判別できない。このため、別の小さな2つのフィルタ A1 と B1 を用意する。そうして 値が 0 でB0 では偽陽性となるキーを A1 に、また値が 1 でA0 では偽陽性となるキーを B1 に登録しておく。そうして A0 にも B0 にも存在するとされたキーについては、そのキーを A1 と B1 で検証する。 しかしこの段階でもまだ偽陽性が発生する可能性はある。これに対しても同じ解決策を再帰的に適用する。フィルタのペアは上位のペアの片方にマップされていてもう片方で偽陽性となるものだけを登録するので、登録すべきキーの数は劇的に減っていき、ある段階になると確率的ではないデータ構造に収めることのできる数になる。また、このフィルタの階層構造を下っていかなければならない場合の数は非常に少ないため、全体としての検索時間は線形時間になる。また、全体で必要な空間のほとんどは最初のフィルタペアのものであり、n には無関係である。 以上で、データ構造と検索アルゴリズムが与えられた。新たなキーと値のペアを格納する方法は次の通りである。このとき、プログラムは同じキーに両方の値を設定するような動作は絶対にしてはならない。いま値が 0 の場合には、キーをA0 に追加し、そのキーをB0 も持っていると（嘘を）答えるかどうかを調べる。もしも B0 が（持っているという）偽陽性の結果を返すならば、そのキーを次のレベルの A1 にも追加して、以下同様の処理をする。最終のレベルにまで到達したら、そのキーを単純に挿入する。あるいは値が 1 の場合であれば、この操作を A と B を入れ替えておこなえばよい。 さて、これでキーに対して値 0 または値 1 を正しくマッピングすることができるようになったが、任意の値を格納するにはどうすればよいであろうか？ それは簡単である。値の各ビットを返すような Bloomier filter をビット幅の個数だけ作成すればよい。値のビット幅が大きい場合には、値そのものではなくて何らかのハッシュ値を Bloomier filter が返すようにする。n ビットの値を扱う Bloomier filter が必要とする空間量はブルームフィルタ 2n 個分よりも若干大きいだけである。