Misra-Gries 頻繁項（heavy hitters）

假設十億張選票從你面前流過，你必須說出每個得票超過例如 1% 的候選人——但你只負擔得起追蹤少少幾個計數，遠不到每位候選人一個。你要怎麼在不記住每個人的情況下，找出真正受歡迎的項目？Misra-Gries 就是優雅的答案：一小組計數器，在一遍掃過、幾乎沒有記憶體的情況下，保證抓到每一個「頻繁項」（頻率超過所選門檻的任何項目），同時絕不會把真正稀少的項目誤報為頻繁。

演算法最多保留 k-1 個（項目, 計數）對，對每個到來的項目 x 遵循三條規則。若 x 已有計數器，就遞增它。否則，若使用中的計數器少於 k-1 個，就為 x 新開一個計數器、值為 1。否則（所有計數器都忙、且 x 是新的），把「每一個」計數器都遞減 1，並刪掉任何歸零的。最後這條規則是聰明的核心：把它想成一次抵消 k 個不同的項目，像把對立的選票成對劃掉。隨之而來的保證是：每個計數器的值對真實頻率的低估，最多差 m/k，其中 m 是串流長度。所以任何出現超過 m/k 次的項目都會以正計數存活並被回報。取 k 約為 1/epsilon，每個頻率高於 epsilon*m 的項目都會被找到，只用 O(1/epsilon) 個計數器。它是單邊估計：可能略為低估，絕不會高估。

Misra-Gries 之所以重要，是因為頻繁項到處都值得找出：灌爆網路的最忙 IP 位址、爆紅的搜尋詞、最暢銷的產品、最常見的錯誤碼——全都能在一遍掃過、用幾 KB 狀態下偵測到。它把經典的 Boyer-Moore 多數技巧（用「一個」計數器找出現超過一半的項目）推廣到任何門檻。誠實的提醒：這些計數是下界（真實頻率介於儲存的計數與計數 + m/k 之間），它找出「候選」頻繁項，但可能需要第二遍來驗證精確頻率，而且它告訴你哪些項目「可能」頻繁，保證絕不漏掉真正的頻繁項，但可能列出幾個臨界的。