指定鍵值與發現鍵值
上一篇筆記回答的是一個事後查詢:事先指定鍵值 ,估計 出現了多少次。Count-Min sketch 可以做到這一點,卻不能告訴我們應查詢哪些鍵值。它的計數器混合了多個鍵值,也沒有記錄鍵值的身份;估計值為正,甚至不能證明該鍵值曾經出現。
這一篇處理另一個任務,稱為候選項發現。我們只讀取有限數據流一次,事前不知道哪些鍵值重要。讀取完後,希望得到一份短的鍵值清單,保證收錄所有出現次數超過數據總量某固定比例的鍵值。以下方法是確定性的:不需要雜湊,也沒有失敗概率。它通常稱為 Misra–Gries 頻繁項摘要。
下文會明確列出假設,並完整證明各項結論。
模型與假設
數據流是鍵值組成的有限序列 ,其中 。鍵值可來自任何全集;算法只需要能精確測試兩個鍵值是否相等。每次更新只插入一個出現項,沒有權重、刪除出現項或負更新。對長度為 的前綴,其中 ,記
固定整數 。摘要由一個表 和一個整數 組成: 最多儲存 對(鍵值、正整數計數器),而 記錄全表遞減事件的次數。令 為讀完 個項目後 的計數器;若 不在表內,約定 。所有運算都是精確整數運算。數據流有限,所以每個計數器都不超過 。
FREQUENT-CANDIDATES(stream, k) // k >= 1
T <- 空字典 // 鍵值 -> 正整數
D <- 0; N <- 0
依次讀取資料流中的每個鍵值 y:
N <- N + 1
若 y 在 T 中:
T[y] <- T[y] + 1
否則若 |T| < k:
T[y] <- 1 // 插入,計數為一
否則: // |T| = k 且 y 不在 T 中
對 T 中每個鍵值 z:
T[z] <- T[z] - 1
刪除所有滿足 T[z] = 0 的 z
D <- D + 1 // 不插入 y
返回 (T, D, N)
若數據流為空,迴圈內容不會執行;輸出是空表, 且 。以下所有陳述在這情況仍然成立。
由三個分支可直接得到兩個不變量。第一,:只有 時才插入。第二,表內每個計數器至少為 :遞增和插入產生正值,而遞減分支會刪除每個變成零的計數器。第二點對主要證明很重要:發生全表遞減時,恰有 個計數器,而每一個都至少為一。
計數恆等式與誤差界
直觀來看,一次全表遞減會從表內 個不同鍵值各扣去一次出現,同時拒絕新到鍵值的一次出現;新到鍵值與表內各鍵值都不同。因此,每次事件恰好丟棄屬於 個不同鍵值的 次出現。其餘未丟棄的出現仍記錄在計數器中。
定理 15.1.1
( 計數器摘要的不變量)
對每個前綴長度 ,其中 :
- ;
- 對每個鍵值 ,包括不在表內的鍵值,。
證明
(對三個分支歸納)
令 ,對 使用歸納法。當 時,表是空的,沒有鍵值出現,所以 ,所有 均為零,兩項結論成立。
假設兩項結論對長度 的前綴成立,並令 。在所有頻數中只有 改變,且增加一。
情況一: 在表中。 增加一而 不變。計數器之和增加 ,與 的增量相同。 和 同時增加一,所以 不變;其他 亦不變。
情況二: 不在表中且 。 由 變成 ,而 不變。計數器之和再次增加 , 仍然不變。
情況三: 不在表中且 。 表內 個計數器均至少為一,因此各減一後 恰好減少 。刪除現在等於零的計數器不改變總和,因為按約定,被刪鍵值的計數器也變成 。 不被插入,故 保持 。因此
至於誤差項, 增加一,因為 增加而 不變。表內 個鍵值的 也各增加一,因為它們的計數器下降而頻數不變;其他鍵值不受影響。
在每種情況下,每個 不是不變就是恰好增加一,而且只有 同時增加一的步驟才可能增加。由 ,可得 。
證明透視
兩個結論如何描述同一筆帳
對所有鍵值求和得 ,所以結論一是各鍵值損失的總和。情況三解釋了因子 :表內 個鍵值和新到鍵值兩兩不同,一次事件使 個不同鍵值各損失一次。由於鍵值互異,每次事件中單一鍵值最多損失一次,這正是 。如果新到鍵值與表內某鍵值相同,就會進入情況一;這也是偽代碼中分支次序重要的原因。
推論。 結論一中的量均非負,所以 。由於 為整數,
結論二亦說明每個計數器是下界,一般而言並非精確計數:。若鍵值不在表中,估計值 比真值少至多 。因此,對任何指定鍵值,表也能回答事後查詢,其確定性加法誤差至多為 。
常見錯誤
(把計數器當作頻率)
儲存的計數器只是下界:。在下面的追蹤中, 而 。把 報告為次數,或按 排列鍵值並當作精確排名,都忽略了每個鍵值可能損失的至多 次出現。精確次數需要第二遍掃描。
每個嚴格重頻鍵值都會保留
若 ,稱 為重頻鍵值,其中 。重頻鍵值最多只有 個:若有 個,它們的頻數之和便已超過 。
定理 15.1.2
(嚴格重頻鍵值的保留)
讀完整個數據流後,每個滿足 的鍵值都有 ,因此在最終表中。
證明
(計數器減去損失仍為正)
由誤差界和 的上界,
計數器是整數,故 ,即 被儲存。
不等式必須是嚴格的。最終表稱為候選集合,它包含所有重頻鍵值,但可能包含誤報。證明並不排除某個輕頻鍵值在數據流接近結尾時佔用空位。
常見錯誤
(把候選集合當作重頻鍵值報告)
保證是單向的:每個重頻鍵值都是候選項,但候選項未必是重頻鍵值。在最後一次全表遞減之後到達的鍵值,無論頻率多少都會以計數 插入,正如下面追蹤中的 。若沒有第二遍掃描,也沒有下文的判定,最終表只能報告為重頻鍵值的超集。
例題 15.1.3
(,追蹤 )
| 項目 | 分支 | 執行後的表 | |
|---|---|---|---|
| 插入 | 0 | ||
| 插入 | 0 | ||
| 全表遞減; 歸零並刪除;不插入 | 空 | 1 | |
| 插入 | 1 | ||
| 遞增 | 1 | ||
| 插入 | 1 | ||
| 遞增 | 1 |
因此 ,最終表為 。真實計數是 ,且 。
恆等式成立:。損失 和 均不超過 ,其和為 。上界 也成立。
門檻為 。只有 是重頻鍵值,因為 ;正如定理保證, 被保留。候選項 是誤報,因為 。另留意 低估了 。
下面的互動圖逐項重播 個計數器的摘要,在每個前綴後顯示表、全表遞減次數 與恆等式 ,最後列出重頻鍵值、誤報與第二遍精確計數的結果。
反例模式
恰好等於門檻不保證保留
取 和數據流 。頭兩項填滿表;第三項觸發全表遞減,使兩者都被刪除,而 亦不插入。最終表為空,。
每個鍵值均有 ,但沒有一個被保留。因此「每個滿足 的 都被保留」是錯的。證明失效的位置正是需要 之處:這裏 。在程式中比較門檻時,應使用精確整數測試 ,而非浮點商。
第二遍掃描精確找出重頻鍵值
假設可以再次讀取同一個數據流,例如數據已儲存或可重播。為最多 個候選項配置精確計數器,只統計這些鍵值:
EXACT-HEAVY(stream, T, N, k) // 資料流須與摘要所用者相同
對 T 中每個鍵值 z: E[z] <- 0
對資料流中每個鍵值 y:
若 y 在 E 中: E[y] <- E[y] + 1
返回 { z in E : (k+1) * E[z] > N }
定理 15.1.4
(兩遍掃描的精確恢復)
若第二遍讀取產生 的同一序列,輸出恰好等於 。
證明
(在超集上精確計數)
第二遍掃描後,每個候選項 的 均為精確值。候選項被輸出當且僅當它是重頻鍵值,因此輸出為 。由保留定理,,所以 。
計數不受順序影響,因此第二遍其實只需要相同的鍵值多重集合,毋須相同排列。不過,如果內容改變,候選清單便失去原有意義:新數據中的重頻鍵值可能從未成為候選項。數據流為空時,兩遍都不做任何事,輸出 是正確的。
單靠這個摘要,一遍掃描不能確定甚麼
第一遍確實能提供部分判定。若 ,由 ,可肯定 是重頻鍵值。若 ,則可肯定 不是重頻鍵值。在以上例子中,這些判定剛好能判斷兩個候選項;一般而言卻不一定,如以下比較所示。
例題 15.1.5
(追蹤中兩個候選項的判定)
在 、 的追蹤中,最終狀態為 ,。對 ,,由 得 : 肯定是重頻鍵值。對 ,,由 得 : 肯定不是重頻鍵值。不在表中的鍵值,例如 ,有 及 ,所以也被判定為輕頻。兩種判定都只讀取摘要;若某候選項有 ,判定便無法下結論,因為 。
反例模式
相同最終狀態,不同答案
令 。數據流 的最終狀態為表 、、;數據流 的最終狀態完全相同。
在第一個數據流中,,所以 是重頻鍵值;在第二個數據流中,,所以 不是重頻鍵值。任何只讀取 的規則都不能同時正確分類這兩個數據流中的 。
這說明這個摘要不支援單遍精確分類;它不是對所有算法的一般下界。
定理對任何輸入順序均成立,但最終表可以依賴順序。
例題 15.1.6
(同一多重集合的另一種順序)
取 ,把第一個追蹤的多重集合重排為 。 和 填滿表; 觸發全表遞減,刪去兩者,本身不插入,令 。其後四個 被插入並遞增,最終為 ,。恆等式為 ,損失為 、,此時 的計數器是精確的。這個表與 不同,但兩種結果都符合所有保證,而這次沒有誤報。
短數據流。 若 ,包括 ,便永不發生全表遞減。在第 步遞減,要求讀取 個項目後已有 個鍵值在表中;每個儲存鍵值都至少出現過一次,因此這不可能。故 ,由誤差界,每個計數器都精確。門檻滿足 ,所以重頻鍵值恰好是所有出現過的鍵值,表也恰好是該集合。當 時,沒有儲存項,也沒有重頻鍵值。
記憶體與更新成本
摘要最多儲存 對鍵值與計數器,另加 和 ,即 個計數器。但不能不加限定地把位元成本稱為 個字。每個計數器需要 位元。每個儲存的鍵值也需要自身的表示:若全集有限,需要 位元;若是長字串,可能需要多得多。字典亦有額外開銷。在固定字長硬件上,精確運算模型假設計數器不會溢出;已知 的上界時可以檢查這一點。
若以精確相等測試直接線性掃描整個表,每次輸入在最壞情況下花費 ,包括可能發生的全表遞減,因此 次輸入合共花費 。另一方面,恆等式給出整個數據流的計數器遞減次數 。這個總次數界不計查找成本,也不表示單次全表遞減可在常數時間完成。移除歸零計數器是表內部的整理,並非從輸入中刪除一次出現;移除次數不超過插入次數,而插入次數至多為 。若要更快地操作字典,便必須說明採用的數據結構和成本模型。
正文的論證不依賴合併這些表;本節也沒有聲稱支援帶權及負更新,或一遍掃描能作精確分類。
練習
練習 15.1.7
(以 對 執行算法。寫出最終表及 ,指出被刪除的鍵值,並驗證兩個不變量及保留定理。)
核心
解答(4)
- 1
處理首五項
讀完四項後,表為 。 到達時表已滿,遞減後得 。 和 都降至零而被刪除, 不插入,。
- 2
完成整個數據流
其後插入 ,再插入 。最終表為 ,,。
- 3
驗證兩個不變量
關鍵一步
恆等式成立:。真實次數為 。損失為 ,均不超過 ,總和為 。
- 4
驗證保留定理
門檻為 。重頻鍵值是 和 ,兩者都被保留。候選項 是誤報。
練習 15.1.8
(取 ,數據流為 ,求最終狀態。結果是否與保留定理矛盾?)
基礎
解答(2)
- 1
追蹤數據流
每個 都插入空表,隨後的 發現表已滿,觸發遞減並刪去 。最終表是空的,, 的上界恰好達到。
- 2
與定理比較
兩個頻率都等於 。兩個鍵值都不是嚴格重頻,所以空表並不與定理矛盾。
練習 15.1.9
(使用第一個追蹤的候選項 ()。若第二遍改為讀取 ,。輸出是甚麼?哪裏出錯?)
核心
解答(2)
- 1
在新數據上執行第二遍
計數為 ,都不超過 ,所以輸出為空。
- 2
與兩個重頻集合比較
新數據有 ,其重頻集合為 ;原數據流的重頻集合則為 。輸出對兩個數據流都不正確。
依據: 兩遍定理要求同一數據流,或至少相同的鍵值多重集合。
練習 15.1.10
(取 、,鍵值為 64 位元。界定 ,寫出重頻測試,並估計表、 及 所需位元(不計字典開銷)。再界定單次更新最壞的遞減工作量及總遞減工作量。)
核心
解答(3)
- 1
界定 並寫出測試
。鍵值是重頻當且僅當 。
- 2
計算位元數
計數器至多為 ,每個需 20 位元。表需 位元。儲存 需 20 位元, 需 14 位元,合共 位元。
- 3
界定遞減工作量
一次全表遞減改動 99 個計數器。整個數據流至多執行 次計數器遞減。
本節涵蓋僅插入數據流的確定性候選項發現、不變量及兩遍精確恢復;合併、帶權和有符號數據流,以及空間下界均不在本節範圍內。