アルゴリズム・データ構造図鑑 · 基礎から応用へ

Bloomフィルタ:存在しないことを小さな領域で判定する

偽陽性を許す代わりに、不要な検索を減らすビット配列の仕組みを説明する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. ビット配列へ複数の印を付ける
  2. 小さな例で偽陽性を見る
  3. 領域・個数・ハッシュ回数の関係
  4. 確定検索の前に置く
  5. この記事をロゲイアに質問する理解を確かめる

ビット配列へ複数の印を付ける

標準的なBloomフィルタは、最初はすべて0のビット配列と複数のハッシュ計算を使います。キーを追加するとき、そのキーから得られる複数の位置を1にします。元のキーや値そのものは保存しません。検索では同じ位置を調べ、一つでも0があれば、そのキーは追加されていません。すべて1の場合は、他のキーが付けた印かもしれないため、「存在する可能性がある」という答えになります。

小さな例で偽陽性を見る

8ビットの配列を考え、キーAが位置1と4を、Bが位置3と6を1にしたとします。未登録のCが位置1と6へ対応すると、両方が既に1なので存在候補と判定されます。これは偽陽性です。一方、Dが位置2と4へ対応し、位置2が0なら確実に未登録と判定できます。追加後にビットを壊さず、同じハッシュ規則を使うという条件下では、登録済みキーを未登録と答える偽陰性は生じません。

領域・個数・ハッシュ回数の関係

登録数に対してビット数が少ないと、1が増えて偽陽性が出やすくなります。ハッシュ回数を増やすと検索時の確認は増えますが、追加時により多くのビットも1になります。そのため回数を増やし続ければ必ず改善するわけではありません。一般的な近似モデルでは、ビット数m、登録数n、ハッシュ数kから偽陽性率を見積もりますが、ハッシュの独立性などの仮定と、実際の登録数を確認して容量設計します。

確定検索の前に置く

たとえばストレージへ問い合わせる前にBloomフィルタを見て、未登録と分かるものを省略します。存在候補と答えた場合には、本体で確定検索を行います。アクセス許可のように誤判定が許されない最終判断を、フィルタだけに任せてはいけません。また標準のビット配列では、あるキーを削除するために印を0へ戻すと、同じ印を共有する別のキーを壊します。削除が必要ならCounting Bloomフィルタなど別の設計を検討します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