計數最小值草圖（count-min sketch）

你想為一個龐大串流中「每個」相異項目都保留近似的計數——每個 URL、單字或 IP 出現了幾次？——但相異項目實在太多，無法給每個都配一個計數器。計數最小值草圖是一張小小的二維計數器表，加上幾個雜湊函數，讓你能即時為某項目的計數加一，之後再問「項目 x 大約出現了幾次？」並得到接近的答案，而所用空間不隨相異項目數成長。

機制如下。取一張有 d 列、w 行計數器的表，全部從 0 開始，並選 d 個獨立的雜湊函數 h1..hd，每列一個，各把任何項目映到 w 行之一。要記錄項目 x 的一次到來，就在每一列、其雜湊所選的那一行加 1：遞增 row1[h1(x)]、row2[h2(x)]、...、rowd[hd(x)]。要估計 x 的計數，就看那同樣的 d 個格子，回報其中的「最小值」。為何取最小？x 碰到的每個格子，都含有 x 的真實計數「加上」恰好碰撞進該格的其他項目——碰撞只會增加，絕不會減少。所以每個格子都高估，而最小的那個污染最少，因此最接近真相。取 w = e/epsilon、d = ln(1/delta)，估計超過真實計數的部分，以至少 1 - delta 的機率不超過 epsilon*m（m = 串流長度）。

計數最小值草圖之所以重要，是因為它是串流頻率估計的首選：它驅動頻繁項偵測、找出頻繁的網路流、支援近似的資料庫查詢規模、並服務於判斷「什麼是熱門」的快取——全都在固定的幾 KB 內，無論存在多少鍵，每次更新與查詢都只做 O(d) 的工作。誠實的提醒：它的誤差是單邊的——它可能「高估」（因為碰撞會增加）但絕不低估，所以當高估可接受時它最理想；它對有真正頻繁項的偏斜資料最有效；而且保證是機率性的、與串流總質量 m 成正比，所以稀少項目埋沒在雜訊裡。