← 回首頁
串流概要（Count-Min Sketch + HyperLogLog）
資料像水流般不斷湧來時——每秒上百萬次點擊、上億個訪客——你根本存不下每一筆,卻又想知道「某個東西出現了
幾次」和「總共有幾個不一樣的東西」。這兩種串流概要（sketch）就是用一點點固定空間換一個夠準的估計:
Count-Min Sketch 像幾排共用的計數格子,同一格會被不同東西擠著用,所以估出來只會多、不會少;
HyperLogLog 則像看賭桌上「有人連丟出一長串正面」的罕見巧合,反推現場一定人很多。下面兩節都會把
「估計值」和「獨立算出的真正答案」並排,讓你親眼看見它們差多少。
兩者都是在固定小空間內近似串流統計量的機率性資料結構，用精確度換取規模：Count-Min Sketch 以 d×w 計數矩陣
逐事件更新，點查詢時對每一列取命中格計數的最小值作為頻次估計——因不同鍵可能雜湊到同一格造成碰撞，估計值
只會「高估或持平」，絕不「低估」真實頻次；HyperLogLog 則對每個事件的雜湊值取前導零位置（ρ），存進固定
數量的暫存器並只升不降地更新，再由全部暫存器獨立重算調和平均公式估計相異值個數（基數），教學用小參數下
偏差明顯，但方向不固定（可能高估也可能低估）。本頁兩個 section 皆同時揭露「估計值」與「獨立重算的真實值」，
誠實對照兩者差距。
為什麼 AI 時代重要
觀測系統（observability）處理巨量請求流量時，無法為每個 API／服務組合維護精確計數器，Count-Min Sketch
用固定小空間近似統計流量頻次，支撐即時告警與限流判斷；LLM 訓練資料清洗常需要依 token／n-gram 出現頻次
過濾低頻雜訊或高頻重複樣本，逐一精確計數在十億級語料上不可行，只能容忍「只會高估」的近似頻次；而估計
十億級使用者／IP／去重樣本數（基數）時，精確去重需要儲存全部相異值，HyperLogLog 只用固定數量的暫存器，
以有偏差但誠實可控的方式換取常數空間。
它是 Bloom Filter 的延伸
Bloom Filter 只用位元陣列回答「是否存在」；Count-Min Sketch 把位元陣列換成計數矩陣，回答「大約出現幾次」
（只會高估，原理同 Bloom Filter 的碰撞——只是碰撞混入的是其他鍵的計數貢獻而非置位訊號）；HyperLogLog
則把雜湊值的前導零位置存進固定數量的暫存器，回答「大約有幾個相異值」。三者同屬「用雜湊格位換取空間、
犧牲部分精確度」的機率性資料結構家族 →
雜湊 Hash Table / Bloom Filter
1. Count-Min Sketch（計數矩陣 + min 查詢）
buildMatrix：對每個到達事件 x，依固定雜湊族 h_i(x) = ((A[i]·x + B[i]) mod 17) mod 8（i=0..2，共 D=3 個
雜湊函式，每列 W=8 格，A/B 皆為固定參數表）在每一列各選一格計數 +1；query：對每個查詢鍵，獨立由矩陣
終態取每一列命中格的最小值作為頻次估計，並與獨立 Map 全掃得到的真實頻次同幀對照。因為不同鍵可能雜湊到
同一格（碰撞），格內計數會混入其他鍵的貢獻，估計值恆 >= 真實頻次，只會高估或持平，絕不低估。
固定事件串流（token id）：[5,12,5,7,12,5,3,12,5,9,12,5,7,12,3]（15 事件，熱鍵 5/12 重複出現）；
查詢鍵：[5,12,7,3,9,11]（11 為未出現鍵，真實頻次為 0，CMS 仍可能因碰撞估出 >0）。矩陣 D=3×W=8，
MOD=17，A=[1,3,5]，B=[5,0,1]（固定雜湊族，對照 Java CountMinSketch.java）。
已更新格數（updates）：0
階段：updates
列＝雜湊函式 row0..row2（D=3）、欄＝桶 0..7（W=8）；格值＝該列該桶目前計數（從 0 起，非空格語意）。
藍色外框（active）＝當前事件／查詢命中的格；查詢階段粉紅（pivot）＝取得最小值的格（第一個達到最小值
的列）。只會高估，絕不低估：碰撞（不同鍵雜湊到同一格）使該格計數混入其他鍵的貢獻，估計值
（取各列 min）恆 >= 真實頻次——碰撞範例 key=12：est=6 > true=5。
2. HyperLogLog（前導零暫存器 + 基數估計）
buildRegisters：對每個到達事件 x，以 16-bit 決定性雜湊 H(x) = ((2691·x + 479) mod 65537) & 0xFFFF
取前 REG_BITS=3 位選暫存器索引（m=8 個暫存器）、其餘位計算前導零 rank（ρ），並以 max(目前值, ρ) 更新
暫存器（只升不降）。estimate：由暫存器終態獨立重算調和平均公式 E = alpha_m·m²/Σ(2^-register[j])，
當 raw 值偏小且存在空暫存器時，改用 linear counting 公式修正。真實基數則由獨立 Set 全程計數相異值。
固定事件串流（同 Count-Min Sketch 一節）：[5,12,5,7,12,5,3,12,5,9,12,5,7,12,3]（相異值 5/7/9/12/3 共
5 個）。REG_BITS=3（m=8 暫存器），16-bit 決定性雜湊 H(x)=((2691·x+479) mod 65537)&0xFFFF（固定
參數表，對照 Java HyperLogLog.java）。
已處理事件數（updates）：0
唯一 1 列 × 8 欄的暫存器列（m=8=2^REG_BITS）；格值＝該暫存器目前的最大 ρ（前導零 rank，從 0 起，
非空格語意）。藍色外框（active）＝當前事件命中的暫存器。暫存器只升不降（單調）。
教學用小參數誤差大：m=8 時估計值可能明顯偏離真實基數（可能高估也可能低估，方向不固定，
這是小參數的正常教學可視現象而非估計失準）；raw 調和平均值過小且存在空暫存器時會觸發 linear
counting 修正；生產環境建議 m 從 2^14 起以壓低誤差。
估計 vs 真實基數 即時對照
| 項目 | 數值 |
|---|
| 估計 estimate | 0.000 |
| 真實 trueCardinality | 0 |
| 差值（estimate − true） | 0.000 |
Count-Min Sketch 與 HyperLogLog 同屬串流 sketch 家族，與相似度雜湊（MinHash/SimHash）一樣把資料壓縮成
固定大小的摘要，只是換取的是「近似頻次／基數」而非「近似相似度」→
相似度雜湊 MinHash/LSH/SimHash