Bloom Filter

🔥 Vibe プロンプト

「100万件のメールが新規か既存か確認。1%誤判定率のBloom Filterを使用。HashSetとのメモリ比較。」

Bloom Filterとは？

Bloom Filter は、1970年にBurton Howard Bloomによって発明された、省メモリな確率的データ構造です。要素が集合に属するかをテストでき、誤検出（false positive）はあり得るが、誤否定（false negative）は絶対にないという特性を持ちます。

| 性質 | 保証 | |------|------| | check()がFalseを返す | 要素は絶対に集合に含まれない ✅ | | check()がTrueを返す | 要素は含まれている可能性あり（誤検出の可能性あり） ⚠️ |

このトレードオフにより、膨大なメモリ節約が可能です。1%の誤検出率のBloom Filterは100万アイテムに約1.2 MBしか使いませんが、HashSetは約50 MB必要です — 97.6%の節約です。

仕組み

1. mビットのビット配列を用意し、すべて0に初期化
2. k個の独立したハッシュ関数を選ぶ
3. 要素の追加 → k個のハッシュ関数でハッシュ → 対応ビットを1に設定
4. 要素の確認 → k個のハッシュ関数でハッシュ
   - 1つでも0があれば → 要素は存在しない（100%確実）
   - すべて1なら → 要素は存在する可能性あり

数学的基礎

最適パラメータは以下の式で計算されます：

m = -(n * ln(p)) / (ln(2)²)    ← 最適ビット配列サイズ
k = (m / n) * ln(2)            ← 最適ハッシュ関数数

ここで:
  n = 予想要素数
  p = 目標誤検出率（例: 0.01 = 1%）
  m = ビット配列のサイズ
  k = ハッシュ関数の数

例: 100万アイテム、1%誤検出率

m = -(10^6 * ln(0.01)) / (ln(2)²)
m ≈ 9,585,058 ビット ≈ 1.14 MB

k = (9,585,058 / 1,000,000) * ln(2)
k ≈ 6.64 → 7 ハッシュ関数

結果: 100万アイテムに約1.14 MBと7個のハッシュ関数のみ！

実装

import math
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, n, fp_prob):
        """
        n: 保存する予想要素数
        fp_prob: 目標誤検出率（例: 0.01 = 1%）
        """
        self.fp_prob = fp_prob
        self.size = self._get_size(n, fp_prob)
        self.hash_count = self._get_hash_count(self.size, n)
        self.bit_array = bitarray(self.size)
        self.bit_array.setall(0)
    
    def _get_size(self, n, p):
        """最適ビット配列サイズmを計算"""
        m = -(n * math.log(p)) / (math.log(2) ** 2)
        return int(m)
    
    def _get_hash_count(self, m, n):
        """最適ハッシュ関数数kを計算"""
        k = (m / n) * math.log(2)
        return int(k)
    
    def add(self, item):
        """アイテムをBloom Filterに追加"""
        for i in range(self.hash_count):
            digest = mmh3.hash(str(item), i) % self.size
            self.bit_array[digest] = True
    
    def check(self, item):
        """アイテムが存在する可能性があるか確認"""
        for i in range(self.hash_count):
            digest = mmh3.hash(str(item), i) % self.size
            if not self.bit_array[digest]:
                return False  # 絶対に存在しない
        return True  # 存在する可能性あり（誤検出の可能性）

# 使用例
bf = BloomFilter(1000000, 0.01)
print(f"ビット配列サイズ: {bf.size/1024/1024:.2f} MB")
print(f"ハッシュ関数数: {bf.hash_count}")
print(f"目標誤検出率: {bf.fp_prob:.1%}")

# 1万件のメールを追加
for i in range(10000):
    bf.add(f"user_{i}@gmail.com")

# テスト
print(f"\n既知のメール: {bf.check('user_123@gmail.com')} (Trueであるべき)")
print(f"未知のメール: {bf.check('fake_email@gmail.com')} (Falseであるべき)")

# 実際の誤検出率を測定
test_size = 10000
false_positives = sum(
    1 for i in range(test_size)
    if bf.check(f"not_in_set_{i}@test.com")
)
print(f"\n実測誤検出率: {false_positives/test_size:.4%} (目標: {bf.fp_prob:.1%})")

メモリ比較

| データ構造 | 100万アイテム | メモリ | 備考 | |-----------|-------------|--------|------| | HashSet | 100万文字列 | ~50 MB | 100%正確 | | Bloom Filter (1% FP) | 100万アイテム | ~1.2 MB | 97.6%節約 | | Bloom Filter (0.1% FP) | 100万アイテム | ~1.8 MB | 96.4%節約 | | Bloom Filter (0.01% FP) | 100万アイテム | ~2.4 MB | 95.2%節約 |

実世界の応用

1. キャッシュフィルタリング（キャッシュ貫通防止）

Webサーバーがキーに対するリクエストを受けたとき、まずBloom Filterをチェック。フィルターが「存在しない」と言えば、キャッシュルックアップを完全にスキップ — これによりデータベースへの負荷を防ぎます。

2. WebクローラーのURL重複排除

検索エンジンのクローラーは訪問済みURLを追跡するためにBloom Filterを使用します。数十億のURLがある場合、Bloom FilterはHashSetと比較してテラバイト単位のRAMを節約します。

3. スパム検出

メールサービスは既知のスパム送信者アドレスのBloom Filterを維持します。「絶対にない」と判定された送信者のメールは迅速に配信され、「可能性がある」場合はより詳細なチェックが行われます。

4. データベースクエリ最適化

Apache CassandraはBloom Filterを使用して、SSTableに行が存在するかどうかを素早く判定し、不要なディスクI/Oを回避します。

時間複雑度

| 操作 | 時間複雑度 | |------|-----------| | add(item) | O(k) — k個のハッシュ関数 | | check(item) | O(k) — k個のハッシュ関数 | | 空間 | O(m) — mビットの配列 |

制限事項

| 制限 | 説明 | |------|------| | 削除不可 | 標準BFは削除をサポートしない（Counting BFを使用） | | 誤検出 | メモリ効率とのトレードオフ | | FP率が増加 | 予想nを超えて追加するとFP率が上昇 | | 列挙不可 | 保存されたアイテムを一覧表示できない |

まとめ

省メモリな確率的データ構造
100%再現率 — 誤否定がないことを保証
設定可能な誤検出率（メモリと精度のトレードオフ）
k個の独立したハッシュ関数を使用してアイテムをビット位置にマッピング
データベース、キャッシュ、分散システムで広く使用