Count-Min Sketch (CMS)

引言：「頻繁項」問題

想像你正在管理一個全球網絡。你想知道：「IP 1.2.3.4 在過去一小時內發送了多少次請求？」 在每秒數十億個數據包的流中，為每一個 IP 都存一個計數器會消耗數 TB 的記憶體。

Count-Min Sketch 是一種估算流中事件 頻率 的概率型結構。她就像布隆過濾器，但她存的不是位元位 (0/1)，而是 計數器。她可能會稍微高估頻率，但 絕對不會低估 頻率。

演算法要解決什麼問題？

• 輸入： 元素流。
• 輸出： 任意給定元素的估算出現頻率（計數）。
• 承諾： 在海量數據集下，使用固定、低廉的記憶體來追蹤頻率。

核心思想 (直覺版)

想像一個 多層計數器網格。

1. 網格： 創建 $D$ 行、$W$ 列的計數器。
2. 添加元素： 對於每一行，使用不同的雜湊函數找到一個列，並增加該計數器的值 (count[row][col]++)。
3. 查詢元素： 同樣使用這 $D$ 個雜湊函數。你會得到 $D$ 個不同的計數值（每行一個）。
4. 答案： 這 $D$ 個計數值中的 最小值 就是你的估算結果。

為什麼取最小值？因為由於雜湊衝突，某些計數器可能被多個元素共享（導致高估）。同一個元素在所有 $D$ 行都發生嚴重衝突的概率極低。

為什麼要用她？

• ✅ 尋找「重炮手」 (Heavy Hitters)： 無需儲存所有數據，即可在流中找到最頻繁出現的項（前 1%）。

• ✅ DDoS 防護： 快速識別發送異常高流量的 IP 地址。

• ❌ 高估風險： 她可能會說一個元素出現了 1005 次，而實際只有 1000 次。但她絕不會說 999 次。

• ❌ 去重計數： 如果你想知道「有多少個唯一元素」，請用 HyperLogLog。CM Sketch 是用來問「這個元素出現了多少次」。

典型業務場景

• ✅ 即時分析： 即時追蹤 Twitter 上的熱門話題。
• ✅ 內容交付 (CDN)： 確定哪些影片是當下的「爆款」，以便將其推送到邊緣快取。
• ✅ 資料庫最佳化： 查詢最佳化器使用 Sketch 來估算列中重複值的分佈，從而計算 Join 操作的成本。

性能與複雜度總結

• 時間： $O(D)$，$D$ 是雜湊函數的數量（通常很小，如 5-10）。
• 空間： $O(D \cdot W)$ —— 根據你要求的誤差容忍度確定的固定記憶體。

小結：一句話記住它

「Count-Min Sketch 是『頻率估算器』。透過在多個雜湊計數器中取最小值，她過濾了噪聲，並為你提供了一個可靠的事件頻率上限。」