ブルームフィルタ
ブルームフィルタとは、ある要素が集合の中に存在するかどうかをコンピュータに確認させるためのデータ構造です。ブルームフィルタは、ハッシュ関数を使ってこれを行います。追加される各要素について、ハッシュ値が計算されます。新しい要素が追加されると、そのハッシュ値は集合内の他の要素と比較されます。ブルームフィルタは確率的なデータ構造である。偽陽性を得ることはできますが、偽陰性を得ることはできません。言い換えれば、クエリは「セットに含まれている可能性がある」か「セットに含まれていない可能性がある」かのどちらかを返します。要素をセットに追加することはできますが、削除することはできません。要素が追加されるごとに、偽陽性を取得する確率が高くなります。
エドワード・ブルームは1970年にブルームフィルタを提唱した。記事の中でブルームは、行末の単語をハイフンで区切るアルゴリズムがあると仮定しています。その例によると、ほとんどの単語は単純なハイフネーションパターンを持っている。しかし、約10％の単語は、正しいルールを取得するために時間のかかるルックアップを必要とする。彼のケースは、約50万語の単語をハイフネーションするというものでした。彼は、ハイフネーションパターンを保存する「通常の」エラーフリーのハッシュ技術を使うと、多くのメモリを必要とすることに気づきました。彼は、彼の技術を使えば、ほとんどのルックアップをなくすことができることを発見しました。例えば、理想的なエラーフリーハッシュで必要とされるサイズの15%しかないハッシュ領域でも、 ディスクアクセスの85%を排除できるのです。
より一般的には、セット内の要素のサイズや数に関係なく、1%の偽陽性確率を得るためには、要素あたり10ビット以下が必要です。
質問と回答
Q:ブルームフィルタとは何ですか?
A: ブルームフィルタは、コンピュータがある要素が集合の中にあるかどうかを確認するためのデータ構造です。ハッシュ関数を用いて、追加された各要素のハッシュ値を計算し、集合内の他の要素と比較することによってこれを行います。
Q:ブルームフィルタとはどのようなデータ構造ですか?
A:ブルームフィルタは確率的なデータ構造です。つまり、偽陽性を得る可能性はありますが、偽陰性を得る可能性はありません。
Q:ブルームフィルタを提案したのは誰ですか?
A:エドワード・ブルームが1970年にブルームフィルタを提唱しました。
Q:エドワードが提案した手法の使用例とは?
A:エドワードは約50万語のハイフン処理の例で、彼の技術を用いると、ほとんどのルックアップがなくなり、ディスクアクセスも15％削減できることを発見した。
Q:誤検出確率が1％の場合、1要素あたり何ビットが必要ですか?
A: 誤検出確率を1%にするためには、集合のサイズや要素数に関係なく、1要素あたり10ビット以下が必要です。
Q: ブルームフィルターに追加された要素を削除することは可能ですか?
A: いいえ、要素は集合に追加されるだけで、削除されることはありません。
Q: 要素を追加すると、偽陽性になる確率は高くなりますか、低くなりますか?
A: 要素を追加すると、誤検出の確率が高くなります。
