操作して学ぶ
Bloomフィルタ可視化
Bloomフィルタは「無い」は確実に、「ある」は“たぶん”で答える確率的データ構造です。 要素を追加すると k 個のビットが立ち、確認はその k 個が全部立っているかを見るだけ。追加していない要素なのに「たぶんある」と答えてしまう偽陽性を、実際に起こして体感してください。
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
立っているビット: 0 / 32追加した要素: 0推定偽陽性率: 0.0%
要素を追加
含まれるか確認
仕組みと使いどころ
- 偽陰性は起きない。ある要素を追加したなら、その k ビットは必ず立っている。だから確認で1つでも 0 があれば「確実に含まれない」と断言できる。この非対称性が Bloomフィルタの核心。
- 偽陽性は埋まるほど増える。別々の要素が同じビットを共有するため、追加していない要素の k ビットが偶然すべて立つことがある。要素数が増えビットが埋まるほど、偽陽性率
(1 − e−kn/m)kは上がる。 - k の最適値がある。k を増やすと1要素あたりのビットが増え、少数なら精度が上がるが配列も速く埋まる。最適は
k ≈ (m/n)·ln2。スライダーで動かすと埋まり方が変わる。 - 削除はできない。ビットを 0 に戻すと、同じビットを共有する別の要素まで壊れる。削除が要るなら、各ビットを数える Counting Bloom Filter を使う。
用途は「確実に無いものを、省メモリで高速に弾く」こと。DBが不要なディスク読み込みを避ける、CDNがキャッシュに無いキーを早く判定する、ブラウザが危険URLを一次判定する、といった前段フィルタで広く使われます。