ブルームフィルタが「ない」ときだけ断言できる理由
ブルームフィルタが「確実にない」か「あるかもしれない」でしか答えない理由、偽陰性が出ないという保証が成り立つ条件、偽陽性の確率の式、ビットを消すと保証が崩れる理由を整理します。
ブルームフィルタの答えは「集合に確実にない」か「集合にあるかもしれない」のどちらかです。Burton Bloom が1970年に提案した構造で、少しの誤答を受け入れる代わりに使う領域を大きく減らします。
材料はすべて0の m ビットと、k 個のハッシュ関数です。要素を追加すると、ハッシュ値が指す k ビットを1にします。問い合わせでは同じ k ビットを読み、1つでも0があれば「ない」と答えます。
偽陰性が出ない理由
追加した要素の k ビットは、追加した時点で1になっています。標準的なブルームフィルタはビットを0に戻さず、問い合わせも同じ方法でハッシュするので、そのビットを読めばすべて1です。
この保証が成り立つのは、その要素が引き続きフィルタの表す集合の要素であり、ビットが消されず、m、k、ハッシュ値からビット位置への対応が変わっていない間だけです。Python の hash() は、デフォルトでは文字列のハッシュに実行ごとに予測できないランダムな値を混ぜます。hash() で位置を決めたフィルタを保存し、ハッシュシードの異なる別プロセスで読み込むと、同じ要素が別のビットを指して保証が崩れることがあります。
偽陽性が出る理由
追加していない要素でも、ほかの要素が1にした k ビットにすべて当たることがあります。ハッシュ値が一様かつ互いに独立で、要素が n 個なら、その確率はおよそ f ≈ (1 − e^(−kn/m))^k で、k = (ln 2)·m/n のとき最小になります。m = 8n ならこの値は約5.5です。k = 6 とすると
python3 -c "import math; print((1 - math.exp(-6/8))**6)"の結果は約0.0216です。
削除
ある要素のビットを0に戻すと、ほかの要素が使っていたビットまで消えることがあり、そのほかの要素が「ない」と判定されます。カウンティングブルームフィルタはビットの代わりに小さなカウンタを置き、追加で増やし、削除で減らします。あふれたカウンタを最大値に固定する場合は、それでも偽陰性が起こりえます。
細かな動作は実装ごとに違います。Redis は、フィルタが容量に達するとデフォルトでサブフィルタを追加します。