ブルームフィルタを例で理解する

 (llimllib.github.io)
2 ポイント 投稿者 GN⁺ 2025-07-01 | 1件のコメント | WhatsAppで共有
  • ブルームフィルタは、大きな集合に含まれるかどうかを少ないメモリで素早くふるい分けるデータ構造で、「確実に存在しない」と「存在する可能性がある」だけを区別する
  • 中核となるのは ビットベクタと複数のハッシュ関数で、挿入時にはハッシュ結果が指す位置のビットを 1 に変更する
  • 参照時には同じ位置を確認し、1つでも 0 があれば除外できるが、すべて 1 でも 偽陽性の可能性は残る
  • ハッシュ関数は独立していて一様分布に近く、かつ高速である必要があり、md5 から murmur に変更して約 800% の速度向上を得た事例がある
  • フィルタの精度とコストは、想定される要素数 n、ビット数 m、ハッシュ数 k のバランスに依存し、挿入と参照はいずれも O(k) 程度である

ブルームフィルタの動作方式

  • ブルームフィルタは、要素が集合に含まれるかどうかを高速かつメモリ効率よく判定する確率的データ構造である
  • 結果は2種類に限定される
    • 要素が集合に 確実に存在しない
    • 要素が集合に 存在する可能性がある
  • 内部構造は ビットベクタであり、要素を追加するときに入力を複数のハッシュ関数に通す
  • 各ハッシュ値が指すビットインデックスを 1 に設定すれば挿入は完了する
  • 例では Fnv と Murmur が単純なハッシュ関数として使われている

含有判定と偽陽性

  • 参照でも挿入時と同じハッシュ関数群を使用する
  • ハッシュ値が指すビットのうち1つでも 0 であれば、その要素は 確実に集合に存在しない
  • 関連するビットがすべて 1 であれば、その要素が 存在する可能性がある
    • 同じビットが、別の1つの要素、または複数の要素の組み合わせによってすでに設定されている可能性がある
  • この衝突のため、ブルームフィルタには 偽陽性(false positive) の可能性が存在する

ハッシュ関数の選択基準

  • ブルームフィルタのハッシュ関数は 独立していて 一様分布に近く、できるだけ高速である必要がある
  • sha1 のような暗号学的ハッシュは広く使われているが、ブルームフィルタにとって常に良い選択とは限らない
  • 高速で単純なハッシュの例は次のとおり
  • ブルームフィルタ実装を md5 から murmur に変更した後、約 800% の速度向上を得た 事例 がある

実装で実際に使われるハッシュ

  • 複数の実装が、ブルームフィルタにそれぞれ異なるハッシュ関数を使用している
    • Chromium: murmur を使用
    • Plan9: Mitzenmacher 2005 で提案された単純なハッシュを使用
    • Sdroege Bloom filter: fnv1a を使用
    • Squid: MD5 を使用
    • RedisBloom: murmur を使用
    • Apache Spark: murmur を使用
    • influxdb: xxhash を使用
    • bloomd: 最初の2つのハッシュは murmur、次の2つのハッシュは SpookyHash、以降のハッシュはその2つの組み合わせを使用
    • fleur, flor, bloom: fnv を使用
    • Sqlite: 分析クエリ用のブルームフィルタを追加
    • RocksDB: 設定可能で、ソースでは xxhash 系の xxh3 が最も良かったとしている
    • ScyllaDB: murmur を使用

フィルタサイズとハッシュ関数の数を決める

  • ブルームフィルタは 偽陽性率を調整できる
    • より大きいフィルタでは偽陽性が減る
    • より小さいフィルタでは偽陽性が増える
  • 偽陽性率はおおよそ (1-e^-kn/m)^k で計算される
    • n: 挿入されると想定される要素数
    • m: フィルタのビット数
    • k: ハッシュ関数の数
  • ハッシュ関数が多いほど参照と挿入は遅くなり、フィルタもより早く埋まる
  • 逆にハッシュ関数が少なすぎると 偽陽性が過度に多くなる可能性がある
  • 与えられた m と n に対する最適な k は (m/n)ln(2) として選べる
  • フィルタサイズは次の手順で合わせてみることができる
    • 想定 n の値をおおよそ決める
    • m の値を選ぶ
    • 最適な k の値を計算する
    • 選んだ n、m、k で誤り率を計算する
    • 誤り率を許容しにくい場合は m を変えて再計算する

性能と適した利用条件

  • m ビットと k 個のハッシュ関数を持つブルームフィルタでは、挿入と含有判定はいずれも O(k) である
  • 要素を追加または参照するときは、要素を k 個のハッシュ関数に通し、該当するビットを設定または確認すればよい
  • 空間効率は許容できる誤り率によって変わる
  • 挿入可能な要素の範囲が非常に限定されている場合は、決定的な ビットベクタのほうがよい場合がある
  • 挿入される要素数を大まかにでも推定できない場合は、ハッシュテーブルや scalable Bloom filter のほうが適している場合がある

参考資料と活用例

関連記事

