过滤豆瓣租房小组中介贴之 python 实现布隆过滤器（三）

Pythoner

其实这篇文章跟过滤中介贴没什么关系，只是在爬豆瓣小组的时候遇到的一点思考，我们知道，其实爬虫就是循环的爬取网站的 url，但是怎么判断爬取的 url 是否重复呢，最简单的，维护一个列表，每次循环查找，很明显效率很低。进阶的，采用哈希表，每次查询都是 O(1), 看上去不错。不过如果一旦 url 大到一定程度时，单台机器的内存肯定吃不消，这个时候分布式方案就呼之欲出，变得越来越复杂。那么能不能在牺牲一点点精确性的前提下，有简单的方案呢，答案是肯定的。这就是 布隆过滤器 。

布隆过滤器的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0 ，则被检元素一定不在；如果都是 1 ，则被检元素很可能在。（引用自维基百科）。布隆过滤器可以看成是 bitmap 的扩展，它的优点是空间和时间复杂度都是常数，缺点是有一定的误算率。

具体还可以参考：布隆过滤器 -- 空间效率很高的数据结构

维基百科-布隆过滤器

我们写爬虫很多时候会使用 redis 作为各种队列来提高性能。同样，这次我们将用 redis 和 python 结合起来写个布隆过滤器。

首先需要实现一个求 hash 的函数，这里采用 murmurhash 算法。然后算出 k 个点的位置（这里是 7 个点）。

BIT_SIZE = 5000000
SEEDS = [50, 51, 52, 53, 54, 55, 56]
        return [mmh3.hash(content, seed) % BIT_SIZE for seed in SEEDS]

接下来就是 insert 和 is_contains 方法

def insert(self, content):
    locs = self.cal_offsets(content)
    for loc in locs:
        self.db.setbit(self.key, loc, 1)