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

github:bloompy

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

pip install bloompy

通過bloompy你可以使用四種布隆過濾器

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

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

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

# 查詢元素是否在過濾器里返回狀態(tài)標(biāo)識
# 如果不在里面則插入，返回False表示元素不在過濾器里
>>> 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

# 將過濾器存儲在一個文件里
>>> bf.tofile("filename.suffix")

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

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

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

# 過濾器的容量
>>> bf.capacity
1000

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

# 過濾器位數(shù)組長度
>>> bf.bit_num
14400

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

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

計數(shù)布隆過濾器

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

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

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

# 查詢元素狀態(tài)返回標(biāo)識，如果元素存在過濾器里則刪除
>>> cbf.delete(12)
True
>>> cbf.delete(12)
False
>>> 12 in cbf
False
>>> cbf.count
0

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

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

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

當(dāng)插入的元素個數(shù)超過當(dāng)前過濾器的容量時，自動增加過濾器的容量，默認(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)過濾器的元素個數(shù)達(dá)到容量極限時，過濾器會自動增加內(nèi)置的標(biāo)準(zhǔn)過濾器，
#每次增加2倍容量，自動實(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ù)過濾器
>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile("filename.suffix")

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

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

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

>>> 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á)到過濾器當(dāng)前容量極限值
>>> for i in range(1100):
        scbf.add(i)
>>> len(scbf)
2
>>> scbf.filters
[, ]

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

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

類方法"fromfile"

函數(shù)get_filter_fromfile()

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