Count-Min Sketch 與頻率估計

問題

在串流場景中（即時處理數百萬筆資料），我們常需要知道每個元素的出現頻率。用 HashMap 儲存所有頻率，對海量串流來說是災難性的。

Count-Min Sketch 解法

Count-Min Sketch (CMS) 用一個二維陣列 + 多個 hash 函數來估計頻率。

import math
import mmh3

class CountMinSketch:
    def __init__(self, epsilon=0.01, delta=0.01):
        """
        epsilon: 誤差容許度
        delta: 失敗機率
        """
        self.width = int(math.ceil(math.e / epsilon))
        self.depth = int(math.ceil(math.log(1 / delta)))
        self.table = [[0] * self.width for _ in range(self.depth)]
    
    def add(self, item, count=1):
        """增加元素的計數"""
        for d in range(self.depth):
            idx = mmh3.hash(str(item), d) % self.width
            self.table[d][idx] += count
    
    def estimate(self, item):
        """估計元素的出現頻率"""
        estimates = []
        for d in range(self.depth):
            idx = mmh3.hash(str(item), d) % self.width
            estimates.append(self.table[d][idx])
        return min(estimates)  # 取最小值（CMS 永遠不低估）
    
    def merge(self, other):
        """合併兩個 CMS（用於分散式系統）"""
        for d in range(self.depth):
            for w in range(self.width):
                self.table[d][w] += other.table[d][w]

# 測試
cms = CountMinSketch(epsilon=0.01, delta=0.01)
print(f"表格大小: {cms.width}x{cms.depth} = {cms.width * cms.depth} 個計數器")
print(f"實際記憶體: {cms.width * cms.depth * 4 / 1024:.2f} KB (int32)")

# 模擬串流資料
import random
random.seed(42)

true_counts = {}
for _ in range(100000):
    item = f"item_{random.randint(1, 1000)}"
    cms.add(item)
    true_counts[item] = true_counts.get(item, 0) + 1

# 評估誤差
print(f"\n=== 頻率估計評估 ===")
errors = []
for item, true_count in list(true_counts.items())[:20]:
    est = cms.estimate(item)
    error = est - true_count
    errors.append(error)
    print(f"{item}: 實際={true_count}, 估計={est}, 誤差={error}")

print(f"\n平均誤差: {sum(errors)/len(errors):.2f}")
print(f"最大誤差: {max(errors)}")
print(f"理論保證: 誤差 ≤ epsilon * N = {0.01 * 100000} = 1000")

應用場景

1. 即時熱門商品榜：在電商平台中即時統計商品點擊次數
2. DDoS 檢測：監控每秒來自同一 IP 的請求數
3. 熱門搜尋詞：即時統計搜尋引擎的熱門查詢
4. IoT 感測器資料：在邊緣設備上統計感測器讀數分布