028-86261949

当前位置:首页 > 技术交流 > 布隆过滤器简介和Python实现

布隆过滤器简介和Python实现

2019/04/09 17:37 分类: 技术交流 浏览:13

假设您正在Geekbook上创建一个帐户,您想输入一个很酷的用户名,您输入它但是却收到一条消息:“用户名已被占用”。你在用户名中添加了你的出生日期,但仍然没有运气,还是被占用。现在您还添加了大学里使用的学生号,仍然有“用户名已被占用”。这真的令人沮丧,不是吗? 但你有没有想过Geekbook通过搜索数百万用户名来检查用户名的可用性有多快。其实有很多方法可以完成这项工作。

线性搜索:不是一个好的选择!

二分搜索:按字母顺序存储所有用户名,存储在列表/数组中,在用户输入的用户名的时候与数组里面的用户名进行比较,搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。这种技术更好,更有前途,但它仍然需要多个步骤。

Bloom Filter是一个可以完成这项工作的一种数据结构。

要了解Bloom Filter,您必须知道什么是散列。哈希函数接收输入并输出固定长度的唯一标识符,该标识符用于识别输入信息。

什么是布隆过滤器?

Bloom Filter是一种节省空间的概率性质的数据结构,用于测试元素是否是集合的成员。例如,成员资格问题中检查用户名的可用性,其中该集合是所有已注册用户名的列表。在效率显著提升的情况下,付出的代价是它本质上是概率性的,这意味着可能存在一些错误的结果。也就意味着会出现误报情况,它可能会告诉我们已经使用了给定的用户名但实际上并非如此。

Bloom过滤器的有趣属性

与标准哈希表不同,固定大小的布隆过滤器可以表示具有任意大量元素的集合。

添加元素永远不会失败。但是,误差率随着元素的增加而稳定增加,直到滤波器中的所有位都设置为1,此时所有查询都会产生正确结果。

Bloom过滤器永远不会生成错误的否定结果,即告诉您实际存在的用户名不存在。

从过滤器中删除元素是不可能的,因为如果我们通过清除由k个散列函数生成的索引处的位来删除单个元素,则可能导致删除少数其他元素。示例 - 如果我们通过清除1,4和7处的位来删除“geeks”(在下面的给定示例中),我们可能最终也会删除“nerd”,因为索引4处的位变为0,并且布隆过滤器表明“nerd”没有出现。

使用Bloom过滤器

空的bloom过滤器是一个由m位组成的位数组,所有的位都设置为0,就像这样

我们需要k个哈希函数来计算给定输入的哈希值。当我们想在过滤器中添加一项时,设置下标为k的位数组的值为1,位值的计算是通过哈希函数h1(x)、h2(x)、hk(x)来计算的。假设我们想在过滤器中输入'geeks',我们使用3个哈希函数和一个长度为10的位数组,初始值都设置为0。首先,我们将计算散列如下:

h1(“geeks”) % 10 = 1
h2(“geeks”) % 10 = 4
h3(“geeks”) % 10 = 7

注意:这些输出是随机的,仅供参考。 现在我们将索引1,4和7的位设置为1。

 

再次我们想要输入“nerd”,同样我们将计算哈希值:

h1(“nerd”) % 10 = 3
h2(“nerd”) % 10 = 5
h3(“nerd”) % 10 = 4

将索引3,5和4处的位设置为1。

现在,如果我们想要检查过滤器中是否存在“geeks”。我们将以相反的顺序执行相同的过程。我们使用h1,h2和h3计算各自的哈希值,并检查位数组中是否所有这些索引都设置为1。如果所有位都是1,那么我们可以说可能存在 “geeks” 。如果这些指数中的任何一位为0,则绝对不存在 “geeks” 。

布隆过滤器中的误报

问题是为什么我们说可能存在”,为什么出现这种不确定性。让我们通过一个例子来理解这一点。假设我们要检查“cat”是否存在。我们将使用h1,h2和h3计算哈希值:

h1(“cat”) % 10 = 1
h2(“cat”) % 10 = 3
h3(“cat”) % 10 = 7

如果我们检查位数组,这些索引处的位设置为1,但我们知道“cat”从未添加到过滤器中。当我们添加“geeks”并且设置了三个位,我们添加了“nerd”,设置了索引3和5的位。

因此,因为计算索引处的位已经被某些其他项设置,所以布隆过滤器错误地声称“cat”存在并产生错误的结果。

我们可以通过控制Bloom过滤器的大小来控制获得误报的可能性。更多的空间意味着更少的误报。如果我们想要降低误报结果的概率,我们必须使用更多数量的散列函数和更大的位数组。这将增加存储的内容和增加检查成员资格的延迟时间。

误报概率:m为位数组的大小,k为散列函数的数量,n为要插入过滤器的预期元素的数量,则误报概率p可计算为:

 

散列函数的最佳数量:散列函数k的数量必须是正整数。如果m是位数组的大小,而n是要插入的元素数,则k可以计算为:

 

空间效率

我们可以将数据先存储在数组,列表,链表,哈希表等中,所有这些方法都需要存储内容本身,这样势必会占有很多内存,并且也不高效。例如,如果我们想在哈希表中存储“geeks”,我们必须将实际字符串“geeks”存储为键值对{some_key:“geeks”}。 Bloom过滤器根本不存储数据项。正如我们所看到的,它使用允许哈希冲突的位数组。

