【ぶるーむふぃるた】
ブルームフィルタ とは？
最終更新:
💡 「ない」はわかる。「あるかも」は再確認
要素をそのまま保存せず、ビット配列とハッシュ関数で集合への所属を調べるデータ構造。「含まれるかもしれない」と「含まれない」を判定し、不要な検索を減らす。存在するとの判定には偽陽性があり得る。
📌 このページのポイント
ひよこ 普通の集合と、何が違うの？
ペンギン先生 普通の集合は要素そのものを保存して調べるけれど、ブルームフィルタは要素から計算したビットの位置だけを記録するよ。少ないメモリで事前チェックできる代わりに、「あるかも」の判定だけでは存在を確定できないんだ。
ひよこ ビットで、どうやって調べるの？
ペンギン先生 ひよこ 全部1なのに、入っていないことがあるの？
ペンギン先生 あるよ。別々の要素が、同じビットを1にすることがあるからね。入っていない要素を「あるかも」と判定するのが偽陽性。図ではAを追加した位置とIを調べる位置が重なる例にしたよ。元のデータを検索すれば、最終的に区別できるんだ。
ひよこ どこで役立つの？
ペンギン先生 ひよこ 要素を消すときは、ビットを0に戻せばいい？
ペンギン先生 通常のブルームフィルタでは、それはできないよ。同じビットを他の要素も使っているかもしれないからね。勝手に消すと、追加済みなのに「ない」と判定してしまう。「偽陰性がない」という性質は、追加した要素を正しく保持し、同じ方法で照会することが前提なんだ。
まとめ：ざっくりこれだけ覚えればOK！
「ブルームフィルタ」って出てきたら「省メモリで『ない』を先に確かめるフィルタ」と思えばだいたいOK！
📖 おまけ：英語の意味
「Bloom Filter」 ＝ ブルームフィルタ
💬 要素そのものではなく、ハッシュ関数で選んだビットの位置を記録する仕組みだよ。