✍️ 필사 모드: 確率的データ構造 完全ガイド 2025: Bloom Filter、HyperLogLog、Count-Min Sketch、実戦活用

TL;DR

• 確率的データ構造の本質: 100% の精度を捨てて、メモリ／速度を極端に節約
• Bloom Filter: 「この要素は集合にあるかもしれない」 — false positive あり、false negative なし。RocksDB、Cassandra、BigTable の中核
• HyperLogLog: 12KB で数十億要素のユニークカウント。Redis PFADD/PFCOUNT、BigQuery、Druid で使用
• Count-Min Sketch: ストリームで要素頻度を推定。ホットキー検出、DDoS 検出
• トレードオフ: 精度 vs メモリ vs 速度 — 正確な答えが不要なときに爆発的な効率

1. 確率的データ構造とは？

1.1 中心アイデア

「100% 正確な答えが要らないなら、メモリと速度を極端に節約できる。」

伝統的なデータ構造:

• HashMap で 100 万要素を保存 → 約 50 MB
• 「この要素はあるか？」 → 正確な答え

確率的データ構造:

• Bloom Filter で 100 万要素を保存 → 約 1 MB（50 倍の節約！）
• 「この要素はあるか？」 → 「あるかもしれない」または「確実にない」

トレードオフ: メモリ 50 倍節約 + わずかな false positive（1%）。

1.2 なぜ必要か？

大規模システムでは:

• メモリは高い — RAM はディスクの 100 倍以上
• L1/L2 キャッシュに乗ると速い → 小さいほど良い
• 数十億要素 — HashMap は不可能
• 分散システム — 小さいデータはネットワーク効率的

1.3 精度が不要なケース

2. Bloom Filter — 最も有名な確率的データ構造

2.1 原理

ビット配列 + 複数のハッシュ関数。

挿入:

1. 要素を K 個のハッシュ関数に通す → K 個のインデックス
2. 各インデックスのビットを 1 に設定

照会:

1. 同じ K 個のハッシュ関数
2. すべてのインデックスのビットが 1 なら → 「あるかもしれない」
3. 1 つでも 0 なら → 「確実にない」

2.2 可視化

ビット配列（8 ビット）:  [0, 0, 0, 0, 0, 0, 0, 0]

"apple" を挿入 (hash → [1, 4]):
                  [0, 1, 0, 0, 1, 0, 0, 0]

"banana" を挿入 (hash → [3, 6]):
                  [0, 1, 0, 1, 1, 0, 1, 0]

"apple" を照会 (hash → [1, 4]): 両方 1 → 「あるかもしれない」 OK
"grape" を照会 (hash → [2, 5]): 0 がある → 「確実にない」 NG
"cherry" を照会 (hash → [1, 6]): 偶然両方 1 → 「あるかもしれない」 (false positive)

2.3 false positive 率の計算

数式:

P(fp) = (1 - e^(-k*n/m))^k

• n: 要素数
• m: ビット数
• k: ハッシュ関数の数

最適な k:

k = (m/n) * ln(2)

1% の false positive が目標なら:

m/n ≈ 9.6 ビット
k ≈ 7

100 万要素 = 1.2 MB + 7 つのハッシュ関数 = HashMap より 50 倍小さい。

2.4 Python 実装

import hashlib
import math

class BloomFilter:
    def __init__(self, n, fp_rate):
        self.size = -int(n * math.log(fp_rate) / (math.log(2) ** 2))
        self.hash_count = int(self.size / n * math.log(2))
        self.bits = [0] * self.size

    def _hashes(self, item):
        for i in range(self.hash_count):
            h = hashlib.md5(f"{item}{i}".encode()).hexdigest()
            yield int(h, 16) % self.size

    def add(self, item):
        for h in self._hashes(item):
            self.bits[h] = 1

    def contains(self, item):
        return all(self.bits[h] for h in self._hashes(item))

# 使用例
bf = BloomFilter(n=1000000, fp_rate=0.01)
bf.add("alice@example.com")
print(bf.contains("alice@example.com"))  # True
print(bf.contains("bob@example.com"))    # ほぼ常に False