Hash函数的选择

布隆过滤器中使用的散列函数应该是独立且均匀分布的。它们应该尽可能快。例如murmur,FNV,Jenkins等。 生成散列是bloom过滤器中的主要操作。加密的哈希函数提供了稳定性和精度,但计算成本很高。随着散列函数k的增加,布隆过滤器变慢。虽然非加密哈希函数都不提供精度保证,但可以增加性能。

Python3中Bloom Filter类的基本实现。将其保存为bloomfilter.py

# Python 3 program to build Bloom Filter
# Install mmh3 and bitarray 3rd party module first
# pip install mmh3
# pip install bitarray
import math
import mmh3
from bitarray import bitarray

class BloomFilter(object):

    '''
    Class for Bloom filter, using murmur3 hash function
    '''

    def __init__(self, items_count,fp_prob):
       '''
       items_count : int
           Number of items expected to be stored in bloom filter
       fp_prob : float
           False Positive probability in decimal
       '''
       # False posible probability in decimal
       self.fp_prob = fp_prob

       # Size of bit array to use
       self.size = self.get_size(items_count,fp_prob)

       # number of hash functions to use
       self.hash_count = self.get_hash_count(self.size,items_count)

       # Bit array of given size
       self.bit_array = bitarray(self.size)

       # initialize all bits as 0
       self.bit_array.setall(0)

    def add(self, item):
       '''
       Add an item in the filter
       '''
       digests = []
       for i in range(self.hash_count):

           # create digest for given item.
           # i work as seed to mmh3.hash() function
           # With different seed, digest created is different
           digest = mmh3.hash(item,i) % self.size
           digests.append(digest)

           # set the bit True in bit_array
           self.bit_array[digest] = True

    def check(self, item):
       '''
       Check for existence of an item in filter
       '''
       for i in range(self.hash_count):
           digest = mmh3.hash(item,i) % self.size
           if self.bit_array[digest] == False:

              # if any of bit is False then,its not present
              # in filter
              # else there is probability that it exist
              return False
       return True

    @classmethod
    def get_size(self,n,p):
       '''
       Return the size of bit array(m) to used using
       following formula
       m = -(n * lg(p)) / (lg(2)^2)
       n : int
           number of items expected to be stored in filter
       p : float
           False Positive probability in decimal
       '''
       m = -(n * math.log(p))/(math.log(2)**2)
       return int(m)

    @classmethod
    def get_hash_count(self, m, n):
       '''
       Return the hash function(k) to be used using
       following formula
       k = (m/n) * lg(2)

       m : int
           size of bit array
       n : int
           number of items expected to be stored in filter
       '''
       k = (m/n) * math.log(2)
       return int(k)

让我们测试布隆过滤器。创建一个文件名为bloom_test.py

from bloomfilter import BloomFilter
from random import shuffle

n = 20 # no of items to add
p = 0.05 # false positive probability

bloomf = BloomFilter(n,p)
print("Size of bit array:{}".format(bloomf.size))
print("False positive Probability:{}".format(bloomf.fp_prob))
print("Number of hash functions:{}".format(bloomf.hash_count))

# words to be added
word_present = ['abound','abounds','abundance','abundant','accessable',
              'bloom','blossom','bolster','bonny','bonus','bonuses',
              'coherent','cohesive','colorful','comely','comfort',
              'gems','generosity','generous','generously','genial']

# word not added
word_absent = ['bluff','cheater','hate','war','humanity',
           'racism','hurt','nuke','gloomy','facebook',
           'geeksforgeeks','twitter']

for item in word_present:
    bloomf.add(item)

shuffle(word_present)
shuffle(word_absent)

test_words = word_present[:10] + word_absent
shuffle(test_words)
for word in test_words:
    if bloomf.check(word):
       if word in word_absent:
           print("'{}' is a false positive!".format(word))
       else:
           print("'{}' is probably present!".format(word))
    else:
       print("'{}' is definitely not present!".format(word))

输出:

Size of bit array:124
False positive Probability:0.05
Number of hash functions:4
'war' is definitely not present!
'gloomy' is definitely not present!
'humanity' is definitely not present!
'abundant' is probably present!
'bloom' is probably present!
'coherent' is probably present!
'cohesive' is probably present!
'bluff' is definitely not present!
'bolster' is probably present!
'hate' is definitely not present!
'racism' is definitely not present!
'bonus' is probably present!
'abounds' is probably present!
'genial' is probably present!
'geeksforgeeks' is definitely not present!
'nuke' is definitely not present!
'hurt' is definitely not present!
'twitter' is a false positive!
'cheater' is definitely not present!
'generosity' is probably present!
'facebook' is definitely not present!
'abundance' is probably present!

Bloom过滤器的应用

媒体使用Bloom过滤器通过过滤用户已经看过的帖子来向用户推荐新帖子。

Quora在后端实现了一个共享的Bloom过滤器,用于过滤人们之前看过的问答。

Google Chrome网络浏览器曾使用Bloom过滤器来识别恶意网址。

参考

  https://en.wikipedia.org/wiki/Bloom_filter

  https://blog.medium.com/what-are-bloom-filters-1ec2a50c68ff

  https://www.quora.com/What-are-the-best-applications-of-Bloom-filters

 

 

 

#标签:布隆过滤器