ブルームフィルター101

エンティティが特定のデータセットに高速で存在しているかどうかを判断するために、どのようなデータ構造を使いますか?多くの人は「ハッシュテーブル」とためらうことなく答えます。ハッシュテーブルはエンティティ群の中でエンティティにアクセスする際に良好に機能します。読み取り操作の平均時間計算量は一定です。しかし、大規模なデータセットを扱う場合、ハッシュテーブルの使用はかなりコストがかかることがあります。ハッシュテーブルはデータセット内のすべてのエンティティを追跡する必要があるため、空間の複雑さは線形になります。

Hashtableのより良い代替案はありますか?質問してみると良いかもしれません。答えは「はい」ですが、精度を犠牲にする意思があることを条件にします。この記事では、Bloom Filterを紹介します。これは、より空間複雑度の高いデータセットに属しているかどうかを確認するための代替手段であり、精度は低下します。

ブルームフィルターとは何か

ブルームフィルターは、アイテムが集合に属しているかどうかを判定するための空間効率の良い確率的データ構造です。Hashtableと同様に、ブルームフィルターもハッシュ処理を利用しています。しかし、Hashtableとは異なり、Bloom Filterは追加されたアイテムを保存しません。代わりに、追加されたアイテムのハッシュ値を計算し、その値を集合内に存在しているとマークします。したがって、Hashtableほど多くのスペースを必要としないため、優れた空間計算量が得られます。

しかし、ここでは空間効率と正確さのトレードオフを行っています。アイテムをブルームフィルターに保存しないことで、アイテムが集合に属しているかどうかを確実に判断する能力も失われます。これはハッシュテーブルを使う際に当然のように使われている点です。アイテムがブルームフィルターに存在するかどうか知りたいときは、そのアイテムのハッシュ値を計算し、そのハッシュ値がブルームフィルターに存在しているか確認します。偽陽性は気にしますが、偽陰性は気にしません。言い換えれば、ブルームフィルターがアイテムが集合に属さないと主張した場合、その主張の正確性は100%保証されます。しかし、ブルームフィルターが行う逆の主張が常に正しいとは限りません。

ブルームフィルターを使うタイミング

前述の通り、ブルームフィルターは、精度よりもスペース効率(特に誤検知の有無)を重視する場合、Hashtableの理想的な代替手段です。悪意のあるURL検出器はその一例です。数百万の悪意あるURLを収集したとしましょう。もしHashtableで悪意のあるURL検出器を作るなら、すべての悪意のあるURLをHashtableにダンプしなければなりません。検索は遅くなり、URLは多くの容量を消費します。この検出器は高い精度を持っています。しかし、必ずしも正確である必要はありません。悪意のあるURL検出器の目的は悪意のあるURLからユーザーを守ることにあるからです。検出器が悪意のあるURLを安全なURLと間違えない限り、その役割を果たしたと言えます。

比較すると、Bloom Filterで悪意のあるURL検出器を構築することで、空間の複雑さの両面でより良いパフォーマンスが得られます。また、Bloom Filterは安全とマークされたすべてのURLが常に安全に開けるようにし、ユーザーを悪意のあるURLから守ることができます。唯一の欠点は、悪意のあるURL検出器が誤検知に悩まされていることであり、悪意のあるURLが安全である可能性が高いことです。しかし、この欠点は、必要な容量が少なく、検出速度が速くなる利点によって上回ります。

偽陽性の除去が重要な場合でも、Bloom Filterを使うことは可能です。しかし、Bloom Filterが陽性の結果を返した後に重要なステップを加える必要があります。陽性が偽陽性(陰性の偽装)でないことを確認するために、元のデータソース(データベースなど)を参照し、陽性の結果が正しいかどうかを確認します。陰性の結果については同じ手順を行う必要がなく、すべての陰性結果は確実に正しいです。

この記事では、Bloom Filterとは何か、どのように機能し、いつ使うべきかについて解説しました。Bloom FilterはHashtableの代替手段ですが、それぞれに利点と欠点があります。次にどの機能を使うか決める際には、この点を念頭に置いてください。