1件のコメント

 
GN⁺ 2025-07-01
Hacker News のコメント

  • この記事はまさに自分のような人に向けたものだった。Bloom フィルタという名前は聞いたことがあり、話題に出るたびに調べようと思うだけだったが、この記事を見てようやく調べたところ、自分が求めていた入門として完璧だった :)

    • 10年以上前に iBooks の検索機能向けに実装する仕事を任されて、Bloom フィルタを知った
    • 本当に面白い構造だ。Bloom フィルタが必要になる問題に出会うとわくわくするが、残念ながら分野によってはそういう機会は少ないこともある

  • 2009年に大学で CUDA を使って Bloom フィルタを作った。指導教員は元 Nvidia の人だった。ところが、その後のキャリアでは GPU プログラミングをまったくしなくなった
    あのとき別の選択をしていれば、1億ドルは稼げていたかもしれない

    • 自分も似たようなものだ。2009年に好奇心から GeForce 8 で CUDA v1 を使い、GPU 最適化されたバイオインフォマティクス・ツールキットのごく初期版のようなものを作ったと思う
      その後は別の仕事に行って、大金を逃した
    • 1970年に出たコンピュータサイエンスのアイデアだという点を考えると、その可能性は低そうだ。汎用 GPU で試す価値のあるアイデアは、すでに誰もが狙えたはずだ
      10年前に GPU で hashcash 実装を作ったが、今ではほとんど価値がないと思う
    • 学部の優等プロジェクトで機械学習アルゴリズムを CUDA に移植したあと、ただ肩をすくめて組み込みプログラミングに進んだ
    • Bitcoin を買っていても、ずっと多く稼げていただろう

  • 著者へのメモ: インタラクティブ部分が本当に良い。要点をさらに明確に見せるなら、ハッシュ衝突を起こす2つの文字列の例を示し、片方を最初の入力欄に入れさせて、もう片方を2つ目の欄で検査させると良さそうだ
    そうすれば、答えがなぜ常に「集合に含まれている可能性がある」であって「含まれている」ではないのかを示せる

    • "bloom" と "demonstrators " が衝突する。後ろの文字列末尾の空白文字に注意
      どちらも fnv: 7、murmur: 12 で衝突する

  • 自分の好きな小技が一つある。小さい可能性のある集合に対してメンバーシップ検査を大量に行う必要がある場合、64ビット Bloom フィルタを非常に単純なハッシュ関数と一緒に、投機的に付け足せる
    ものすごく馬鹿げて聞こえるが、コストがあまりに小さいので賭けとして試す価値がある。うまくいかなくても挿入とメンバーシップ検査におよそ10ns足す程度だが、うまくはまれば膨大な作業量を減らせる

    • Chromium もいろいろな場所でこれをやっている。記事では Safe Browsing が murmur を使う例だけリンクしていたが、レンダラーである Blink は通常 rapidhash を使い、この種のマイクロフィルタをあちこちで使っている
      たとえば特定ケースの querySelector()、CSS バケットでのハッシュ検索の事前フィルタリング、アクセシビリティ向けに特定の Aria 属性を探す際に要素を素早く棄却する用途などだ。32ビットや64ビットの極小フィルタが機能するのは驚きだが、実際にはよく効く。より大きな Bloom フィルタも一部ある。このうちいくつかは自分が追加した

  • ChatGPT に Python で作ってもらい、基本的な md5 ダイジェストを切り分けて複数のハッシュのように使う方式を使った。重要でない用途なら問題なさそうだ

  • Bloom フィルタの別の可視化は、このページの末尾で見られる:
    https://www.chrislaux.com/hashtable.html

  • 以前見たことがあると思っていたが、実際にはこちらの別ページだった: https://bdupras.github.io/filter-tutorial/
    このページは Bloom フィルタと cuckoo フィルタを比較していて、情報が少し追加されている

  • 最近、Bloom フィルタで ログメッセージのスパム防止機能を実装した。ロガーでメッセージをハッシュしてフィルタに入れ、項目があればメッセージを出力しないようにした
    数秒ごとにフィルタを巡回して全ビットを消していたが、フィルタの全ビットをアトミックに消す問題を気にしなくてよかったのでうまく合っていた。メッセージが入ってくる途中で、そのうち一部のビットが消えるだけでも、再びログに出るには十分だった。以前の実装は見たメッセージ数を数え、N で飽和する方式で、特定のメッセージが繰り返し出ると、フィルタが消される速度以下でしか見えなくなる効果があった
    Bloom フィルタのことを知ってはいたものの、このように自然に実用途を見つけて大きな改善を生めたのはかなり満足感があった

  • さらに読みたいなら、Eli Bendersky の Bloom フィルタ記事も良かった:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Bloom フィルタ、集合、ハッシュテーブルを理解するのに必要な概念は、体感では95%ほど重なっている。集合は値ではなくキーだけを気にするメンバーシップ検査用のハッシュテーブルであり、Bloom フィルタは多対一ハッシュが衝突によってキー空間を「圧縮」するという事実を利用する集合だ
    意図的に衝突が多く起きるハッシュ関数を使っているようなものだ。特定のキーが一度でもハッシュされていれば必ず一致と出るが、同じハッシュを作った別のキーがあるかもしれない。バグではなく機能だ

    • Bloom フィルタを、実データは追跡せずデータがあるバケットだけを追跡するハッシュテーブルとして理解しているのが自分だけではなくてうれしい
    • この説明で抜けている重要点は、Bloom フィルタが衝突を減らすために複数のハッシュ関数を使うことだ。たとえばハッシュが3つなら、あるキーが集合に含まれると判断されるには3つのハッシュすべてが一致しなければならない
      こうすることで偽陽性の衝突確率を下げつつ、偽陰性がないという保証は維持できる
    • Bloom フィルタをきちんと理解していれば、ランダム射影や局所性鋭敏型ハッシュの一部実装を理解するところまで、ほとんど到達している