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 布隆过滤器内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！