布隆过滤器 / Bloom Filter :快速判断海量数据中是否包含目标数据

Bloom Filter原理

布隆过滤器是一个 bit 向量或者说 bit 数组。

布隆过滤器可以理解是n个hash函数+一个数值(这个数值可能很长)。添加数据的时候就是通过计算改数据的hash函数,然后将得到的位置数据置为1。这样如何判断数值B是否存在时,就一次查看对应N个位置的数值是否有0,如果有0的存在,则必然B不在于该集合中。

如上就是向BloomFilter中添加数值的方法。

布隆过滤器的特性

不能删除元素

布隆过滤器不能删除元素,所以之前看到有说过布隆过滤器的硬件实现版本。 虽然硬件实现也并非意味者完全不能够修改(例如利用FPGA),但是在硬件上频繁的改动是不合适的,而无法删除元素就决定了布隆过滤器只能添加元素,这样就把改动的概率降低一半,在某种场景下可能就无需更改了。

从原理上也很容易理解,暂略不表。

假阳率

和hash碰撞相似,如果通过hash计算,数据A和数据B的hash值相同,也不能说的A=B,只能说

1
2
if hash(A) != hash(B) :
print("A not equals B")

Bloom过滤器和hash也算是一脉相承,自然也有这样的问题。

如果经过bloom过滤器发现数据A的转换值不存在目标集合中,则A绝对不在目标集合中;如果判断存在于目标集合中,则A有极小的概率不在目标集合中。

假阳率/误算率的大小和目标集合的大小有着较大的关系。

Bloom Filter和Hash Table的差异

前面提到的假阳率,这个本质上是hash函数的问题。但是在Hash Table上就不存在这样的问题,这个是因Hash Table是采用了冲突处理的方法,所以Hash Table = Hash function + Collision resolution

上图右侧的节点就代表hash之后冲突的数据,同时记录原数值作为区分标准。

所以Bloom Filter和Hash Table的差异点有:

  • 不记录原始数据;
  • 无法保证验证结果100%的正确率(有一定概率的假阳性)

使用场景

在参考文档中,记录了浏览器通过bloom filter来识别有害网址的方法。具体参看对应参考文档。

不过这个场景也说明了BloomFilter的适用条件:

  • 海量数据
  • 不追求100%的有效性

布隆表达式的一个实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class HashMap(object):
def __init__(self, m, seed):
self.m = m
self.seed = seed

def hash(self, value):
""" Hash Algorithm """
ret = 0
for i in range(len(value)):
ret += self.seed * ret + ord(value[i])
return (self.m - 1) & ret

class BloomFilter(object):
def __init__(self, server, key, bit=BLOOMFILTER_BIT, hash_number=BLOOMFILTER_HASH_NUMBER):
"""
Initialize BloomFilter
:param server: Redis Server
:param key: BloomFilter Key
:param bit: m = 2 ^ bit
:param hash_number: the number of hash function
"""
# default to 1 << 30 = 10,7374,1824 = 2^30 = 128MB, max filter 2^30/hash_number = 1,7895,6970 fingerprints
self.m = 1 << bit
self.server = server
self.key = key
self.maps = [HashMap(self.m, seed) for seed in range(hash_number)]

def exists(self, value):
"""if value exists"""
if not value:
return False
exist = True
for map in self.maps:
offset = map.hash(value)
exist = exist & self.server.getbit(self.key, offset)
return exist

def insert(self, value):
""" add value to bloom"""
for f in self.maps:
offset = f.hash(value)
self.server.setbit(self.key, offset, 1)

如上就是利用redis服务器的位操作来提供一个布隆过滤器,从而可以面向分布式的爬虫系统来提供目标请求是否重复爬取。 在这个过程中需要定义n个hashmap对象,然后通过这nhashmap对象实现判断。整个布隆过滤器提供了两个主要的API:exists以及insert。

参考文档

What are Bloom filters? 从需求触发,引出hash的讨论,最后论述Bloom Filter.

布隆过滤器 随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣

详解布隆过滤器的原理,使用场景和注意事项 介绍了布隆向量的构造过程以及使用redis的实践方法

what-is-the-advantage-to-using-bloom-filters doesn’t store the elements themselves; 答案二给出了一个BloomFilter的使用场景(海量数据的比对)。

哈希表 / 散列表 根据散列函数处理冲突的方法将一组关键字映射到一个有限的连续的地址集;所以hash table和Bloom Filter的较大差异在于后者没有处理冲突的机制。

HashTable 的 Python 实现 要区分hash table和hash function

本文原创,请随意转载,但请添加文章链接,并将链接放置在文章开头,谢谢。

随手请吃块糖呗