核心概念#
在日常生活和軟體開發中，經常需要判斷一個元素是否在一個集合中（如拼字檢查、黑名單過濾、爬蟲去重等）。布隆過濾器（Bloom Filter）是一種用極少空間高效解決此問題的數學工具。
1. 布隆過濾器的原理#
問題背景#
- 用哈希表存儲集合元素，優點是快速準確，缺點是耗費存儲空間
- 以電子郵件黑名單為例：存儲一億個地址需要約 1.6GB 記憶體，幾十億個地址就需要上百 GB，一般伺服器存不下
- 布隆過濾器只需哈希表 1/8 到 1/4 的大小就能解決同樣的問題
工作原理#
- 布隆過濾器由伯頓·布隆（Burton Bloom）於 1970 年提出
- 本質上是一個很長的二進制向量和一系列隨機映射函數
- 具體步驟：
- 建立一個 16 億比特的向量，全部清零
- 對每個電子郵件地址 $X$，用 8 個不同的隨機數產生器 $(F_1, F_2, \ldots, F_8)$ 產生 8 個資訊指紋
- 再用一個隨機數產生器 $G$ 把指紋映射到 1-16 億中的 8 個位置
- 將這 8 個位置的比特設置為 1
- 檢測時：對可疑地址 $Y$ 同樣產生 8 個指紋，檢查對應的 8 個比特是否都為 1
特性#
- 不會漏掉黑名單中的任何元素（零假陰性）
- 但有極小概率將不在黑名單中的元素誤判為在其中（假陽性），因為對應的比特位可能被其他地址「恰巧」設置為 1
- 常見的補救辦法是建立一個小的白名單，存儲被誤判的郵件地址
2. 延伸閱讀：布隆過濾器的誤識別問題#
- 假定布隆過濾器有 $m$ 比特，$n$ 個元素，每個元素對應 $k$ 個散列函數
- 插入 $n$ 個元素後，某個比特仍為 0 的概率是 $(1 - \frac{1}{m})^{kn}$
- 一個不在集合中的元素被誤識別的概率（假陽性率）為：
$$\left(1 - \left[1 - \frac{1}{m}\right]^{kn}\right)^k \approx \left(1 - e^{-\frac{kn}{m}}\right)^k$$
- 假定每個元素用 16 比特、$k = 8$，假陽性概率約為萬分之五，在大部分應用中可以接受
麥迪遜威斯康星大學的曹培（Pei Cao）教授提供了 $m/n$ 比值和 $k$ 分別為不同值時的假陽性概率表。例如 $m/n = 16, k = 8$ 時，誤識別率僅為 0.0215%。
本章小結#
布隆過濾器背後的數學原理在於兩個完全隨機的數字相衝突的概率很小，因此可以在很小的誤識別率條件下，用很少的空間存儲大量資訊。布隆過濾器中只有簡單的算術運算，速度很快，使用方便。