← 回首頁
Heavy Hitters（串流 top-k 高頻項：Misra-Gries / Space-Saving）
資料像水流般不斷湧來——每秒上百萬次點擊、上億筆日誌——你存不下每一筆,卻很想知道「哪幾個東西最常出現」:
最熱門的商品、被搜最多次的關鍵字、打最多流量的那幾個 IP。這類「找串流裡的少數高頻項」問題叫
Heavy Hitters 。笨方法是替每個相異項都開一個計數器,但相異項可能有幾千萬個,記憶體爆掉。聰明的做法
是只用固定的 k 個計數器 (本頁 k=3),單次掃描就逼近答案。代價是計數不再精確——這頁把兩種經典解法
並排,讓你親眼看見它們各自「往哪個方向不準」。
Misra-Gries（MG） 像「僧多粥少就一起扣」:新項若已在表就 +1,有空槽就進駐;但表滿又來個生面孔時,
所有計數器同時 −1 、歸零的踢出去,新項這回不進表。這種「連坐扣減」會讓留下來的計數偏低
(估計 ≤ 真頻,低估或準)。Space-Saving（SS） 則反過來「鳩佔鵲巢」:表滿又來生面孔時,找計數
最小 的那個槽,把它換成新項、繼承它的計數再 +1 ——於是新來的項白白揹上前一位的計數,讓估計
偏高 (估計 ≥ 真頻,高估或準)。下面用同一份串流餵給兩者,並把「兩法的估計」和「暴力精確算出的真值」
三欄並排對照。
為什麼 AI 時代重要
找 top-k 高頻項是串流系統的日常剛需:觀測系統(observability)要即時抓出「打最多流量的熱點 API / IP」做限流
與 DDoS 防護、推薦與廣告系統要追「當下最熱門的商品 / 查詢」、CDN 要決定「哪些內容最該進快取」。放到
LLM 語料工程更關鍵——清洗數十億級 token 語料時,常要依高頻 token / n-gram 過濾樣板重複或偵測資料
污染,逐項精確計數在這種規模上不可行,只能用 Heavy Hitters 以固定 O(k) 空間單次掃描逼近。看懂 MG「低估」
與 SS「高估」兩個方向,才知道拿到近似 top-k 後該往哪邊修正、能信到什麼程度。
它是串流概要（Count-Min / HyperLogLog）與雜湊的延伸
Heavy Hitters 是串流 sketch 家族的第三根柱子:
串流概要 Count-Min / HyperLogLog 裡,Count-Min 估「某一項出現
幾次 」
(頻次)、HyperLogLog 估「總共有
幾個 不同的項」(基數),而本頁回答的是「
哪些 項最熱門」(top-k)
——三者都以固定小空間換取近似,方向與代價各不相同。實作上 Space-Saving 常以
雜湊 Hash Table / Bloom Filter 的雜湊表加 min-heap 做到近
O(1) 更新(本頁為教學用小陣列線性掃描示範核心邏輯),同屬「用固定格位換空間、以偏差換規模」的血緣。
雙表並行（stream 逐項更新 → estimate vs 真實）
固定串流 [A,B,A,B,C,A,D,A,B,E,A,A,B](共 13 項,A 為主導高頻項、B 次之,C/D/E 為低頻雜訊,刻意穿插製造
MG 的 decrement-all 溢位與 SS 的 replace-min 替換)。每個到達項先更新 MG、再更新 SS ,各產生一幀;
最後對相異項 [A,B,C,D,E] 逐項揭露「暴力精確真值 vs MG 估計 vs SS 估計」。兩法都只保證「超過各自門檻的項
必留」:MG 門檻 n/(k+1)=13/4=3.25、SS 門檻 n/k=13/3≈4.33——真頻 6 的 A 與真頻 4 的 B 是真正的 top-2,
兩法皆保留;C/D 真頻僅 1,被兩法丟棄。
固定串流(項目標籤):[A,B,A,B,C,A,D,A,B,E,A,A,B](13 項);計數器數 k=3;查詢項 [A,B,C,D,E]。
無隨機,對照 Java aiera/HeavyHitters.java(決定性)。
重播
已處理項數（processed）：0 / 13
階段：stream
4 列 × 3 欄計數器表:列 0/1 = Misra-Gries （項目列 / 計數列）、列 2/3 = Space-Saving
（項目列 / 計數列);空槽項目顯示「·」、計數顯示 0（0 為合法計數,非「未填」）。藍色外框（active）＝
當前到達項在該法本步觸及的格;粉紅（pivot）＝MG decrement-all 歸零被移除的槽 / SS replace-min 被替換
的槽。MG 低估、SS 高估 :MG 的連坐 −1 使留存計數 ≤ 真頻;SS 的繼承 +1 使新項揹上舊計數 ≥ 真頻。
誠實揭露 :k=3 為教學用極小值 ,刻意讓溢位/替換在小格子上看得見,真實系統 k 會大得多;
兩法皆非精確 top-k ——只保證超過門檻(MG:n/(k+1)、SS:n/k)的項必留,門檻以下(如 C/D/E)可能
被丟棄或以偏差計數呈現(如 E 被 SS 高估到 3,真頻其實只有 1)。
Space-Saving 計數器（高估或準；err = 可能高估量）