頻率問題
串流包含對固定全集 中鍵值 的更新 ,權重 是非負整數。令 為鍵值 的權重總和, 為總權重;處理的更新數有限。為每個不同鍵值保留精確計數器可能代價高昂;Count–Min 草圖以精確性換取緊湊表格。它可回答指定鍵值的頻率,但本身不會列出所有出現過的鍵值。
定義 1.2.1
(Count–Min 草圖及其估計)
取正整數 (寬度)和 (深度),並對各行 獨立選取隨機雜湊函數 。每一行只假設以下碰撞界:
初始時每個計數器 均為零。每次更新 ,就在每行的 加上 。鍵值頻率的估計為
串流及任何查詢鍵值均與所選雜湊獨立地預先固定。我們不要求同一行中不同碰撞彼此獨立。也必須儲存雜湊函數的描述及種子,其大小取決於所選函數族與全集。碰撞條件是要為該函數族核實的假設,並非任意雜湊函數都具備的性質。
命題 1.2.2
(估計永不低估)
若每個更新權重均非負,則對每個鍵值 及雜湊函數的每個實現,都有 。
證明
(每個受查詢計數器都包含完整計數)
固定一行 。每次更新 都把 加到 ,所以這個計數器收到 的全部,另加滿足 的鍵值 的權重。這些額外權重非負,故對每個 都有 ,對 取最小值亦至少為 。
論證只用到碰撞權重的符號,別無其他,所以更新的非負假設不能刪去。
反例模式
負更新可令估計低於真值
斷言:對任何整數更新串流,Count–Min 估計都是上界。取 、,並讓雜湊在兩行都把鍵值 和 送到同一個桶。處理 及 。 的兩個受查詢計數器都是 ,所以 ,但 。證明正好在假設碰撞權重非負的地方失效。修正後的陳述就是上面的命題:更新非負時估計是單側的;有負更新時,既不聲稱這個不等式,也不聲稱下面的誤差界。
固定鍵值的誤差界
定理 1.2.3
(Count–Min 誤差界)
設更新非負,在抽取雜湊前固定串流及鍵值 ,並設 。若 ,則
特別地,對 ,取 、 可使成功概率至少為 。
證明
(每行用 Markov,各行之間用獨立性)
由上一命題,下方不等式恆成立。當 時,所有計數器和頻率均為零,結論確定地成立,不必除以 ;以下設 。第 行超出真實計數的部分是
由期望的線性性與碰撞假設,
此求和不需要各項獨立。Markov 不等式給出
因為完整的各行雜湊函數相互獨立,而串流已固定,各行誤差 相互獨立。最小估計超過 ,只可能在每一行的誤差都超過 時發生,其概率至多為 。最後, 給出 。
證明透視
各個假設在誤差界中的位置
證明分兩步。第一步在單一行內:超出量的期望只需要兩兩碰撞概率與線性性,所以同一行內的雜湊值可以任意相關。接著 Markov 不等式需要 ,這又是更新非負的假設。這個單行界很弱,只有 。第二步是放大:取最小值把「有一行良好」變成成功,所以失敗需要全部 行同時失敗;整行雜湊的獨立性只在這裏用到。在抽取雜湊前固定串流與鍵值,才令各 只是獨立雜湊的函數;看過表格後才選的鍵值會破壞這一步。
這是對固定串流及鍵值、以雜湊選擇為隨機性的概率陳述;它不保證看到表格後自適應選出的每個鍵值。若預先指定有限集合 ,其中有 個鍵值,聯集界給出同時成功的概率至少為 ;取 可使總失敗概率至多為 。聯集界不要求不同鍵值的失敗事件相互獨立。
常見錯誤
(誤差相對於總權重是加性的,而非相對於該鍵值)
界寫作 ,其中 是整個串流的權重。它並非說 。對於 遠小於 的罕見鍵值,估計可以是真實計數的許多倍,而仍然符合定理。
小表格與合併
例題 1.2.4
(從固定表格讀出估計)
設 、、,並取 、。第 1 行讓 、 雜湊至桶 0, 至桶 1;第 2 行讓 、 雜湊至桶 1, 至桶 2。非零計數器為
查得的兩行計數是 ,故 ; 查得 ,估計為 ; 查得 ,估計為 。每個估計都不小於真實計數,正如命題所保證;取最小值則去掉了較乾淨那一行以外的碰撞。此例展示特定函數的碰撞;單個選定表格不是概率界的實驗證明。
例題 1.2.5
(為固定查詢集合決定草圖大小)
設查詢是預先指定的 個鍵值,,總失敗概率 。寬度與 無關:。深度須滿足 ,所以 。此時 ,因此以至少 的概率,全部 個估計都落在 。表格有 個計數器。若只有一個鍵值, 已足夠;多出的五行是聯集界的代價。
只有當兩個不重疊更新批次的草圖具有相同維度及各行雜湊函數時,才能把相應計數器相加來合併。所得結果等同以同一組雜湊順序處理兩批更新。若批次重疊,共有更新會重複計數。若合併後的串流與共用雜湊選擇獨立,上述界可用於該串流。
例題 1.2.6
(以共用雜湊合併兩批更新)
沿用第一個例子的雜湊。第 1 批是 ,第 2 批是 。草圖 1 有 、、;草圖 2 有 、、。逐項相加得
串接後的串流有 、、,直接處理得 、、、,正是同一個表格。因此 ,與整個串流的單一草圖完全相同。
常見錯誤
(把以不同種子建立的草圖相加)
只有描述同一組桶的計數器才可相加。取 、,草圖 1 用 並接收 ,草圖 2 用 並接收 。相加後計數器為 ;用 查詢 讀到 ,但 。即使更新非負,單側保證亦失效,因為合併所得的表格不是任何串流在單一雜湊選擇下的草圖。
表格使用 個計數器,每次更新改動 個計數器;此外還要計算及儲存雜湊描述。若字長模型中算術及雜湊均為常數時間,則使用 個計數器,每次更新及查詢需 次操作。精確非負計數器可達 ;當 ,每個最多需要 個位元。固定字長溢出會破壞精確算術,也可能破壞上述保證。計數器數目小並不自動給出完整的位元記憶體界。
習題
快速檢查
(在第一個例題中,為甚麼即使所有更新非負, 仍大於 ?)
看看每一行中哪些鍵值與 共用桶。
解答 · 答案
兩個受查詢計數是 和 :第 1 行中 與 碰撞並加上 ,第 2 行中 碰撞並加上 。每一行都有正的碰撞貢獻,所以連最小值 也大於 。非負性只保證 ,並不保證相等。
快速檢查
(若 、,按取上整的方法求整數 、,並寫出它們對一個固定鍵值的概率保證。)
解答 · 答案
,。對在抽取雜湊前固定的串流及鍵值,獨立選取各行雜湊後,估計落在 與 之間的概率至少為 。
快速檢查
(用戶查詢草圖、看過表格後,挑出估計看來最大的鍵值。固定鍵值定理能否界定這個估計的誤差?)
解答 · 答案
不能。定理要求鍵值與雜湊獨立地預先固定。看過表格後才選的鍵值,可能正因其桶中碰撞很大而被選中。只有預先指定的 個鍵值集合才受保證,方法是取 的聯集界。