在爬虫中，我们经常遇到这样的问题。一是希望抓取过的URL不再重复抓取，节省资源；二是希望下载过的数据不再重复下载（一般情况下保证了第一条可以差不多满足第二条）。
爬虫去重一般是对URL去重，访问过的页面不在访问去重可以避免网络之间的环路，并且增加爬取效率。
今天我们介绍几个去重策略
一、像十万以下URL的抓取可以简单的用set来实现去重，可以在O(1)的时间内查询到一个URL是否存在于set中。
缺点：占用内存大，比如有1亿条URL，占用的内存是：1000000000*2byte*50字符/1024/1024/1024 = 9G(假设字符使用的是unicode编码，每一个字符占2字节，每一个URL有50个字符)。
二、如果是百万或者千万量级的话，考虑到性能，我们应该使用基于hash的set实现去重。哈希使得我们并不需要对比超长的URL以及params，只需要对比其哈希值。
缺点：如果检测结果为是，该元素不一定在集合中；但如果检测结果为否，该元素一定不在集合中。这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况，可见 Bloom filter 是牺牲了正确率和时间以节省空间。
三、URL经过MD5或SHA-1等哈希算法生成摘要，再存到HashSet中。MD5处理后摘要长度128位，SHA-1摘要长度160位，这样占用内存比直接存小很多。（scrapy使用的就是类似的方法）
四、使用bitmap方法，将访问过的URL通过hash函数映射到某一位上，这种方法可以大大压缩URL的存储空间，但是缺点是，会有很多的映射冲突，即多个不同的URL映射到一个位上。
五、如果数据量上亿或者几十亿时使用 Bloom Filter（中文：布隆过滤器）算法。布隆过滤器原理是这样的，一个URL过来，通过M个特别的哈希函数对其进行运算，映射成一个M维位数组的M个维度。新的URL诞生时，进行同样操作并逐个与set中的位数组做“与”运算，若结果改变则说明URL一定没有被抓取过，若结果一致则说明URL有一定概率被抓取过因为有一定的低错误率。布隆过滤器的插入和查询效率都是O(M)，远低于其他一般策略。使用Bloom Filter方法对bitmap进行改进，多重哈希函数降低冲突，是对（四：bitmap方法）的改进，既能降低冲突，又能大大压缩内存
六、像MySQL这种关系型数据库，我们可以设置主键或者唯一索引来保证数据的唯一性。查询导致效率低，不推荐。
七、像MongoDB这种Schema free的非关系型数据库，我们可以用先检索再插入或者是upsert的方式保证数据的唯一性。（相对于MySQL数据库的性能有了很大的提升）
八、缓存数据库去重： 如Redis数据库其高速的读写，使用其中的Set数据类型，并可将内存中的数据持久化，应用广泛，推荐。
比较好的方式为：URL经过MD5或SHA-1等哈希算法生成摘要，再存到 Redis的HashSet中
欢迎留言纠错补充，QQ：2223136131
网友评论