収集したURLが10億件あり、新しいURLがすでに検出済みかどうかを知りたいとします。これらをすべてハッシュテーブルに格納すると、数十GBもの容量を消費してしまいます。ブルームフィルターなら、わずか数百MBでこれを実現できます。
仕組み
当初はすべて0で構成されていた1つのビット配列と、k個の異なるハッシュ関数。
- 要素の追加：k個の関数すべてでハッシュ処理を行い、対応するk個の位置で1を設定する
- 検証：ハッシュ処理を行い、k個の位置を確認する。0となる位置が1つでもあれば、その要素は確実に追加されていない。k個の位置すべてが1であれば、追加されている可能性がある
2つ目のケースは、誤りである可能性がある場合です。つまり、それらのビットは他の要素によってオンにされていた可能性があります。これは「偽陽性」と呼ばれます。
最も重要な性質
偽陰性は決して発生しません。ブルームフィルターが「ない」と返した場合、それは確実な答えです。この特性が、その使い方を決定づけています。つまり、コストのかかる検索の前にブルームフィルターを配置することで、検索の必要がないケースの大部分を排除できるのです。
代表的な用途
- ディスク上のファイルにキーが存在するかどうかを確認するデータベース。実際にディスクを読み込む前に
- 分散キャッシュにより、確実に存在しないキーに対するネットワーク呼び出しを回避
- Webクローラーは、以前に遭遇したURLをフィルタリングする
受け入れなければならないこと
要素を削除できない — 1つのビットをオフにすると、そのビットを共有している他の要素が破損する可能性がある。また、要素の数をあらかじめ見積もっておく必要がある。詰め込みすぎると偽陽性率が急上昇し、ほぼすべての回答が「あり得る」となり、構造が役に立たなくなってしまう。
Thảo luận