2.5 Bloom Filter の限界

• 削除不可 — ビットを 0 に戻すと他の要素に影響
• リサイズが困難 — 新しいフィルタを作りすべての要素を再挿入する必要がある
• カウント不可 — 何個入っているか分からない

解決策: Counting Bloom Filter、Cuckoo Filter（下記参照）。

2.6 Bloom Filter の実戦活用

RocksDB / Cassandra / BigTable

LSM ツリーベースの DB で、SSTable ごとに Bloom Filter:

クエリ: "key123"

SSTable 1 の Bloom Filter: 「確実にない」 → ディスク読まない OK
SSTable 2 の Bloom Filter: 「確実にない」 → ディスク読まない OK
SSTable 3 の Bloom Filter: 「あるかもしれない」 → ディスク読む（実際の検索）

効果: ディスク I/O 99% 削減。SSTable 全体を読まない。

CDN キャッシュ

リクエスト: GET /image/123.jpg

Bloom Filter: 「キャッシュにない」 → 即 origin にリクエスト（キャッシュ lookup 省略）
              「あるかもしれない」 → キャッシュ lookup

効果: キャッシュミス時の時間節約。

パスワード漏洩検査

HaveIBeenPwned の 1 億以上のパスワードデータベース → クライアントが直接確認可能（Bloom Filter をダウンロード）。

Chrome 悪意のある URL 検査

Google が既知の悪意ある URL データベースを → Bloom Filter としてクライアントに送信 → ブラウザが即確認。

3. Counting Bloom Filter

3.1 問題の解決

基本の Bloom Filter は削除不可能。Counting Bloom Filter はビットの代わりにカウンターを使用:

配列: [0, 0, 0, 0, 0, 0, 0, 0]  (各セルが 4 ビットのカウンター)

"apple" を挿入 ([1, 4]):
        [0, 1, 0, 0, 1, 0, 0, 0]

"apple" をさらに挿入:
        [0, 2, 0, 0, 2, 0, 0, 0]

"apple" を削除:
        [0, 1, 0, 0, 1, 0, 0, 0]

3.2 欠点

• メモリ 4 倍 — 1 ビット → 4 ビット（オーバーフロー防止のため）
• 依然として false positive あり

3.3 Cuckoo Filter（代替）

Cuckoo Filter は Bloom Filter より優れた代替:

• 削除可能
• false positive 率がより低い
• メモリ効率は同程度
• 「Cuckoo hashing」ベース

# pycuckoofilter の例
from cuckoofilter import CuckooFilter

cf = CuckooFilter(capacity=1000000, error_rate=0.01)
cf.insert("alice")
print(cf.contains("alice"))  # True
cf.delete("alice")  # 可能！

Cuckoo > Bloom のとき: 削除が必要なとき、より低い false positive が必要なとき。

4. HyperLogLog — カーディナリティ推定

4.1 問題

「今日我々のサイトに何人のユニーク訪問者が来たか？」

伝統的な方法: HashSet にすべての訪問者 ID を保存 → 1000 万訪問者 = 800 MB。

HyperLogLog: 12 KB で数十億要素まで推定。1% 誤差。

4.2 基本アイデア

要素をハッシュ → 二進数の先頭 0 の数を追跡。

"alice" → hash → 00000010110...  (先頭 0 が 5 個)
"bob"   → hash → 00100110...     (先頭 0 が 2 個)
"carol" → hash → 0001110...      (先頭 0 が 3 個)

観察: ランダムハッシュで K 個の先頭 0 が出る確率は 1/2^K。

→ 「最大で先頭 0 が 5 個出た」 → 約 2^5 = 32 個のユニーク要素と推定。

現実: 単一の測定は不正確。複数のバケットに分けて平均 → 精度向上。これが HyperLogLog。

4.3 精度

核心: メモリは要素数に無関係！1 億要素でも 100 万要素でも同じメモリ。

4.4 Redis HyperLogLog

