大数据算法——布隆过滤器

理

在我之前的理解当中，如果想要判断某个元素在不在集合当中，经典的结构应该是平衡树和hash table。但是无论是哪一种方法，都逃不开一点，都需要存储原值。

比如在爬虫场景当中，我们需要记录下之前爬过的网站。我们要将之前的网址全部都存储在容器里，然后在遇到新网站的时候去判断是否已经爬过了。在这个问题当中，我们并不关心之前爬过的网站有哪些，我们只关心现在的网站有没有在之前出现过。也就是说之前出现过什么不重要，现在的有没有出现过才重要。

我们利用平衡树或者是Trie或者是AC自动机等数据结构和算法可以实现高效的查找，但是都离不开存储下所有的字符串。想象一下，一个网址大概上百个字符，大约0.1KB，如果是一亿个网址，就需要10GB了，如果是一百亿一千亿呢？显然这么大的规模就很麻烦了，今天要介绍的布隆过滤器就可以解决这个问题，而且不需要存储下原值，这是一个非常巧妙的做法，让我们一起来看下它的原理。

布隆过滤器本身的结构非常简单，就是一个一维的bool型的数组，也就是说每一位只有0或者1，是一个bit，这个数组的长度是m。对于每个新增的项，我们使用K种不同的hash算法对它计算hash值。所以我们可以得到K个hash值，我们用hash值对m取模，假设是x。刚开始的时候数组内全部都是0，我们把所有x对应的位置标记为1。

举个例子，假设我们一开始m是10，K是3。我们遇到第一个插入的值是”线性代数“，我们对它hash之后得到1，3，5，那么我们将对应的位置标记成1.

然后我们又遇到了一个值是”高等数学“，hash之后得到1，8，9，我们还是将对应位置赋值成1，会发现1这个位置对应的值已经是1了，我们忽略就好。

如果这个时候我们想要判断”概率统计”有没有出现过，怎么办？很简单，我们对“概率统计”再计算hash值。假设得到1，4，5，我们去遍历一下对应的位置，发现4这个位置是0，说明之前没有添加过“概率统计”，显然“概率统计”没有出现过。

但是如果“概率统计”hash之后的结果是1，3，8呢？我们判断它出现过就错了，答案很简单，因为虽然1，3，8这个hash组合之前没有出现过，但是对应的位置都在其他元素中出现过了，这样就出现误差了。所以我们可以知道，布隆过滤器对于不存在的判断是准确的，但是对于存在的判断是有可能有错误的。

代码

布隆过滤器的原理很简单，明白了之后，我们很容易写出代码：

# 插入元素
def BloomFilter(filter, value, hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        filter[idx] = True
    return filter
    
# 判断元素
def MemberInFilter(filter, value, hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        if not filter[idx]:
            return False
    return True

错误率计算

之前的例子当中应该展示得很明白了，布隆过滤器虽然好用，但是会存在bad case，也就是判断错误的情况。那么，这种错误判断发生的概率有多大呢？

这个概率的计算也不难：由于数组长度是mm，所以插入一个bit它被置为1的概率是1m1m，插入一个元素需要插入k个hash值，所以插入一个元素，某一位没有被置为1的概率是(1−1m)k(1−1m)k。插入n个元素之后，某一位依旧为0的概率是(1−1m)nk(1−1m)nk，它变成1的概率是1−(1−1m)nk1−(1−1m)nk。

如果在某次判断当中，有一个没有出现过的元素被认为已经在集合当中了，那么也就是说它hash得到的位置均已经在之前被置为1了

本站声明：
1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。