如水柱般的資料：只看一次，且存不下來
上一篇指南讓你站在線上演算法的位置上：在看不到未來的情況下當下就要做決定。串流模型保留了這種「只走一遍」的精神，但又加上第二個殘酷的限制：不只未來是一次來一個項目，你連過去也留不住。想像穿過路由器的網路封包、打進伺服器的搜尋查詢，或來自十億台裝置的感測讀數——這個序列長到把全部存下來根本不可能。你只能依序把每個項目讀一次，讀完之後它就永遠消失了。
這裡的主角資源不是時間，而是空間。我們衡量的是演算法在任一瞬間握有多少位元的工作記憶體，而夢想是「次線性」空間——遠小於串流長度，理想上是像 O(log n) 位元那樣的量，或對相異項目數而言是多對數等級。如果串流有一兆筆，一個誠實的串流演算法或許只用幾 KB。整個遊戲就是這件事：當大河在身旁轟然流過時，手裡只攥著一份極小、卻精心挑選的摘要，並且只憑這份摘要就把問題回答出來。
莫里斯計數器：用一個位元組數到十億
從最溫和的問題開始：當項目一個個流過時，只要把它們「數」起來就好。一個樸素的計數器要數到 n，大約需要 log n 位元——要數到十億，差不多要 30 位元。這已經很小了，但它正是初識串流思維的絕佳起點，因為只要我們願意接受一個近似的計數，就能做得戲劇性地好。這個訣竅就是莫里斯計數器，而它美極了。
與其儲存計數 n，不如儲存一個「指數」X，讓它大致追蹤 log n。我們保留的是 X，而不是 n。每來一個新項目時，我們並不總是加一——我們擲一枚有偏的硬幣，只以 1 / 2^X 的機率把 X 加一。所以當 X 還小時，加一既容易又頻繁；隨著 X 變大，加一就以指數速度變得愈來愈罕見。要讀出真實計數的估計值，我們回報 2^X - 1。因為 X 頂多爬到約 log n，儲存 X 只需約 log log n 位元——要數到十億，大約 5 位元，一個位元組還綽綽有餘。
init X = 0
on each item:
with probability 1 / 2^X: X = X + 1
estimate of count = 2^X - 1為什麼回報 2^X - 1 才對？看清這點最乾淨的方法是透過期望值：如果你去追蹤隨機變數 2^X，一段簡短的計算會顯示，在 n 個項目之後它的期望值恰好是 n + 1，所以 2^X - 1 是 n 的一個「不偏」估計量。這是誠實的部分——平均而言它精準命中。但有個但書：變異數。單一一個莫里斯計數器是有雜訊的，任何一次運行都可能偏掉。標準的補救法是跑好幾個彼此獨立的計數器再取平均，藉此把散布縮小；這是一個蒙地卡羅式的答案，又快又小，但只是「很可能接近」，並不保證精確。
重量級元素：只用少數幾個格子，找出誰出現得多
一個更實用的問題：哪些項目「經常」出現？想想熱門搜尋詞，或是灌爆伺服器的那些 IP 位址。我們想找出每個出現比例超過（比方說）1/k 的項目——也就是重量級元素。為每個相異項目都存一個計數可能需要龐大的記憶體。米斯拉–格里斯演算法只用 k - 1 個計數器就能找出那些頻繁的項目，無論流過多少個相異項目都一樣。
- 保留至多 k - 1 個帶標籤的計數器，一開始全都是空的。對每個到來的項目：若它已經有一個計數器，就把那個計數器加一。
- 否則，若還有空閒的計數器格子，就把它認領給這個項目，並將其計數設為一。
- 再否則（沒有空閒格子），就把 k - 1 個計數器全部各減一；任何歸零的計數器都會被釋放，留給未來的項目。
- 到最後，存活下來的標籤就是你的重量級元素候選名單；它們所存的計數會「低估」真實頻率，但低估的幅度絕不超過 n/k。
為什麼這行得通？每一次全域減一的步驟，一口氣丟掉 k 個項目（一個真正到來的，加上記在既有計數上的 k - 1 個），而在長度為 n 的串流裡你頂多能這樣做 floor(n/k) 次。所以任何單一項目從它的真實計數中頂多損失 n/k——這意味著一個貨真價實、出現超過 n/k 次的重量級元素無法被抹除，必定帶著一個正的計數存活下來。反過來說，這就是它誠實的限制：有些存活者可能是冒牌貨、其實從未真正越過門檻，所以米斯拉–格里斯「保證抓到每一個」重量級元素，但也可能多報幾個假的。若你負擔得起，再走第二遍就能把那些濾掉。
草圖：把眾多項目雜湊進一張小網格
串流最深刻的點子是草圖：一個很小、大小固定的資料結構，它「概括」整條串流，使得近似的答案能直接從中讀出。明星範例是count-min 草圖，它用一張計數器網格搭配一族雜湊函數，去估計你所詢問的任何項目的頻率。它倚靠的正是你早在隨機演算法那一階段就見過的那匹主力：通用雜湊——隨機挑選的雜湊把項目打散開來，使碰撞變得罕見，而且至關重要地，是「可分析的」。
想像一張有 d 列、w 行計數器的網格，全部從零開始，每一列配一個獨立的雜湊函數，把項目映射到某一行。要處理一個項目，就對每一列各雜湊一次，並在它落入的那 d 個格子各加一。要查詢一個項目的計數，就用同樣方式雜湊它、讀出那 d 個格子——然後回報其中的「最小值」。每個格子裝的是「該項目的真實計數」加上「碰撞進同一格的其他項目」，所以每個格子都會高估；在 d 個獨立的高估中取最小的那個，就是你最好、最緊的猜測。總記憶體就只是 d 乘以 w 個計數器，完全與出現了多少個相異項目無關。
以下是誠實的帳。每個格子只會加進碰撞帶來的「額外」質量，所以它從不低估——因此那個最小值是真值的一個上界，而誤差是單邊的。通用雜湊讓任一列裡的期望碰撞雜訊很小（大約是「總質量 / w」的量級），而一個馬可夫不等式式的論證把它轉成每一列的失敗機率；接著 d 個獨立的列把「所有列都很糟」的機率以指數速度壓下去，這和一個切爾諾夫式的論證會做的事很像。把 w 取在約 e/epsilon、d 取在約 ln(1/delta)，你就得到：以至少 1 - delta 的機率，每個估計值對真值的高估都不超過 epsilon 乘以串流的總計數。小網格、誤差可調、且不需要為每個項目存東西。
計數相異元素：到底飛過了多少種不同的東西？
最後一個經典，而且很漂亮：這條串流裡含有多少個「相異」項目？不是總長度——而是不同值的個數。精確的答案需要與相異項目個數成正比的記憶體，而那可能大得驚人，所以我們改用估計。相異元素計數背後的核心點子是：把每個項目雜湊成 [0, 1] 區間裡一個看起來隨機的實數，然後就只記住「曾見過的最小」雜湊值。
其中的直覺愉快地簡單。如果你把 m 個相異值均勻隨機地撒進 [0, 1]，它們傾向於分散開來，而其中最小的那個會落在約 1/(m + 1) 附近。重複的項目會雜湊到「同一個」數，所以它們永遠不會把最小值再往下推——只有相異值才算數，而那恰好就是我們想要的量。所以若你見過的最小雜湊是某個值 v，那麼 1/v - 1 就是相異項目個數的一個合理估計。記憶體裡只放一個實數，重複項就被自動忽略了。
串流真正換來什麼，又付出什麼代價
退一步看，共通的食譜就清楚了。這裡每個方法都拿一個「精確、確定」的答案去換一個「近似、很可能對」的答案，而正是這一項讓步，才解開了次線性空間之鎖——去對付那些「精確版可被證明塞不下」的問題。挑大樑的工具，是你早在前面階段就已擁有的隨機機制：用雜湊把項目可預測地打散、用期望值的線性性質釘住一個估計量平均而言代表什麼，以及用集中不等式論證估計值鮮少偏離太遠。與其說串流是一袋新把戲，不如說是把那些把戲對準了一個單一而嚴苛的記憶體預算。
對這些保證要講精確，因為最容易的誤讀很危險。count-min 那個「至多 epsilon 乘以總量」的高估，是一個「以高機率成立」的「最壞情況」界——它並不是對任何單一一次孤立查詢的承諾，而那個罕見的失敗事件是真的可能發生的。莫里斯與相異計數給的是「不偏」估計量，意思是對隨機性「平均而言」正確，這跟「在你這一次特定的運行上正確」並不是同一回事；這正是為什麼「取多個副本的平均」不是可有可無的修飾，而是讓變異數小到足以倚靠的關鍵。而且，就跟任何隨機方法一樣，這些方法只在它們的假設之下才誠實——主要是假設雜湊函數的行為夠隨機，而通用雜湊正是為兌現這一點而精心設計的。
最後，要把界線握清楚。串流草圖在「可加總的、彙總式的」問題上大放異彩——計數、頻率、相異總數、重量級元素——這些問題裡每個項目的小誤差會在摘要中被沖淡。但當你需要「精確的集合成員判定」「精確的中位數」，或想「把資料本身重建出來」時，它們就是錯的工具，因為那些資訊是被刻意丟掉的。知道一份極小的摘要「能」與「不能」回答哪些問題，才是真正的本事；而這份本事會一路帶進接下來的前沿：同一種「超越最壞情況、近似但夠好」的思維，會在參數化演算法與區域搜尋中再度現身，在那裡，結構與「夠好的答案」又一次勝過了蠻力式的精確。