摘要：布隆過(guò)濾器的實(shí)現(xiàn)，包括標(biāo)準(zhǔn)計(jì)數(shù)標(biāo)準(zhǔn)擴(kuò)容計(jì)數(shù)擴(kuò)容。計(jì)數(shù)擴(kuò)容布隆過(guò)濾器標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器的子類，功能繼承自標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器，但支持刪除元素的操作。

github:bloompy

布隆過(guò)濾器的Python3實(shí)現(xiàn)，包括標(biāo)準(zhǔn)、計(jì)數(shù)、標(biāo)準(zhǔn)擴(kuò)容、計(jì)數(shù)擴(kuò)容。更新自pybloom。

pip install bloompy

通過(guò)bloompy你可以使用四種布隆過(guò)濾器

標(biāo)準(zhǔn)布隆過(guò)濾器

標(biāo)準(zhǔn)布隆過(guò)濾器只能進(jìn)行數(shù)據(jù)的查詢和插入，是下面幾種過(guò)濾器的基類，可以進(jìn)行過(guò)濾器的存儲(chǔ)和恢復(fù)

>>> import bloompy
>>> bf = bloompy.BloomFilter(error_rate=0.001,element_num=10**3)

# 查詢?cè)厥欠裨谶^(guò)濾器里返回狀態(tài)標(biāo)識(shí)
# 如果不在里面則插入，返回False表示元素不在過(guò)濾器里
>>> bf.add(1) 
False
>>> bf.add(1)
True
>>> 1 in bf
True
>>> bf.exists(1)
True
>>> bf.add([1,2,3])
False
>>> bf.add([1,2,3])
True
>>> [1,2,3] in bf
True
>>> bf.exists([1,2,3])
True

# 將過(guò)濾器存儲(chǔ)在一個(gè)文件里
>>> bf.tofile("filename.suffix")

# 從一個(gè)文件里恢復(fù)過(guò)濾器。自動(dòng)識(shí)別過(guò)濾器的種類。
>>> recovered_bf = bloompy.get_filter_fromfile("filename.suffix")

# 或者使用過(guò)濾器類的類方法 "fromfile" 來(lái)進(jìn)行過(guò)濾器的復(fù)原。對(duì)應(yīng)的類只能恢復(fù)對(duì)應(yīng)的過(guò)濾器
>>> recovered_bf = bloompy.BloomFilter.fromfile("filename.suffix")

# 返回已經(jīng)插入的元素個(gè)數(shù)
>>> bf.count
2

# 過(guò)濾器的容量
>>> bf.capacity
1000

# 過(guò)濾器的位向量
>>> bf.bit_array
bitarray("00....")

# 過(guò)濾器位數(shù)組長(zhǎng)度
>>> bf.bit_num
14400

# 過(guò)濾器的哈希種子，默認(rèn)是素?cái)?shù)，可修改
>>> bf.seeds
[2, 3, 5, 7, 11,...]

# 過(guò)濾器哈希函數(shù)個(gè)數(shù)
>>> bf.hash_num
10

計(jì)數(shù)布隆過(guò)濾器

標(biāo)準(zhǔn)布隆過(guò)濾器的子類，但是計(jì)數(shù)布隆過(guò)濾器可以執(zhí)行刪除元素額操作。內(nèi)置默認(rèn)使用4位二進(jìn)制位來(lái)表示標(biāo)準(zhǔn)布隆過(guò)濾器的1個(gè)位，從而實(shí)現(xiàn)可以增減。

>>> import  bloompy
>>> cbf  = bloompy.CountingBloomFilter(error_rate=0.001,element_num=10**3)

# 與標(biāo)準(zhǔn)布隆過(guò)濾器一樣
>>> cbf.add(12)
False
>>> cbf.add(12)
True
>>> 12 in cbf
True
>>> cbf.count
1

# 查詢?cè)貭顟B(tài)返回標(biāo)識(shí)，如果元素存在過(guò)濾器里則刪除
>>> cbf.delete(12)
True
>>> cbf.delete(12)
False
>>> 12 in cbf
False
>>> cbf.count
0

