在昂貴查詢之前
假設搜尋大型數據庫需要昂貴的磁碟讀取。我們希望先用小型記憶體結構回答:「這個鍵有可能存在嗎?」布隆(Bloom)過濾器的否定回答可以精確,肯定回答卻可能誤報。因此它只能作為初步檢查;若需要精確判斷,回答「可能存在」後仍須查詢權威數據庫。
定義 16.1.1
(布隆過濾器)
取整數 、。布隆過濾器是初始全為零的 位元陣列,配合值域為 的雜湊函數 。插入鍵 時,把 指向的位元都設為一;查詢 時,若全部被指向的位元均為一,回答「可能存在」,否則回答「不存在」。對從未插入的鍵回答「可能存在」,稱為誤報。
容許碰撞,也容許同一鍵的多個位置相同。若雜湊函數固定,重複插入同一鍵不會再改變位元。
命題 16.1.2
(單側正確性)
若一個鍵已插入,而且之後沒有位元被清除,查詢絕不會把它判為不存在。這是確定性結論,不需要隨機雜湊假設。
證明
(位元只會被設為一)
插入時,該鍵指向的每個位元均設為一。其後的插入只會把位元設為一,所以查詢時這些位元仍全為一,回答必為「可能存在」。碰撞及重複插入也包含在論證內。這裏要求插入及查詢使用相同函數和陣列,更新沒有遺失;結論並不保證肯定回答正確。
反方向,即「肯定回答證明了存在」,並不成立。
反例模式
肯定回答不等於真正存在
令 、,插入滿足 的鍵 。若另一個從未插入的鍵 亦滿足 ,查詢 仍會回答「可能存在」。僅憑該位元無法區分兩種歷史。
明確的隨機模型
定義 16.1.3
(固定查詢的理想雜湊模型)
在選取雜湊函數之前,先固定 個互異的已插入鍵,以及一個不在該集合內的查詢鍵。理想雜湊模型假設這 個鍵的 個雜湊值互相獨立,各自在 個位置上均勻分佈。
此理想模型比「每個雜湊值各自均勻」強;實作能否適切近似它,須按雜湊方式和工作負載另行驗證。此結果不自動適用於觀察過濾器後自適應選擇的查詢。
設插入後共有 個一位元。
命題 16.1.4
(佔用量與誤報概率)
在理想雜湊模型下,
其中 是固定查詢鍵被回答「可能存在」的概率。
證明
(佔用量用線性性,查詢用條件化)
共有 次獨立插入位置抽取;一個指定位置從未被抽中的概率為 。把 個位置「被抽中」的指示變量相加,再用期望的線性性,即得 。給定已完成的過濾器後,不存在的查詢鍵的 個位置仍是獨立均勻抽取,因為它們與插入位置獨立。每個位置以條件概率 落在一位元上,所以條件誤報概率為 ;對過濾器取平均便得 。公式也涵蓋 :因 ,此時 ,誤報概率為零。
證明透視
兩個強弱不同的獨立性
證明用了兩次獨立性,兩者不可混為一談。第一,查詢位置與插入位置獨立;這正是查詢鍵必須預先固定、且與所有已插入鍵不同之處。觀察過濾器後才選的查詢,或再次查詢已插入的鍵,都會破壞這一點。第二,給定過濾器時, 個查詢位置互相獨立,於是得到乘積 。它們並非無條件獨立: 大時每一個都較易成功,所以這些事件共用隨機的佔用量。因此要先取 次方,後取平均。確定性的無錯誤否定命題兩者都不需要。
隨機模型用於概率結論,並非上述確定性正確性所需。
精確有限公式與可靠上界
對 ,先選出恰好被佔用的 個位置,再計算其中每個位置至少出現一次的插入位置序列。
命題 16.1.5
(佔用量的精確有限分佈)
在理想雜湊模型下,設 ,並約定 。對 ,
證明
(對遺漏位置作容斥)
所有 個位置序列等概率。固定一組 個位置,先數在這組內取值的 個序列;減去漏掉某指定位置的序列,加回漏掉兩個位置的序列,如此交替,便是內層容斥和。再乘 ,因每個序列的佔用集合唯一。最後對 作條件化並求和。當 ,約定使 的概率為一。公式雖精確,交替項在浮點計算中可能不穩定。
概念視角組合
以滿射計數佔用量
長度為 、恰好佔用一組指定的 個位置的地址序列,就是從 個地址到這 個位置的滿射。這樣的滿射等於先把 個地址分成 個非空塊,再把各塊分配到各位置,所以容斥和等於 ,其中 是第二類 Stirling 數。因此 。當 、 時得到 及 ,與下文計算一致。
不必計算整個分佈,也可由 和 得到可能較鬆的上界:
第一式用 時 ;第二式對每個實現的過濾器都成立。兩者均不假設對插入隨機性取平均後,查詢位元事件仍獨立。常見的 把隨機佔用量換成其平均值;在這個有限模型中它只是近似,通常不是精確概率。
例題 16.1.6
(小型過濾器的修正)
取 、,插入一鍵。兩次位置相同的概率為 ,此時 ;否則 。因此不存在的查詢鍵誤報概率為
平均佔用比例為 ,但其平方是 ,並非 。上述兩個可靠上界分別為 和 ,故此處前者較好。
例題 16.1.7
(計算容斥公式)
取 、,插入一鍵,故 。公式給出
以及 ;這是必然的,兩個位置不可能佔用三格。各概率之和為一。直接計算亦然:兩個位置相同的概率是 。因此
作為比較,,以平均佔用量計算的近似給出 ,低於精確的 。兩個可靠上界為 和 ,均高於精確值。
例題 16.1.8
(兩個不同鍵與重複插入同一鍵)
令 、,插入兩個固定的不同鍵。其位置以 概率相同,此時 ;以 概率不同,此時 。因此固定的不存在查詢鍵有
相反,插入同一鍵兩次會把相同位置設為一兩次:,誤報概率為 。模型中的 是互異插入鍵數,不是插入調用次數。把重複調用當作獨立新雜湊抽取會改變算法,得出錯誤計算。
常見錯誤
(把平均佔用比例的 k 次方當作精確值)
先把隨機佔用量換成平均值,再取次方。由於 在 上是凸函數,Jensen 不等式給出 :在有限模型中,這個近似只會低估精確概率, 時取等號。上面的例子顯示差距: 對 , 對 。
合併、刪除與實際意義
若兩個過濾器使用相同的 、 和雜湊函數,可逐位作 OR 合併。輸出位元為一當且僅當任一輸入位元為一,故結果恰好等於插入兩個集合之聯集所得的陣列。即使集合重疊,此等式仍確定成立。不過聯集的概率計算仍需檢查其互異鍵和查詢鍵是否符合雜湊假設;不同雜湊函數的過濾器不能這樣詮釋。
常見錯誤
(以清除位元來刪除鍵)
直接清除被刪鍵指向的位元並不安全:其他已插入鍵可能共用該位元。例如 時兩鍵都使用唯一位元,清除它會令另一鍵被錯判為不存在。單側正確性命題假設沒有位元被清除,而刪除正好違反這個假設。
計數變體可儲存重數,但安全刪除需要正確的插入記錄、一致的計數更新及沒有溢出或更新遺失;普通位元陣列本身無法重建重數。
過濾器能否節省輸入輸出,取決於記憶體、 次雜湊及誤報查詢的成本是否適合工作負載。佔用率高時大多數查詢都會呈陽性。如果輸入或查詢者能針對所選雜湊作對抗,固定查詢的隨機保證並不是安全保證。應分開記錄雜湊族、種子政策、插入數與實測負載,不把理想模型當成實測。
練習與解答
快速檢查
(令 、,插入一鍵。在理想模型下,固定的不在集合中的查詢鍵誤報概率是多少?)
先數一位元的個數。
解答 · 答案
恰有一位元為一,查詢命中它的概率為 。也可用確定的 得 。
快速檢查
(令 、,插入一鍵並查詢固定的不在集合中的另一鍵。四個雜湊位置全相同的概率是多少?它是否涵蓋所有誤報?)
分開 與 兩種情況。
解答 · 答案
第一個位置任意,其餘三個各以概率 相同,故概率為 。這只涵蓋 的情況;若插入佔滿兩位置,任何查詢都為陽性,另貢獻 ,總計 。
快速檢查
(兩個參數和雜湊均相同的過濾器分別含集合 、。說明即使 ,其 OR 仍是 的過濾器。)
說明 OR 後某位置何時為一。
解答 · 答案
OR 後某位置為一,當且僅當任一集合中有鍵指向它,這正是聯集的插入規則。重複插入不會改變已為一的位元。
快速檢查
(工程師清除離開的鍵所指全部位元。舉出錯誤否定,並說明計數方法需要甚麼額外狀態。)
用最小的過濾器。
解答 · 答案
時插入兩個不同鍵,兩者設同一位元為一。為第一鍵清除後,第二鍵被判不存在。計數器須保留現存貢獻的數目並正確更新,包括處理重複鍵及溢出;普通位元沒有此資訊。
以上計算只關乎有限理想模型中的固定查詢,並非對實際雜湊實作、自適應查詢或任意刪除的普遍保證。