這個(gè)Kata其實(shí)幾天前就完成了，不過最近一直在忙留學(xué)申請(qǐng)的事口猜，沒顧上寫文章负溪。
這次的內(nèi)容就一個(gè)：實(shí)現(xiàn)一個(gè)布隆過濾器。
布隆過濾器（Bloom Filter）
什么是布隆過濾器呢济炎？簡單來說川抡，布隆過濾器可以告訴你一個(gè)元素是否在一個(gè)集合中。
有同學(xué)可能就會(huì)說了须尚，這很簡單啊崖堤，集合中本來就有所有的元素，我只要檢查輸入內(nèi)容是否在里面不就行了耐床。
沒錯(cuò)密幔，這種方法成功率最高（100%），但是效率最低撩轰。
如果只是處理十個(gè)字符串胯甩、一百個(gè)字符串，這都沒問題堪嫂，但是如果要處理成百上千萬的字符串偎箫，顯然是不可行的，空間和時(shí)間都無法接受皆串。
這時(shí)候該主角出場(chǎng)了——布隆過濾器淹办。
布隆過濾器的核心思想就是用盡可能少的空間來存儲(chǔ)盡可能多的內(nèi)容，同時(shí)盡量保證準(zhǔn)確率恶复。布隆過濾器本質(zhì)上很像哈希表怜森，把一個(gè)大的空間映射到一個(gè)小的空間速挑，那么問題就來了，如果兩個(gè)不同元素映射到了同一個(gè)位置怎么辦呢副硅？哈希表有各種算法可以解決沖突姥宝，但是布隆過濾器非常簡單粗暴——我才不管你，映射到同一個(gè)位置那就存同一個(gè)位置想许。
因此伶授，布隆過濾器的準(zhǔn)確率并不是100%。準(zhǔn)確地說流纹，布隆過濾器具有假陽性，也就是說如果它告訴你一個(gè)元素在集合中违诗，那這個(gè)結(jié)果可能是錯(cuò)誤的漱凝，因?yàn)橛锌赡苓@個(gè)元素和集合中另一個(gè)不同的元素映射到了同一位置。但是反過來诸迟，如果它告訴你一個(gè)元素不在集合中茸炒，那這個(gè)元素就肯定不在集合中。所以布隆過濾器在某些場(chǎng)景下是非常合適的阵苇。
為了進(jìn)一步壓縮空間同時(shí)提高準(zhǔn)確率壁公，布隆過濾器有很多種改進(jìn)方法，其中比較常用的是把一個(gè)元素映射到結(jié)果集中的多個(gè)位（bit）绅项。舉例來說紊册，假設(shè)每個(gè)元素會(huì)被映射到5個(gè)點(diǎn)，那么兩個(gè)元素只要有一個(gè)點(diǎn)不相同就可以判斷出來快耿；但是如果只映射到一個(gè)點(diǎn)囊陡，那么這個(gè)點(diǎn)只要相同就無法準(zhǔn)確判斷了，因此映射到多個(gè)點(diǎn)可以增加準(zhǔn)確度掀亥。此外撞反，這個(gè)方法還可以壓縮空間，因?yàn)橛成湟粋€(gè)點(diǎn)的時(shí)候搪花，為了減少碰撞我們必須使用很大的空間遏片，但是映射多個(gè)點(diǎn)的時(shí)候，多個(gè)點(diǎn)全部相同的概率很小撮竿，所以我們就可以使用比較小的空間吮便。
代碼實(shí)現(xiàn)
我用Python實(shí)現(xiàn)了一個(gè)簡易的布隆過濾器，代碼如下
import hashlib
import struct
import math
def readWords(filename):
result = []
with open(filename) as f:
for i in f.readlines():
result.append(i.strip())
return result
def getNBits(hashedWord, mapLen, bitNumber):
binaryHash = "".join(["0" * (4 - len(bin(int(i, 16))[2:])) + bin(int(i, 16))[2:] for i in hashedWord])
wordLen = len(binaryHash)
if bitNumber > wordLen:
bitNumber = wordLen
gap = min(wordLen / bitNumber, mapLen)
return [int(binaryHash[i * gap: (i + 1) * gap], 2) for i in range(bitNumber)]
def buildBloomFilter(all_words, mapLen, bitNumber):
bitmap = [0 for i in range(2**mapLen)]
def assignBitMap(i):
bitmap[i] = 1
for i in all_words:
map(assignBitMap, getNBits(hashlib.md5(i).hexdigest(), mapLen, bitNumber))
return bitmap
def lookUpBitMap(words, bitmap, mapLen, bitNumber):
for i in getNBits(hashlib.md5(words).hexdigest(), mapLen, bitNumber):
if bitmap[i] == 0:
return False
return True
mapLen = 20
bitNumber = 4
bitmap = buildBloomFilter(readWords("/usr/share/dict/words"), mapLen, bitNumber)
print lookUpBitMap("asdasd", bitmap, mapLen, bitNumber) # false
print lookUpBitMap("chinanb", bitmap, mapLen, bitNumber) # false
說實(shí)話用Python進(jìn)行位操作確實(shí)不太方便倚聚。线衫。。
代碼倒數(shù)四五行的mapLen和bitNumber這兩個(gè)參數(shù)是核心惑折，mapLen是最終存儲(chǔ)空間的長度（位）授账，bitNumber是映射點(diǎn)的數(shù)量枯跑。代碼的思路很簡單，先把字符串用md5編碼白热，然后轉(zhuǎn)換成二進(jìn)制并取bitNumber段二進(jìn)制數(shù)敛助，最后把bitmap中這幾段二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制下標(biāo)設(shè)置為1。檢測(cè)的時(shí)候屋确，先計(jì)算出bitNumber段二進(jìn)制數(shù)纳击，然后檢查bitmap，如果這幾個(gè)位置全是1說明（可能）在集合中攻臀，只要有一個(gè)不是1就說明肯定不在集合中焕数。
壓縮率計(jì)算
通過代碼大家也可以看出，布隆過濾器的思路其實(shí)很簡單刨啸，關(guān)鍵是參數(shù)調(diào)優(yōu)堡赔，這里我們是手工選擇了幾個(gè)參數(shù)進(jìn)行測(cè)試，這方面肯定有很多相關(guān)論文和算法设联，大家感興趣的話可以去搜一下善已。
在我們的代碼中，mapLen是20离例，也就是說存儲(chǔ)空間是2的20次方位换团，等于2的17次方字節(jié)，也就是128KB宫蛆。而/usr/share/dict/words這個(gè)文本文件一共2.4MB艘包，也就是2400KB，壓縮率達(dá)到95%Ｈ髟＜稹！
不過這里還是提一下袍冷，我們的參數(shù)只是手工調(diào)整出來的磷醋，也沒有嚴(yán)格地測(cè)量準(zhǔn)確率，所以只是一個(gè)參考胡诗〉讼撸可能實(shí)際使用中壓縮率沒有這么高，也可能比這個(gè)還要高煌恢，我們只是進(jìn)行一些定性的測(cè)試骇陈。
總之，布隆過濾器實(shí)在是太強(qiáng)了瑰抵，在特定場(chǎng)景下可以起到極大的作用你雌！
