python使用布隆过滤器的实现示例
使用库pybloom_live
from pybloom_live import ScalableBloomFilter,BloomFilter
# 可自动伸缩的布隆过滤器
bloom = ScalableBloomFilter(initial_capacity=100,error_rate=0.001)
# 添加内容
bloom.add('daqi')
print('daqi'in bloom)
# 定长的布隆过滤器
bloom1 = BloomFilter(capacity=10000)
bloom1.add('daqi')
print('daqi'in bloom1)
手动实现一个简单的布隆过滤器
使用bitarray实现，将初始数组置为0，根据hash计算出节点置为1，同时写了一个生成随机码的函数用于测试。
import random
import mmh3
from bitarray import bitarray
import os.path
import re
# bitarray长度
BIT_SIZE = 50000
class BloomFilter():
def __init__(self):
bit_array = bitarray(BIT_SIZE)
bit_array.setall(0)
self.bit_array = bit_array
self.bit_size = self.length()
def get_points(self, url):
"""
生成需要插入的位置
:param url:
:return:节点的列表
"""
point_list = []
for i in range(7):
point = mmh3.hash(url,30+i) % self.bit_size
point_list.append(point)
return point_list
def add(self, url):
"""
添加url到bitarray中
:param url:
:return:
"""
res = self.bitarray_expand()
points = self.get_points(url)
try:
for point in points:
self.bit_array[point] = 1
return '注册完成！'
except Exception as e:
return e
def contains(self,url):
"""
验证url是否存在
:param url:
:return:True or False
"""
points = self.get_points(url)
# 在bitarray中查找对应的点，如果有一个点值为0就说明该url不存在
for p in points:
if self.bit_array[p] == 0:
return False
return True
def count(self):
"""
获取bitarrray中使用的节点数
:return: bitarray长度
"""
return self.bit_array.count()
def length(self):
"""
获取bitarray的长度
:return:bitarray的长度
"""
return len(self.bit_array)
def bitarray_expand(self):
"""
扩充bitarray长度
:return:bitarray的长度或使用率，布隆过滤器的bitarray的使用最好不要超过50%,这样误判率低一些
"""
isusespace = round(int(self.count()) / int(self.length()),4)
if 0.50 < isusespace:
# 新建bitarray
expand_bitarray = bitarray(BIT_SIZE)
expand_bitarray.setall(0)
# 增加新建的bitarray
self.bit_array = self.bit_array + expand_bitarray
self.bit_size = self.length()
return self.bit_size
else:
return f'长度尚可,{round(isusespace * 100,2)}%'
def get_captcha():
"""
生成用于测试的随机码
:return:
"""
seed = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
captcha = ""
for i in range(10):
captcha += random.choice(seed)
print(captcha)
return captcha
if __name__ == '__main__':
bloom = BloomFilter()
for i in range(100000):
bloom.add(f'www.{get_captcha()}.com')
print(bloom.length())
print(bloom.count())
print(bloom.count())
到此这篇关于python使用布隆过滤器的实现示例的文章就介绍到这了,更多相关python 布隆过滤器内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！
您可能感兴趣的文章:布隆过滤器的概述及Python实现方法Python+Redis实现布隆过滤器python实现布隆过滤器及原理解析
