李卓宇，夏必勝，馬樂(lè)榮

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000)

1 布隆過(guò)濾器算法

1.1 背景和原理

布隆過(guò)濾器(Bloom Filter)是在1970年由布隆(Burton Howard Bloom)提出，是一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，它由一個(gè)很長(zhǎng)的二進(jìn)制向量(位向量)和一系列隨機(jī)均勻分布的散列(哈希)函數(shù)組成[1]。用多個(gè)散列函數(shù)，將一個(gè)數(shù)據(jù)映射到位數(shù)組結(jié)構(gòu)中，可以用來(lái)高效地插入元素和檢索判斷“某個(gè)元素一定不存在或者可能存在于某個(gè)集合當(dāng)中”。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內(nèi)存空間[2]。

當(dāng)一個(gè)元素被加入元素集合時(shí)，通過(guò)k個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的k個(gè)點(diǎn)(特征)，把它們置為1，檢索時(shí)這些點(diǎn)如果是1，則被檢元素可能存在，如果這些點(diǎn)當(dāng)中有任何一個(gè)0，則被檢元素一定不在。

基本思路：①設(shè)數(shù)據(jù)集A={a1,a2,…,an}含n個(gè)元素，作為待操作的集合；②Bloom Filter用一個(gè)長(zhǎng)度為m的位向量V={b1,b2,…,bm}表示集合中的元素，位向量的初始值全為0；③獲得k個(gè)具有均勻分布特性的散列函數(shù)；④對(duì)于集合中的每一個(gè)元素，首先經(jīng)過(guò)k個(gè)散列函數(shù)產(chǎn)生k個(gè)隨機(jī)數(shù)h1,h2,…,hk，使向量V的相應(yīng)位置{b1,b2,…,bm}均置為1。集合中其他元素也通過(guò)該操作將向量V的若干位置為1；⑤對(duì)于待查找的元素，首先將該元素經(jīng)過(guò)前四步操作獲得k個(gè)隨機(jī)數(shù)h1,h2,…,hk，然后檢查向量V的相應(yīng)位置{b1,b2,…,bm}上的值，若全為1，則該元素可能存在于集合中，若至少有一個(gè)0存在，則元素不在該集合中，為新元素。步驟過(guò)程如圖1、圖2、圖3所示。

圖1 位數(shù)組m的初始狀態(tài)

圖2 集合A中元素的位置狀態(tài)

圖3 查找狀態(tài)

1.2 算法優(yōu)缺點(diǎn)

關(guān)于布隆過(guò)濾器的優(yōu)點(diǎn)有以下6個(gè)：①在增加元素或查詢?cè)氐臅r(shí)候其時(shí)間復(fù)雜度都為O(k)，(k是散列函數(shù)的個(gè)數(shù)，一般都比較小)，且該時(shí)間復(fù)雜度與數(shù)據(jù)量的大小沒(méi)有關(guān)系；②散列函數(shù)相互之間沒(méi)有關(guān)系，在硬件方面實(shí)現(xiàn)并行運(yùn)算很方便[3]；③布隆過(guò)濾器不需要存儲(chǔ)元素本身，所以對(duì)某些數(shù)據(jù)要求嚴(yán)格保密的情況下選擇布隆過(guò)濾器更好；④在能夠承擔(dān)一定的誤判時(shí)，布隆過(guò)濾器和其他的數(shù)據(jù)結(jié)構(gòu)對(duì)比更具有空間優(yōu)勢(shì)；⑤數(shù)據(jù)量很大時(shí)，布隆過(guò)濾器可以表示全集，而其他數(shù)據(jù)結(jié)構(gòu)不能；⑥使用同一組散列函數(shù)的布隆過(guò)濾器可以進(jìn)行交、并、差運(yùn)算。