PFADD visitors:2025-04-15 "user1" "user2" "user3"
PFADD visitors:2025-04-15 "user1"  # 重複は無視
PFCOUNT visitors:2025-04-15  # 約 3 (2 または 3)

# 複数の HLL をマージ
PFMERGE visitors:week visitors:2025-04-14 visitors:2025-04-15

4.5 HyperLogLog の実戦活用

日次アクティブユーザー（DAU）

import redis

r = redis.Redis()

def track_user(user_id):
    today = datetime.now().strftime("%Y-%m-%d")
    r.pfadd(f"dau:{today}", user_id)

def get_dau(date):
    return r.pfcount(f"dau:{date}")

数億ユーザーでも 12 KB で処理可能。

ユニーク IP カウント（DDoS 分析）

PFADD unique_ips:2025-04-15 "1.2.3.4" "5.6.7.8"
PFCOUNT unique_ips:2025-04-15

Big Data — BigQuery、Druid

SELECT APPROX_COUNT_DISTINCT(user_id) FROM events;

内部的に HyperLogLog を使用。正確な COUNT(DISTINCT) より 100 倍以上高速。

5. Count-Min Sketch — 頻度推定

5.1 問題

ストリームで「各要素は何回現れたか？」

伝統的: HashMap → メモリ急増。

Count-Min Sketch: 小さいメモリで頻度推定。

5.2 原理

2D 配列（d × w） + d 個のハッシュ関数。

挿入:

• 各ハッシュ関数でインデックスを計算
• 該当カウンターをインクリメント

照会:

• 同じハッシュ関数
• それらのカウンターの中の最小値を返す（だから "Count-Min"）

5.3 可視化

配列 (3 x 5):
[0, 0, 0, 0, 0]  ← hash1
[0, 0, 0, 0, 0]  ← hash2
[0, 0, 0, 0, 0]  ← hash3

"apple" を 5 回挿入:
hash1("apple") = 1 → カウンター [0, 5, 0, 0, 0]
hash2("apple") = 3 → カウンター [0, 0, 0, 5, 0]
hash3("apple") = 0 → カウンター [5, 0, 0, 0, 0]

"banana" を 2 回挿入:
hash1("banana") = 4 → [0, 5, 0, 0, 2]
hash2("banana") = 1 → [0, 2, 0, 5, 0]
hash3("banana") = 2 → [5, 0, 2, 0, 0]

"apple" 照会: min(5, 5, 5) = 5 OK
"banana" 照会: min(2, 2, 2) = 2 OK

衝突発生時: 他の要素と衝突するとカウンターが膨らむが、最小値を取るので常に真のカウント以上（overestimate）。

5.4 精度

誤差 ε、信頼度 1-δ
必要なサイズ:
  w = ⌈e/ε⌉
  d = ⌈ln(1/δ)⌉

例: 1% 誤差、99% 信頼度 → w=272、d=5 → 1360 カウンター = 5 KB。数十億要素の処理が可能。

5.5 実戦活用

ホットキー検出（Heavy Hitters）

# 最も頻出するキーを見つける
sketch = CountMinSketch(width=272, depth=5)

for query in stream:
    sketch.add(query)

# Top-K の発見（separate min-heap を使用）

Memcached の LRU の代替

tinylfu キャッシュは Count-Min Sketch で頻度を追跡 → よく使われるキーだけをキャッシュに保持。

DDoS 検出

各 IP のリクエスト数を推定 → 閾値超過時にブロック。

Apache Spark、Flink

大規模ストリーム処理での頻度分析。

6. MinHash — Jaccard 類似度

6.1 問題

「2 つの集合はどれだけ似ているか？」（Jaccard 類似度）

J(A, B) = |A ∩ B| / |A ∪ B|

伝統的方法: すべての要素を比較 → O(|A| × |B|)。

6.2 MinHash の原理

各集合の「最小ハッシュ値」が同じになる確率 = Jaccard 類似度。

def minhash(set_, num_hashes=128):
    return [min(hash(item, seed=i) for item in set_) for i in range(num_hashes)]

# 2 つの集合の MinHash を比較
mh1 = minhash(set1)
mh2 = minhash(set2)

