摘要：布隆過濾器的實現，包括標準計數標準擴容計數擴容。計數擴容布隆過濾器標準擴容布隆過濾器的子類，功能繼承自標準擴容布隆過濾器，但支持刪除元素的操作。

github:bloompy

布隆過濾器的Python3實現，包括標準、計數、標準擴容、計數擴容。更新自pybloom。

pip install bloompy

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

標準布隆過濾器

標準布隆過濾器只能進行數據的查詢和插入，是下面幾種過濾器的基類，可以進行過濾器的存儲和恢復

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

# 查詢元素是否在過濾器里返回狀態標識
# 如果不在里面則插入，返回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")

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

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

# 返回已經插入的元素個數
>>> bf.count
2

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

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

# 過濾器位數組長度
>>> bf.bit_num
14400

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

# 過濾器哈希函數個數
>>> bf.hash_num
10

計數布隆過濾器

標準布隆過濾器的子類，但是計數布隆過濾器可以執行刪除元素額操作。內置默認使用4位二進制位來表示標準布隆過濾器的1個位，從而實現可以增減。

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

# 與標準布隆過濾器一樣
>>> cbf.add(12)
False
>>> cbf.add(12)
True
>>> 12 in cbf
True
>>> cbf.count
1

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

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

計數布隆過濾器其他的功能與標準的差不多。

標準擴容布隆過濾器

當插入的元素個數超過當前過濾器的容量時，自動增加過濾器的容量，默認內置一次擴容2倍。支持查詢和插入功能。

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

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

#當過濾器的元素個數達到容量極限時，過濾器會自動增加內置的標準過濾器，
#每次增加2倍容量，自動實現擴容
>>> for i in range(1000):
        sbf.add(i)
>>> 600 in sbf
True
>>> len(sbf)
2
>>> sbf.filters
[, ]
>>> sbf.capacity
3000

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

其他功能可以參見標準布隆過濾器。

計數擴容布隆過濾器

標準擴容布隆過濾器的子類，功能繼承自標準擴容布隆過濾器，但支持刪除元素的操作。

>>> 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
[]

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

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

參見標準布隆過濾器，可以通過兩種方式來進行過濾器的存儲與復原：

類方法"fromfile"

函數get_filter_fromfile()

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