您的位置:

布隆过滤器python代码实现的简单介绍

本文目录一览:

布隆过滤器详解

布隆过滤器 (英语:Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间也会呈现线性增长,最终达到瓶颈。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 , , 。

这个时候,布隆过滤器(Bloom Filter)就应运而生。

了解布隆过滤器原理之前,先回顾下 Hash 函数原理。

哈希函数的概念是:将任意大小的输入数据转换成特定大小的输出数据的函数,转换后的数据称为哈希值或哈希编码,也叫散列值。下面是一幅示意图:

所有散列函数都有如下基本特性:

但是用 hash表存储大数据量时,空间效率还是很低,当只有一个 hash 函数时,还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图(bitmap)和一系列映射函数组成的。

在初始状态时,对于长度为 m 的位数组,它的所有位都被置为0,如下图所示:

当有变量被加入集合时,通过 K 个映射函数将这个变量映射成位图中的 K 个点,把它们置为 1(假定有两个变量都通过 3 个映射函数)。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在,而不是一定存在呢?那是因为映射函数本身就是散列函数,散列函数是会有碰撞的。

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了,这样就无法判断究竟是哪个输入产生的,因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题,因为布隆过滤器的每一个 bit 并不是独占的,很有可能多个元素共享了某一位。如果我们直接删除这一位的话,会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ,另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

在程序的世界中,布隆过滤器是程序员的一把利器,利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有:

知道了布隆过滤去的原理和使用场景,我们可以自己实现一个简单的布隆过滤器

分布式环境中,布隆过滤器肯定还需要考虑是可以共享的资源,这时候我们会想到 Redis,是的,Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件,放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器,但是需要自己设计映射函数和一些细节,这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下,安装 RedisBloom,有两种方式

直接编译进行安装

使用Docker进行安装

使用

布隆过滤器基本指令:

我们只有这几个参数,肯定不会有误判,当元素逐渐增多时,就会有一定的误判了,这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器,它在我们第一次 add 的时候自动创建。

Redis 还提供了自定义参数的布隆过滤器, bf.reserve 过滤器名 error_rate initial_size

但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在,bf.reserve 会报错

我是一名 Javaer,肯定还要用 Java 来实现的,Java 的 Redis 客户端比较多,有些还没有提供指令扩展机制,笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的,我们这里用 Redisson

为了解决布隆过滤器不能删除元素的问题,布谷鸟过滤器横空出世。论文《Cuckoo Filter:Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足:查询性能弱、空间利用效率低、不支持反向操作(删除)以及不支持计数。

由于使用较少,暂不深入。

如何用python写布隆过滤器

下面的是网络上找到的python的布隆过滤器的实现.

#!/usr/local/bin/python2.7

#coding=gbk

'''

Created on 2012-11-7

@author: palydawn

'''

import cmath

from BitVector import BitVector

class BloomFilter(object):

    def __init__(self, error_rate, elementNum):

        #计算所需要的bit数

        self.bit_num = -1 * elementNum * cmath.log(error_rate) / (cmath.log(2.0) * cmath.log(2.0))

        

        #四字节对齐

        self.bit_num = self.align_4byte(self.bit_num.real)

        

        #分配内存

        self.bit_array = BitVector(size=self.bit_num)

        

        #计算hash函数个数

        self.hash_num = cmath.log(2) * self.bit_num / elementNum

        

        self.hash_num = self.hash_num.real

        

        #向上取整

        self.hash_num = int(self.hash_num) + 1

        

        #产生hash函数种子

        self.hash_seeds = self.generate_hashseeds(self.hash_num)

        

    def insert_element(self, element):

        for seed in self.hash_seeds:

            hash_val = self.hash_element(element, seed)

            #取绝对值

            hash_val = abs(hash_val)

            #取模,防越界

            hash_val = hash_val % self.bit_num

            #设置相应的比特位

            self.bit_array[hash_val] = 1

    

    #检查元素是否存在,存在返回true,否则返回false 

    def is_element_exist(self, element):

        for seed in self.hash_seeds:

            hash_val = self.hash_element(element, seed)

            #取绝对值

            hash_val = abs(hash_val)

            #取模,防越界

            hash_val = hash_val % self.bit_num

            

            #查看值

            if self.bit_array[hash_val] == 0:

                return False

        return True

        

    #内存对齐    

    def align_4byte(self, bit_num):

        num = int(bit_num / 32)

        num = 32 * (num + 1)

        return num

    

    #产生hash函数种子,hash_num个素数

    def generate_hashseeds(self, hash_num):

        count = 0

        #连续两个种子的最小差值

        gap = 50

        #初始化hash种子为0

        hash_seeds = []

        for index in xrange(hash_num):

            hash_seeds.append(0)

        for index in xrange(10, 10000):

            max_num = int(cmath.sqrt(1.0 * index).real)

            flag = 1

            for num in xrange(2, max_num):

                if index % num == 0:

                    flag = 0

                    break

            

            if flag == 1:

                #连续两个hash种子的差值要大才行

                if count  0 and (index - hash_seeds[count - 1])  gap:

                    continue

                hash_seeds[count] = index

                count = count + 1

            

            if count == hash_num:

                break

        return hash_seeds

    

    def hash_element(self, element, seed):

        hash_val = 1

        for ch in str(element):

            chval = ord(ch)

            hash_val = hash_val * seed + chval

        return hash_val

'''

#测试代码

bf = BloomFilter(0.001, 1000000)

element = 'palydawn'

bf.insert_element(element)

print bf.is_element_exist('palydawn')'''

#其中使用了BitVector库,python本身的二进制操作看起来很麻烦,这个就简单多了

如果解决了您的问题请采纳!

如果未解决请继续追问

如何用布隆过滤器过滤重复url,求Python代码实现

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组