similarity = sum(a == b for a, b in zip(mh1, mh2)) / len(mh1)
# similarity ≈ Jaccard(set1, set2)

6.3 活用

重複ドキュメント検出

数十億の Web ページからほぼ同一のページを見つける。Google が使用。

剽窃検出

論文、コードの比較。

レコメンドシステム

「類似ユーザー」を見つける。

クラスタリング

LSH（Locality Sensitive Hashing）と組み合わせて類似項目をグループ化。

7. Skip List — 確率的バランス木

7.1 ソート済みデータ構造

バランス二分木（AVL、Red-Black）の代替として確率的アプローチ。

7.2 原理

多層リンクリスト。上位レベルは sparse、下位レベルは dense。

Level 3:  1 ───────────────→ 9
Level 2:  1 ────→ 4 ────→ 7 ─→ 9
Level 1:  1 → 3 → 4 → 5 → 7 → 8 → 9

検索: 上位から開始、大きすぎれば 1 レベル下る。

挿入時のレベル: コイン投げで決定。50% の確率で次のレベルへ。

7.3 パフォーマンス

長所: バランス木より実装が単純、lock-free 並行性が容易。

7.4 活用

• Redis Sorted Set: ZADD/ZRANGE の内部構造
• LevelDB/RocksDB の memtable
• Java ConcurrentSkipListMap

8. T-Digest — 分位点推定

8.1 問題

大規模ストリームで p99 latency のような分位点をどう計算するか？

伝統的: すべての値を保存してソート → メモリ急増。

T-Digest: 分布の「スケッチ」を小さいメモリで維持。

8.2 原理

値を bucket にグループ化。分布の端（p99、p99.9）により多くの bucket、中央（p50）にはより少なく。

根拠: 我々は通常**テール（tail latency）**に関心がある。中央値は大まかでもよい。

8.3 使用

from tdigest import TDigest

t = TDigest()
for value in stream:
    t.update(value)

p50 = t.percentile(50)
p95 = t.percentile(95)
p99 = t.percentile(99)
p999 = t.percentile(99.9)

8.4 活用

• モニタリング: Prometheus、Datadog、New Relic
• データベース: Druid、Apache Pinot
• ストリーム処理: Apache Beam、Flink

9. トレードオフ比較

9.1 全データ構造の比較

9.2 メモリ比較（1 億ユニークユーザー）

HyperLogLog は 30 万倍小さい。

10. 実戦 — Kafka の Heavy Hitter 検出

10.1 シナリオ

Kafka トピックに毎秒 100 万メッセージ。「どの user_id が最もアクティブか？」（スパム検出）

10.2 実装

from countminsketch import CountMinSketch
import heapq

# Count-Min Sketch + Top-K ヒープ
sketch = CountMinSketch(width=10000, depth=5)
top_k = []  # min-heap of (count, user_id)
TOP_K_SIZE = 100

def process_message(user_id):
    sketch.add(user_id)
    estimated_count = sketch.estimate(user_id)
    
    if len(top_k) < TOP_K_SIZE:
        heapq.heappush(top_k, (estimated_count, user_id))
    elif estimated_count > top_k[0][0]:
        heapq.heapreplace(top_k, (estimated_count, user_id))

# メモリ: ~200 KB で 1 億ユーザーを処理可能

10.3 結果

伝統的 HashMap = 数 GB → CMS = 200 KB（10,000 倍節約）。

わずかな不正確さを受け入れればメモリ効率が爆発的に向上。

クイズ

参考資料

• Bloom Filter 原論文 — Burton Bloom (1970)
• HyperLogLog 原論文 — Flajolet et al.
• Count-Min Sketch 原論文 — Cormode & Muthukrishnan
• Cuckoo Filter — Fan et al.
• Probabilistic Data Structures and Algorithms — Andrii Gakhov 著
• Redis HyperLogLog
• RocksDB Bloom Filter
• Apache DataSketches — 高品質な実装
• stream-lib — Java ライブラリ
• t-digest — Ted Dunning の実装
• pdsa.gakhov.com — 可視化 + シミュレーション