ブルームフィルタ

ブルームフィルタ（Bloom Filter）とは、1970年代に考案された判定システムです。

これによると、ある要素が集合に含まれているかを確率的に判定することができます。含まれないものを含まれると誤って検出する可能性（偽陽性）はありますが、含まれるものを誤って含まれないと検出する可能性（偽陰性）はありません。

たとえばディスク内に保存されている重要な番号を見つけ出したり、大量の電子メールから特定のアドレスを含むものを探し出したりすることができます。誤って含まれると判断された物を取り除くための作業は必要ですが、重要なものを取りこぼすことはありません。

集合に存在しないデータを含まれていると誤判定してしまう場合があります。誤判定が許されないような状況においては、ブルームフィルタは使うことができません。