當(dāng)然，布隆過(guò)濾器也有它的缺點(diǎn)。第一，存在誤判(假陽(yáng)性)[4]。那就是既不能準(zhǔn)確判斷元素是否存在于該集合當(dāng)中，也不能獲得這個(gè)元素，只能判斷這個(gè)元素存在或者不存在。因?yàn)榇嬖谡`判，所以誤判率被提出來(lái)，對(duì)于固定長(zhǎng)度的位數(shù)組來(lái)說(shuō)，當(dāng)存入的元素?cái)?shù)量增加，那么誤判率就會(huì)增加。第二，通常情況下不能從布隆過(guò)濾器中刪除元素。對(duì)于一個(gè)已經(jīng)放入布隆過(guò)濾器的元素，通過(guò)散列函數(shù)將它映射到位數(shù)組的k個(gè)位置上是1，那么刪除的時(shí)候就不能直接將這些位置重新置為0，因?yàn)橥粋€(gè)位有可能有好幾個(gè)隨機(jī)數(shù)都標(biāo)記了它，直接刪除可能會(huì)影響其他元素的判斷。雖然布隆過(guò)濾器可以支持刪除，但刪除的效率不高而且浪費(fèi)空間[5]。當(dāng)然現(xiàn)在也有一些支持刪除操作的方法，如采用計(jì)數(shù)方式刪除一個(gè)元素，但在計(jì)算過(guò)程中可能就會(huì)存在計(jì)數(shù)回繞問(wèn)題[6]。

2 布隆過(guò)濾器算法的誤判率

2.1 最小誤判率

(1)

(2)

所以布隆過(guò)濾器真實(shí)誤判率為：

(3)

現(xiàn)在要檢測(cè)某一元素是否在該集合當(dāng)中，需要判斷這個(gè)元素通過(guò)散列函數(shù)映射以后，對(duì)應(yīng)的位數(shù)組上的k個(gè)特征位都置為1。但是該方法可能會(huì)錯(cuò)誤的認(rèn)為原本不在集合中的元素是在集合中的，所以對(duì)于規(guī)定的數(shù)組長(zhǎng)度m和元素個(gè)數(shù)n，散列函數(shù)的個(gè)數(shù)k是至關(guān)重要的，只有求得k的極值，才能知道誤判率P最小的時(shí)候關(guān)于k的取值個(gè)數(shù)。

因此對(duì)(3)式兩邊取對(duì)數(shù)，得到：

(4)

(5)

lnt0·t0=lnu0·u0。

設(shè)函數(shù)f(x)=lnx·x，那么就有

f(t0)=lnt0·t0，f(u0)=lnu0·u0，

即f(t0)=f(u0)。

(6)

(7)

所以要使得誤判率最小，那么散列函數(shù)的個(gè)數(shù)k的取值就是公式(7)計(jì)算所得。由此可知，如果規(guī)定位數(shù)組m的長(zhǎng)度大小小于集合中要輸入的元素個(gè)數(shù)n時(shí)，那么誤判率P就會(huì)增加。

2.2 誤判率P與m、n、k的關(guān)系

根據(jù)布隆過(guò)濾器的誤判率，總結(jié)了以下的關(guān)系：

①誤判率P與m位數(shù)組長(zhǎng)度的關(guān)系

由公式(3)可知，當(dāng)元素?cái)?shù)量n和散列函數(shù)個(gè)數(shù)k不變，m的長(zhǎng)度增加的時(shí)候，說(shuō)明存儲(chǔ)空間增大了，誤判率P就會(huì)減小。

②誤判率P與k個(gè)哈希函數(shù)計(jì)算量的關(guān)系

(8)

③誤判率P與n的關(guān)系

令位數(shù)組長(zhǎng)度m和散列函數(shù)的個(gè)數(shù)k不變，輸入元素n的大小取決于實(shí)際任務(wù)的決策，所以當(dāng)n減小時(shí)，P顯然減小。

3 應(yīng)用

3.1 置信度與置信區(qū)間分析

對(duì)于置信區(qū)間的分析，用一個(gè)范圍來(lái)對(duì)某個(gè)事情進(jìn)行估計(jì)的方式稱為區(qū)間估計(jì)，在該區(qū)間估計(jì)中，由樣本估計(jì)量構(gòu)造出的總體參數(shù)在一定置信水平下得出來(lái)的區(qū)間就稱為置信區(qū)間[8]。區(qū)間的最小值為置信下限，用a表示，區(qū)間的最大值是置信上限，用b表示，所以置信區(qū)間就表示為[a,b]。對(duì)于置信度的分析，把這個(gè)估算的區(qū)間的準(zhǔn)確度(可信度)稱為置信度(也叫置信水平或置信系數(shù))。一般置信度和置信區(qū)間是同向也就是具有一樣的趨勢(shì)。當(dāng)置信度很高時(shí)，置信區(qū)間也會(huì)很大；當(dāng)置信區(qū)間很大時(shí)，置信度也會(huì)很高。

表1 置信度和標(biāo)準(zhǔn)分值的對(duì)應(yīng)表

通過(guò)上述公式的計(jì)算，置信度為90%、95%、99%時(shí)誤判率的置信區(qū)間結(jié)果如表2所示。

表2 預(yù)估誤判率的置信區(qū)間結(jié)果

3.2 置信度為95%，元素規(guī)模n大小為1e10、1e11、1e12時(shí)的m，k

(9)

引入公式(7)和公式(9)，相應(yīng)的位數(shù)組長(zhǎng)度m和散列函數(shù)個(gè)數(shù)k計(jì)算結(jié)果(均保留整數(shù))如表3所示。

表3 元素規(guī)模n為1e10、1e11、1e12時(shí)的m、k

4 結(jié)論

(1)布隆過(guò)濾器是通過(guò)散列函數(shù)映射到位數(shù)組上的一種數(shù)據(jù)結(jié)構(gòu)，用來(lái)查找判斷某個(gè)元素是否在當(dāng)前集合里[10]。散列函數(shù)的所有特征點(diǎn)對(duì)應(yīng)的位數(shù)組至少存在一個(gè)0，那該元素一定不在集合里；如果全部為1，那么該元素在這個(gè)集合里。布隆過(guò)濾器比其他數(shù)據(jù)結(jié)構(gòu)具有很多的優(yōu)勢(shì)，如時(shí)間復(fù)雜度小、散列函數(shù)相互獨(dú)立、無(wú)需存儲(chǔ)元素本身、能高效查詢又能節(jié)省大量的內(nèi)存空間、可以表示為全集，可以做基本的并交差運(yùn)算。但是布隆過(guò)濾器也存在誤判，會(huì)將不屬于集合的元素判斷為屬于，并且一般情況下不能刪除元素。

(3)對(duì)置信度設(shè)置為90%、95%、99%時(shí)誤判率的置信區(qū)間進(jìn)行了分析，同時(shí)計(jì)算了置信度為95%，元素的規(guī)模為1e10(十億級(jí))、1e11(百億級(jí))、1e12(千億級(jí))時(shí)的位數(shù)組長(zhǎng)度m分別能存儲(chǔ)7GB，73GB，726GB的數(shù)據(jù)容量，其散列函數(shù)個(gè)數(shù)k都為4。