- +在此添加单个AI新笔记
爬虫 - 布隆过滤器 - 高效检测URL是否已抓取
布隆过滤器是一种高效的空间数据结构，用于快速检测元素是否存在于集合中，尤其适用于爬虫中URL去重。其核心优势是低内存占用和快速查询，但存在一定误判率（假阳性，绝不会假阴性）。
工作原理
- 位数组：使用二进制向量（bit array）存储数据。
- 哈希函数：通过多个哈希函数将元素映射到不同的位下标。
- 操作流程：
- 添加元素：将每个哈希对应的位设为1。
- 检查元素：若所有哈希位均为1，则可能已存在；否则不存在。
示例代码（Python）
使用 mmh3 哈希库和 bitarray 实现简单布隆过滤器：
import mmh3from bitarray import bitarrayclass BloomFilter:def __init__(self, size, hash_count):self.size = sizeself.hash_count = hash_countself.bit_array = bitarray(size)self.bit_array.setall(0)def add(self, url):"""添加URL到过滤器"""for seed in range(self.hash_count):index = mmh3.hash(url, seed) % self.sizeself.bit_array[index] = 1def exists(self, url):"""检查URL是否可能已存在"""for seed in range(self.hash_count):index = mmh3.hash(url, seed) % self.sizeif self.bit_array[index] == 0:return Falsereturn True
参数设置与误判率
公式：
- 位数组大小（m）：
m = -(n * ln(p)) / (ln2)^2 - 哈希函数数（k）：
k = (m/n) * ln2n：预期元素数量，p：允许的误判率。
- 位数组大小（m）：
示例计算：
若预计处理1,000,000个URL，误判率设为1% (0.01)：m ≈ 9,585,059 bits（约1.14MB）k ≈ 7个哈希函数。
使用示例
# 初始化：1百万容量，7个哈希函数，误判率约1%bf = BloomFilter(9585059, 7)url1 = "https://example.com"url2 = "https://new-url.com"bf.add(url1)print(bf.exists(url1)) # 输出 True（准确判断）print(bf.exists(url2)) # 输出 False（或小概率True，误判）
优缺点
- 优点：
- 内存占用极低（远低于哈希表）。
- 插入和查询时间复杂度均为
O(k)（k为哈希函数数）。
- 缺点：
- 存在误判率，需根据场景调整参数。
- 不支持删除操作（可用计数布隆过滤器改进）。
实际应用
- 分布式爬虫：结合Redis等工具实现分布式布隆过滤器。
- 预处理阶段：快速过滤已爬取的URL，减少重复请求。
通过合理设计参数，布隆过滤器能够以极小的内存代价，高效处理海量URL去重问题。