C++ で Bloom Filter を実装してみた

Bloom Filter を勉強する機会があったので、実装してみた。

概要

Bloom Filter 自体の説明はよそに譲るとして、ざっくり特徴を言うと、

  • 二分木やハッシュテーブル等のデータ構造と比べると、はるかにメモリ効率が良い
    • キーの値をメモリ上で格納する必要がない
    • 逆に言うと、キーの集合を復元できない
  • false positive(追加していないキーに対して true と返す誤り)による誤検出の可能性があるが、false negative(追加しているキーに対して、false と返す誤り)はない
    • false positive する確率は 1 – exp(- k * n / m)) * k の式から算出できる
      • パラメータ k: ハッシュ関数の個数、n: 追加する要素数, m: ビット列の長さ
      • 要素を追加するほど、false positive が起きやすい
        • n = 10 のとき 0.028, n = 100 のとき 0.254, n = 1000 のとき 0.947

Bloom Filter

コード

実行例

応用

Bloom Filter の応用をいくつか紹介。

まとめ

使いドコロが難しそうだけど、false positive が起こっても許容できる状況では威力を発揮しそうですね!

参考リンク

Leave a Reply

Your email address will not be published. Required fields are marked *