Morris 近似計數器（approximate counter）
/ MOR-iss /
假設你必須數一個龐大的事件數——多達十億——但你只有一個 8 位元的暫存器，正常上限是 255。精確計數毫無希望：十億需要 30 個位元。Morris 在 1978 年的把戲是「近似地」計數，而且儲存的不是計數本身，而是（大致上）它的對數，這樣一個小暫存器就能表示巨大的數字。代價是答案是個隨機估計，接近但不精確。這是串流的種子想法：用一點點準確度，換取記憶體的巨大節省。
它是這樣運作的。保留一個小整數 X，從 0 開始。每個事件「不」總是遞增。而是只以機率 1/2^X 遞增 X（擲 X 枚公正硬幣；全部正面才把 X 加一）。所以 X = 0 時每次都遞增，X = 1 時約一半的時間遞增，X = 5 時只約每 32 次一次。暫存器爬得越來越慢，追蹤著真實計數的對數。要讀出「發生了多少事件」的估計，就算 2^X - 1。可以證明這個估計是無偏的——它的期望值等於真實計數 n——所以平均而言它是對的，雖然任何單次執行都會散落在 n 附近。整個計數器只需要約 log log n 個位元，因為 X 本身只會長到約 log n。
Morris 計數器之所以重要，是因為它是第一個也最簡單的草圖，並且是「儲存對數、接受隨機性」的範本：相同的邏輯支撐著機率計數，以及用於相異元素的 HyperLogLog。當你有數百萬個計數器（每條流、每個鍵、每個格子一個），無法為每個都騰出全寬整數時，它最為閃亮。誠實的提醒：單一個 Morris 計數器是有雜訊的（它的標準差是 n 的一個常數比例，所以一次估計可能偏差數十個百分點）；你藉由平均多個獨立計數器，或使用可調的、更接近 1 的底數 a 來馴服它，這以更多記憶體換取更高準確度。它在期望上無偏，但在任何單次執行上不準。
用從 0 開始的 X 計數事件。第一個事件：以機率 1/2^0 = 1 遞增，所以 X=1。現在遞增以機率 1/2 發生。許多事件後 X 可能達到例如 10；估計為 2^10 - 1 = 1023。暫存器自始至終只裝著小數字 10（4 位元），卻代表約一千個事件——平均無偏，單次有雜訊。
以機率 1/2^X 遞增；回報 2^X - 1。用約 log log n 位元數到 n。
單一個 Morris 計數器無偏但「有雜訊」——一次讀數可能偏差數十個百分點。準確度來自平均多個獨立計數器，或用更接近 1 的底數 a（更多記憶體、更小變異）。它省的是空間（log log n 位元），不是時間，而且給的是估計，絕非精確計數。