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

时间: 2020-08-20

Python+Redis实现布隆过滤器

布隆过滤器是什么 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 布隆过滤器的基本思想 通过一种叫作散列表(又叫哈希表,Hash table)的数据结构.它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点.这样一来,我们只要看看这个点是不是1就可以知道集合中有没

布隆过滤器的概述及Python实现方法

布隆过滤器 布隆过滤器是一种概率空间高效的数据结构.它与hashmap非常相似,用于检索一个元素是否在一个集合中.它在检索元素是否存在时,能很好地取舍空间使用率与误报比例.正是由于这个特性,它被称作概率性数据结构(probabilistic data structure). 空间效率 我们来仔细地看看它的空间效率.如果你想在集合中存储一系列的元素,有很多种不同的做法.你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高.但是,由于ha

python实现布隆过滤器及原理解析

在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

python线程定时器Timer实现原理解析

这篇文章主要介绍了python线程定时器Timer实现原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.线程定时器Timer原理 原理比较简单,指定时间间隔后启动线程!适用场景:完成定时任务,例如:定时提醒-闹钟等等. # 导入线程模块 import threading timer = threading.Timer(interval, function, args=None, kwargs=None) 参数介绍: interval

Python迭代器模块itertools使用原理解析

这篇文章主要介绍了Python迭代器模块itertools使用原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 介绍 今天介绍一个很强大的模块,而且是python自带的,那就是itertools迭代器模块. 使用 使用起来很简单,先导入模块 import itertools 下面,我们通过一些例子边学边练 三个无限迭代器 先告诉大家 control + C 可以强制停止程序哦 1.count() num = itertools.count

python垃圾回收机制(GC)原理解析

这篇文章主要介绍了python垃圾回收机制(GC)原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 今天想跟大家分享的是关于python的垃圾回收机制,虽然本人这会对该机制没有很深入的了解, 但是本着热爱分享的原则,还是囫囵吞枣地坐下记录分享吧, 万一分享的过程中开窍了呢.哈哈哈. 首先还是做一下概述吧: 我们都知道, 在做python的语言编程中, 相较于java, c++, 我们似乎很少去考虑到去做垃圾回收,内存释放的工作, 其实是p

Python线程条件变量Condition原理解析

这篇文章主要介绍了Python线程条件变量Condition原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Condition 对象就是条件变量,它总是与某种锁相关联,可以是外部传入的锁或是系统默认创建的锁.当几个条件变量共享一个锁时,你就应该自己传入一个锁.这个锁不需要你操心,Condition 类会管理它. acquire() 和 release() 可以操控这个相关联的锁.其他的方法都必须在这个锁被锁上的情况下使用.wait()

Python类继承和多态原理解析

这篇文章主要介绍了python类继承和多态原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 现在属于是老年人的脑子,东西写着写着就忘了,东西记着记着就不知道了.之前学C++的时候就把类.对象这块弄得乱七八糟,现在是因为很想玩python,所以就看看python的类和对象. 就像说的,类有三个特征:封装.继承.多态. 1.封装:类封装了一些方法,可通过一定的规则约定方法进行访问权限. C++中的成员变量有public.private.pto

python next()和iter()函数原理解析

这篇文章主要介绍了python next()和iter()函数原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 我们首先要知道什么是可迭代的对象(可以用for循环的对象)Iterable: 一类:list,tuple,dict,set,str 二类:generator,包含生成器和带yield的generatoe function 而生成器不但可以作用于for,还可以被next()函数不断调用并返回下一个值,可以被next()函数不断返回

Python chardet库识别编码原理解析

这篇文章主要介绍了python chardet库识别编码原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 chardet库是python的字符编码检测器,能够检测出各种编码的类型,例如: import chardet import urllib.request testdata = urllib.request.urlopen('http://m2.cn.bing.com/').read() print(chardet.detect(te

Python接口自动化判断元素原理解析

这篇文章主要介绍了Python接口自动化判断元素原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 背景: 在做接口自动化时,通常会判断接口返回中的数据信息,与数据库中返回的数据信息是否一致,比如:将接口返回信息的用户姓名存放到一个列表中,将数据库返回的用户姓名存放到另一个列表中,这时需要判断两个列表是否一致,如果不一致,将不同的元素信息分别回写到excel文件中,可以一目了然的看出哪些信息返回的不正确. 下列代码中直接存放列表信息,比较如