2025/06/29 11:56 Bloom Filters by Example
やあ、ロボ子！今日はBloom Filterについて話すのじゃ。
Bloom Filterですか、博士。名前は聞いたことがありますが、詳しくは知りません。
Bloom Filterは、ある要素が集合に存在するかどうかを高速かつ省メモリで判定するためのデータ構造のことじゃ。簡単に言うと、あるものが「絶対ない」か「あるかも」かを判断できる魔法のフィルターみたいなものじゃな。
なるほど、確率的なデータ構造なのですね。ビットベクトルを使うと書いてありますね。
そうじゃ！要素を追加するときは、ハッシュ関数を使ってビットベクトルの特定の位置を1にするのじゃ。そして、存在を確認するときは、同じハッシュ関数で確認して、全部1なら「あるかも」、一つでも0なら「絶対ない」と判断するのじゃ。
ハッシュ関数が重要そうですね。記事には、高速なハッシュ関数の例としてMurmur、xxHash、fnvなどが挙げられていますね。
その通り！ハッシュ関数が速いほど、Bloom Filterも速くなるのじゃ。実際、md5からMurmurに切り替えるだけで、800%も高速化された例もあるみたいじゃぞ。
それはすごいですね！色々な実装で使われているハッシュ関数も紹介されていますね。ChromiumはMurmur、RedisBloomもMurmurを使っているんですね。
ふむ、偽陽性率（実際にはないものを「ある」と判断する確率）は、Bloom Filterのサイズで調整できるのじゃ。サイズが大きければ大きいほど、偽陽性率は低くなるぞ。
ハッシュ関数の数も重要ですよね。多すぎると遅くなり、少なすぎると偽陽性が増える、と。
そうじゃ！最適なハッシュ関数の数は、k = (m/n)ln(2) で計算できるらしいぞ。ここで、mはビット数、nは挿入された要素数じゃ。
なるほど。挿入とメンバーシップテストはO(k)で、空間効率は許容できるエラー率に依存するんですね。
Bloom Filterは、データベースの検索やネットワークのルーティングなど、様々な場所で使われているのじゃ。C. Titus Brownさんのバイオインフォマティクスへの応用に関する講演も参考になるみたいじゃな。
ありがとうございます、博士。Bloom Filterについてよく理解できました。
どういたしましてじゃ。ところでロボ子、Bloom Filterを使って、私がおやつを隠した場所を当てるゲームでもしてみるかの？
それは面白そうですが、博士のことですから、きっと偽陽性率が非常に高いBloom Filterになっているでしょうね…。
むむ、よくわかっておるの。正解！実は全部私のお腹の中なのじゃ！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。