ブルームフィルタ（ぶるーむふぃるた）

概要

ブルームフィルタは、1970年にバートン・ブルームによって考案されたデータ構造です。主に、大規模なデータセットにおいて、ある要素が既に存在するかどうかを効率的に確認するために使用されます。例えば、Webブラウザのキャッシュ、データベースの検索、スパムフィルタリングなどに応用されています。

仕組み

ブルームフィルタは、ビットベクトルと複数のハッシュ関数を用いて構成されます。ビットベクトルの各ビットは、初期状態では0に設定されています。要素をフィルタに追加する際には、その要素に対して複数のハッシュ関数を適用し、それぞれのハッシュ値に対応するビットを1に設定します。要素の存在を確認する際には、同様にハッシュ関数を適用し、対応するビットがすべて1になっているかどうかを確認します。もし1つでも0になっているビットがあれば、その要素はフィルタに含まれていないと判定されます。すべてのビットが1になっている場合は、その要素が含まれている可能性があると判定されます（誤検出の可能性）。

特徴

• 高速な検索: 要素の存在確認は、ハッシュ関数の計算とビットベクトルの参照のみで済むため、非常に高速です。
• 省メモリ: ビットベクトルを使用するため、データセット全体を保存するよりも必要なメモリ容量が少なくて済みます。
• 誤検出の可能性: 誤検出が発生する可能性がありますが、ハッシュ関数の数やビットベクトルのサイズを調整することで、その確率を低減できます。
• 要素の削除不可: 一度追加した要素を削除することはできません。削除が必要な場合は、別のデータ構造と組み合わせる必要があります。

応用例

• Webブラウザのキャッシュ: 既にキャッシュに存在するURLかどうかを高速に確認します。
• データベースの検索: 大規模なデータベースにおいて、特定のキーが存在するかどうかを事前に確認します。
• スパムフィルタリング: スパムメールの送信元アドレスがブラックリストに登録されているかどうかを高速に確認します。