# 從文件中恢復(fù)過(guò)濾器
>>> recovered_cbf = bloompy.CountingBloomFilter.fromfile("filename.suffix")

計(jì)數(shù)布隆過(guò)濾器其他的功能與標(biāo)準(zhǔn)的差不多。

標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器

當(dāng)插入的元素個(gè)數(shù)超過(guò)當(dāng)前過(guò)濾器的容量時(shí)，自動(dòng)增加過(guò)濾器的容量，默認(rèn)內(nèi)置一次擴(kuò)容2倍。支持查詢和插入功能。

>>> import bloompy
>>> sbf = bloompy.ScalableBloomFilter(error_rate=0.001,initial_capacity=10**3)

# 默認(rèn)初次可以設(shè)置容量1000
>>> len(sbf)
0
>>> 12 in sbf
False
>>> sbf.add(12)
False
>>> 12 in sbf 
True
>>> len(sbf)
1
>>> sbf.filters
[]
>>> sbf.capacity
1000

#當(dāng)過(guò)濾器的元素個(gè)數(shù)達(dá)到容量極限時(shí)，過(guò)濾器會(huì)自動(dòng)增加內(nèi)置的標(biāo)準(zhǔn)過(guò)濾器，
#每次增加2倍容量，自動(dòng)實(shí)現(xiàn)擴(kuò)容
>>> for i in range(1000):
        sbf.add(i)
>>> 600 in sbf
True
>>> len(sbf)
2
>>> sbf.filters
[, ]
>>> sbf.capacity
3000

# 從文件中恢復(fù)過(guò)濾器
>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile("filename.suffix")

其他功能可以參見(jiàn)標(biāo)準(zhǔn)布隆過(guò)濾器。

計(jì)數(shù)擴(kuò)容布隆過(guò)濾器

標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器的子類，功能繼承自標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器，但支持刪除元素的操作。

>>> import bloompy
>>> scbf = bloompy.SCBloomFilter(error_rate=0.001,initial_capacity=10**3)

>>> scbf.add(1)
False
>>> 1 in scbf
True
>>> scbf.delete(1)
True
>>> 1 in scbf
False
>>> len(scbf)
1
>>> scbf.filters
[]

# 插入元素使其達(dá)到過(guò)濾器當(dāng)前容量極限值
>>> for i in range(1100):
        scbf.add(i)
>>> len(scbf)
2
>>> scbf.filters
[, ]

# 從文件中恢復(fù)過(guò)濾器
>>> recovered_scbf = bloompy.SCBloomFilter.fromfile("filename.suffix")

參見(jiàn)標(biāo)準(zhǔn)布隆過(guò)濾器，可以通過(guò)兩種方式來(lái)進(jìn)行過(guò)濾器的存儲(chǔ)與復(fù)原：

類方法"fromfile"

函數(shù)get_filter_fromfile()

如果你很清楚的知道當(dāng)前文件中的過(guò)濾器是一個(gè)標(biāo)準(zhǔn)布隆過(guò)濾器，那么你可以使類方法類恢復(fù)這個(gè)過(guò)濾器:
 bloompy.BloomeFilter.fromfile("filename.suffix) 
如果是個(gè)計(jì)數(shù)布隆過(guò)濾器，那么就是使用:
bloompy.CountingBloomFilter.fromfile("filename.suffix)
其他也是使用對(duì)應(yīng)的類方法來(lái)恢復(fù)對(duì)應(yīng)的過(guò)濾器。 
但如果你不知道文件里存儲(chǔ)是哪種過(guò)濾器，可以使用函數(shù):
bloompy.get_filter_fromfile("filename.suffix") 
它將會(huì)加載文件字節(jié)數(shù)據(jù)，自動(dòng)判斷過(guò)濾器類型并返回對(duì)應(yīng)實(shí)例進(jìn)行復(fù)原。