緊湊的過濾器,不是精確集合
定義 6.1.1
(Bloom 過濾器、假陽性與假陰性)
Bloom 過濾器有 個初始為零的位元,以及 個穩定雜湊函數 ,把鍵值映到索引 。插入鍵值時把所有指定位置設為一;查詢時只要有一個指定位置為零,就回答確定不存在,否則回答可能存在。雜湊輸出可以重複。過濾器不保存鍵值,不能列舉它們,也不能證實正面回答一定正確。假陽性是對未插入的鍵值回答「可能存在」;假陰性是對已插入的鍵值回答「確定不存在」。
定理 6.1.2
(已插入鍵值沒有假陰性)
在雜湊函數穩定、過濾器起初為空且位元不被清除的情況下,每個已插入鍵值在其後的每次查詢中都得到「可能存在」。
證明
(位元只會被設為一)
設 已被插入。插入當刻, 個位元 都成為一。其後的操作只有插入(只會把位元設為一)和查詢(不改變任何東西)。因為函數穩定,之後對 的查詢讀取同樣的 個位置,發現它們全是一,所以絕不會回答「確定不存在」。
未插入鍵值仍可能發現所需位元全被其他鍵值設為一,這就是假陽性。若需要精確成員判定,應在正面回答後查證精確的後端儲存。
跟蹤與不安全刪除
例題 6.1.3
(兩次插入、一個假陽性及一個確定不存在)
取 ,為四個不同鍵值指定如下雜湊輸出。這是例子的指定輸出,不代表某個具體雜湊實作。
| 鍵值 | ||
|---|---|---|
| a | 1 | 5 |
| b | 2 | 5 |
| c | 1 | 2 |
| d | 0 | 5 |
只插入 a 和 b,設為一的位元是 。查詢 c 回答可能存在,雖然 c 沒被插入;查詢 d 因位元 為零而回答確定不存在。出現假陽性不要求 c 的雜湊對與某個已插入鍵值完全相同。
反例模式
清除共用位元會破壞保證
假設嘗試刪除 a,清除位元 和 。鍵值 b 仍在目標集合中,卻需要位元 ,所以下次查詢會錯誤地回答確定不存在。普通位元陣列沒有記錄哪些鍵值共用一個位元。計數變體只有在其自身的計數器、溢位及合法刪除規則下才能支援刪除;本過濾器沒有建立那些規則。
常見錯誤
(把正面回答當成成員的證明)
在上面的跟蹤中,查詢 c 回答可能存在,但 c 從未被插入:位元 和 是 a 和 b 設的。只有「確定不存在」才是對已插入集合的確切陳述。正面回答須對照儲存的鍵值作精確檢查,才算確定。
概率計算的假設
確定的位元位置列表本身沒有內在概率。要建立概率模型,先固定已插入鍵值及一個未插入查詢,並使它們獨立於隨機選取的雜湊。假設這些不同鍵值所用的所有雜湊輸出都在 個索引上獨立且均勻,包括不同函數的輸出。這個理想化模型比只說每個雜湊各自均勻更強。
定理 6.1.4
(均勻模型下的假陽性概率)
在此模型下,插入 個不同鍵值後,令 為值一位元的隨機數目。對未插入的查詢鍵值,假陽性概率 滿足
證明
(以已完成的位元陣列為條件)
給定已完成的位元陣列,未插入查詢的 個輸出獨立且均勻,因為它們獨立於決定該陣列的 個插入輸出。每個輸出落在值一位元的概率為 ,所以 個全部如此的概率為 。對陣列取期望,便得第一個等式。
至於第二個等式:固定位元保持為零,恰當全部 個插入輸出都不等於其索引,概率為 。所以該位元為一的概率是 ,對 個位元求和並用期望線性性,得 。當 ,陣列全為零,,。
證明透視
獨立性用在哪裏
查詢輸出與插入輸出的獨立性只用一次,就是把條件概率寫成 時;沒有它,查詢可能與過濾器內容相關,因子 便不正確。 個查詢輸出之間的獨立性再用一次,才能取 次方。 的期望在求零位元的概率時用到插入輸出的獨立性,但對各位元只用期望線性性,不需要不同位元之間獨立。兩個等式回答不同的問題:第一個給出精確概率,第二個只給出平均佔用率。
把平均值代入 次方得到常用近似,通常不等於次方的精確期望。模型及任何近似都須按實作與工作負載檢查。
常見錯誤
(在次方內以平均佔用數代替隨機佔用數)
令 、,插入一個固定鍵值。其兩個獨立均勻輸出相同的概率為 ,得到 ;否則 。對獨立的未插入查詢,
這裏 ,其平方卻是 ,不是 。佔用數是隨機的,所以不能直接用平均值的次方代替次方的平均值。
例題 6.1.5
(m = 8、k = 2、n = 2 時,以平均值估計與精確值的比較)
共有 個插入輸出。固定位元為零的概率是 ,所以位元為一的概率是 ,以平均值作的估計為 。要求精確值,設查詢輸出為 。若 (概率 ),兩者都落在值一位元的概率為 。若 (概率 ),兩個位元都為一的概率是 ,這由排除任一位元保持為零的情況得出。因此
估計值 與精確值 不同,正如上面 的情況所示。對 同一公式給出 ,因為沒有位元被設為一。
習題與解答
快速檢查
(重複插入。在雜湊穩定時,把同一鍵值插入兩次會怎樣?)
第二次插入設定哪些位元?
解答 · 答案
第二次再把相同位元設為一,陣列不變。
快速檢查
(負面查詢。在例子中,為何 d 確定不存在?)
d 需要哪個位元,而它沒有被設定?
解答 · 答案
它需要的位元 是零,而任何已插入鍵值都會把所需位元設為一。
快速檢查
(細小模型。在 的模型中, 是多少?)
兩個插入輸出何時不同?
解答 · 答案
,因為四個等可能有序輸出對中有兩個的兩項不同。
快速檢查
(精確儲存。若不能接受錯誤的正面回答,Bloom 過濾器能單獨代替集合嗎?)
正面回答能保證甚麼?
解答 · 答案
不能。正面回答可能錯誤,需要精確查證或另一種結構。