位图-布隆过滤器

布隆过滤器(Bloom Filter) 是1970年由布隆提出的。它实际上是一个很长的二进制向量和多个映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难


假设要爬取10亿个网站,现在要判断某个url是否已经爬取过了,如果使用散列表,那么需要存储大量的数据,使用布隆过滤器就非常省空间

布隆过滤器来记录已经爬取过的网页链接,那我们可以用一个 10 倍大小的位图来存储,也就是 100 亿个二进制位,换算成字节,那就是大约 1.2GB。之前我们用散列表判重,需要至少 100GB 的空间。相比来讲,布隆过滤器在存储空间的消耗上,降低了非常多

新增:

新增一个url(www.daileinote.com),利用 k 个哈希函数(假设k = 4,h1 h2 h3 h4)对其进行哈希计算并对 100亿 取余,假设计算出来为 1 2000 34 56,那么我们分别把 第1位 第2000位 第34位 第56位 置1

新增另外一个url(www.baidu.com),我们同样利用 k 个哈希函数对其进行哈希计算并对 100亿 取余,假设计算出来为 33 44 55 777,那么我们分别把 第33位 第44位 第55位 第777位 置1

查询:

假设现在得到一个url(www.daileinote.com),先判断它是否已经被访问过,只需要重复上述步骤,利用 k 个哈希函数对其进行哈希计算并对 100亿 取余,得到 1 2000 34 56,然后分别判断 第1位 第2000位 第34位 第56位 是否全部为1,如果是,代表该url已经访问过了


从上面的步骤我们可以看出,布隆过滤器这种方法难免会遇到冲突现象,即多个url通过k个哈希函数,计算出来的结果是一样的,我们能做的只能是减少冲突现象的发生概率,所以布隆过滤器只适合对冲突误判容忍性比较高的场景

爬虫就是,就算偶尔误判了一个url已经访问过了,也没什么大不了的,因为少几个url也没事

非常重要的特点:判定存在的数据,有可能并不存在,但是对于判定不存在的数据,那肯定就不存在,所以对于一些严格的场景,布隆过滤器可以用来辅助,即校验数据是否不存在


合理选择

这里假设 k 为哈希函数个数,m 为二进制位数(即空间大小),n 为需要存储的数据数(即实际数据大小)

假设k,n不变,那么 m 越大,冲突误报概率肯定越低,但是m太大,空间占用就很多

一般情况下空间利用率为50%差不多了

空间利用率 = k * n / m

下面是一张参考表,里面的值为误报率




上一篇: 两个数相除(位移)
下一篇: 返回不重复的整数
作者邮箱: 203328517@qq.com