1. 前言
Bloom Filter的名字早有耳聞枷畏，但一直沒看實(shí)現(xiàn)原理。今天乘地鐵時(shí)心血來潮看了算法趣兄，頓時(shí)被其簡單與優(yōu)雅震驚木羹。摘錄下wiki上的介紹：
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.
Bloom Filter是一種高效利用空間的概率數(shù)據(jù)結(jié)構(gòu)，由Burton Howard Bloom于1970年發(fā)明峰锁，用于檢測一個(gè)元素是否屬于一個(gè)集合萎馅。
講個(gè)小插曲，我剛開始以為bloom作「開花虹蒋，繁盛」解糜芳，沒想到是發(fā)明人的名字，真相總是沒有想象的美好呢…
我的實(shí)現(xiàn)：https://github.com/liquidconv/DSAF
2. 學(xué)習(xí)Bloom Filter
2.1 爬蟲與集合操作
Bloom Filter通常和爬蟲聯(lián)系在一起魄衅，所以用這個(gè)例子解釋其特性再好不過峭竣。爬蟲最常用的抓取方法是廣度優(yōu)先搜索BFS，概括地說就是：
- 維護(hù)一個(gè)待訪問鏈接的隊(duì)列
- 每次將隊(duì)首元素晃虫，即里第一個(gè)鏈接出隊(duì)
- 將該鏈接對(duì)應(yīng)的頁面上所有鏈接入隊(duì)
- 重復(fù)1~3至隊(duì)列空為止
上面的描述里存在一個(gè)很大的問題——第三步里要加入隊(duì)列的鏈接可能沒有訪問過皆撩，可能已經(jīng)訪問過，如果不做判斷一律加入的話哲银，一個(gè)相同的頁面就可能被訪問幾千幾萬次扛吞，造成資源浪費(fèi)。
要解決也很簡單盘榨，只要維護(hù)一個(gè)訪問過鏈接的集合就可以了喻粹。鏈接入隊(duì)之前，先判斷是否屬于該集合草巡，即是否已經(jīng)訪問過了守呜，屬于就不入隊(duì)，不屬于才入隊(duì)山憨。
2.2 思考
我們需要一個(gè)「集合」數(shù)據(jù)結(jié)構(gòu)查乒，至少要能夠支持插入元素到集合和判斷元素是否屬于集合——也就是插入和屬于這兩種操作，要怎么實(shí)現(xiàn)呢郁竟？
可行思路：數(shù)組/鏈表/樹/哈希表
暫時(shí)不考慮插入和查找操作的時(shí)間復(fù)雜度玛迄，上面每種做法里數(shù)據(jù)單元（數(shù)組的元素，鏈表和樹的節(jié)點(diǎn)棚亩，哈希表的表項(xiàng)）定義形式基本都是：
typedef struct data_item {
key k; // 原始數(shù)據(jù)蓖议，或者原始數(shù)據(jù)的hash值等
extra e ; // 附加信息，指向其它節(jié)點(diǎn)的指針等
};
每次向集合插入元素都要生成新的data_item讥蟆，空間復(fù)雜度是O(N)勒虾，大數(shù)據(jù)情況下hold不住。
算法里經(jīng)常有時(shí)空權(quán)衡的問題瘸彤，可以用空間換時(shí)間保存子問題結(jié)果修然，比如動(dòng)態(tài)規(guī)劃；可以用時(shí)間換空間，比如用泰勒展開計(jì)算三角函數(shù)愕宋。當(dāng)時(shí)間和空間都不能犧牲的時(shí)候玻靡，就只能犧牲正確率了。Bloom Filter之所以稱為概率數(shù)據(jù)結(jié)構(gòu)中贝，就是因?yàn)樗牟僮鹘Y(jié)果有一定概率是錯(cuò)誤的囤捻。
2.3 圖解Bloom Filter
Bloom Filter的核心是一個(gè)m位的bitset和k個(gè)hash函數(shù)。
初始時(shí)bitset中所有位的值都設(shè)置為0雄妥，假設(shè)取m = 10最蕾，k = 3依溯，用藍(lán)色表示某位為0老厌，紅色表示為1：
插入元素的過程是三步走：
- 計(jì)算k個(gè)hash值
- 將k個(gè)hash值對(duì)m取模得到k個(gè)下標(biāo)
- 將bitset中k個(gè)下標(biāo)對(duì)應(yīng)的位設(shè)置為1
比如向剛才的Bloom Filter插入元素“Alice”。分別用3個(gè)hash函數(shù)計(jì)算“Alice”的hash值黎炉，將hash值對(duì)10取模枝秤，得到在[0, 10)范圍內(nèi)的r1、r2慷嗜、r3淀弹，假設(shè)計(jì)算結(jié)果為：
r1 = h1("Alice") % m = 1
r2 = h2("Alice") % m = 3
r3 = h3("Alice") % m = 5
于是將bitset中第1位、第3位和第5位的值置為1：
再插入元素“Bob”的過程還是一樣的庆械，假設(shè)：
r1 = h1("Bob") % m = 8
r2 = h2("Bob") % m = 2
r3 = h3("Bob") % m = 3
那就將bitset中第2位薇溃、第3位、第8位的值置為1（值已經(jīng)為1的第3位不動(dòng)）：
圖形化思考的話就是缭乘，Bloom Filter運(yùn)行過程中不斷插入新元素沐序，bitset里的0逐漸被翻轉(zhuǎn)成1。
怎么判斷元素“Alice”是否在集合里呢堕绩？同樣還是三步走：
- 計(jì)算k個(gè)hash值
- 將k個(gè)hash值對(duì)m取模得到k個(gè)下標(biāo)
- 檢查bitset中k個(gè)下標(biāo)對(duì)應(yīng)的位是否都為1
如果Bloom Filter里有“Alice”策幼，那bitset中相應(yīng)的k位值顯然都為1。問題是即使Bloom Filter里沒有“Alice”奴紧，還是可能由于之前插入的元素而導(dǎo)致“Alice”對(duì)應(yīng)的k位值都為1特姐，因此會(huì)錯(cuò)誤地認(rèn)為集合里已經(jīng)有“Alice”了，這就是Bloom Filter會(huì)出錯(cuò)的地方黍氮。
由于bitset里每位都和多個(gè)元素有關(guān)唐含，將某個(gè)為1的位置為0，涉及到這位的元素都會(huì)被認(rèn)為不屬于集合沫浆，所以Bloom Filter不支持刪除操作捷枯。
2.4 復(fù)雜度分析
空間復(fù)雜度方面，Bloom Filter不會(huì)動(dòng)態(tài)增長件缸，運(yùn)行過程中維護(hù)的始終只是m位的bitset铜靶，所以空間復(fù)雜度只有O(m)。
時(shí)間復(fù)雜度方面，Bloom Filter的插入與屬于操作主要都是在計(jì)算k個(gè)hash争剿，所以都是O(k)已艰。
3. 實(shí)現(xiàn)Bloom Filter
3.1 定義Bloom Filter類
STL里的bitset定義時(shí)就要給定長度，而且之后不能改變蚕苇，所以我用了vector<bool>哩掺。
#ifndef __BLOOM_FILTER_H__
#define __BLOOM_FILTER_H__
#include <vector>
#include <string>
class BloomFilter {
public:
BloomFilter(unsigned int m, unsigned int k);
void insertElement(std::string s);
bool existsElement(std::string s);
private:
unsigned int BKDR_Hash(std::string s, unsigned int i);
unsigned int getSeed(unsigned int hash_index);
std::vector<bool> table;
unsigned int _m;
unsigned int _k;
};
#endif // __BLOOM_FILTER_H__
定義非常簡單：
- _m是bitset的大小，table是bitset
- _k是hash函數(shù)的數(shù)量
- BKDR_Hash是使用了參數(shù)seed的hash函數(shù)
- 用getSeed生成_k種seed涩笤，相當(dāng)于有了_k種hash函數(shù)
- insertElement對(duì)于插入操作
- existsElement對(duì)應(yīng)查找操作
構(gòu)造函數(shù)
BloomFilter::BloomFilter(unsigned int m, unsigned int k):
_m(m), _k(k) {
table.resize(_m);
for(int i = 0; i < _m; ++i)
table[i] = false;
}
3.2 插入與屬于
插入操作 = 計(jì)算_k個(gè)hash值嚼吞，將table中對(duì)應(yīng)位置改為true：
void BloomFilter::insertElement(string s) {
for(int i = 0; i < _k; ++i) {
unsigned int index = BKDR_Hash(s, i);
table[index] = true;
}
}
屬于操作 = 計(jì)算_k個(gè)hash值，檢查table中對(duì)應(yīng)位置是否都為true：
bool BloomFilter::existsElement(string s) {
for(int i = 0; i < _k; ++i) {
unsigned int index = BKDR_Hash(s, i);
if(!table[index])
return false;
}
return true;
}
3.3 BKDR Hash
選擇BKDR Hash最主要的原因就是有參數(shù)seed蹬碧，很容易就能構(gòu)造一族Hash函數(shù)舱禽。seed是個(gè)「魔數(shù)」（magic number），所以不用多糾結(jié)恩沽，推薦取的值為：
131,1313,13131,...
生成第hash_index個(gè)Hash函數(shù)的seed：
unsigned int BloomFilter::getSeed(unsigned int hash_index) {
string seed = "13";
for(int i = 0; i < hash_index; ++i)
seed += (i % 2 == 0)? "1" : "3";
return atoi(seed.c_str());
}
用第hash_index個(gè)Hash函數(shù)計(jì)算字符串s的hash值：
unsigned int BloomFilter::BKDR_Hash(string s, unsigned int hash_index) {
const char *ps = s.c_str();
unsigned int seed = getSeed(hash_index);
unsigned int hash = 0;
for(int i = 0; i < s.size(); ++i)
hash += hash * seed + ps[i];
return hash % _m;
}
4. 數(shù)學(xué)部分
Bloom Filter的原理已經(jīng)講完誊稚，但還是有必要提一下錯(cuò)誤率的問題。錯(cuò)誤率有兩種：
- FP = false positive
- FN = false negative
對(duì)應(yīng)Bloom Filter的情況下罗心，F(xiàn)P就是「集合里沒有某元素里伯，查找結(jié)果是有該元素」，F(xiàn)N就是「集合里有某元素渤闷，查找結(jié)果是沒有該元素」疾瓮。FN顯然總是0，F(xiàn)P會(huì)隨著Bloom Filter中插入元素的數(shù)量而增加——極限情況就是所有bit都為1飒箭，這時(shí)任何元素都會(huì)被認(rèn)為在集合里狼电。
FP的推導(dǎo)并不復(fù)雜，wiki上有非常詳細(xì)的過程补憾，這里就簡單地抄個(gè)結(jié)果漫萄，其中n是當(dāng)前集合里元素的數(shù)量：
從這個(gè)公式里可以讀出一些直觀的信息：
- n = 0時(shí)盈匾，F(xiàn)P = 0腾务；n趨于無窮大時(shí)，F(xiàn)P趨于1
- k/m和n保持不變時(shí)削饵，k越大岩瘦，F(xiàn)P越小
m和k決定了Bloom Filter的「容量」，當(dāng)然hash函數(shù)的選擇也很重要窿撬。
5. 參考資料
- Bloom Filter
https://en.wikipedia.org/wiki/Bloom_filter - Precision and recall
https://en.wikipedia.org/wiki/Precision_and_recall - BloomFilter——大規(guī)模數(shù)據(jù)處理利器
http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html - 各種Hash函數(shù)和代碼
http://www.cppblog.com/bellgrade/archive/2009/09/29/97565.html
