爬虫去重方案

去重一般是对URL去重，访问过的页面不在访问，但是也有例外，比如一些网站有用户评论，内容是不断变化的，若爬取评论，则就不能以URL作为去重标准，但本质上都可以看做针对字符串的去重。
去重可以避免网络之间的环路，并且增加爬取效率。常见有以下几种方式：

• 关系数据库去重：查询导致效率低，不推荐。
• 缓存数据库去重： 如Redis，使用其中的Set数据类型，并可将内存中的数据持久化，应用广泛，推荐。
• 内存去重：最大制约是内存大小和掉电易失。
  1. URL直接存到HashSet中：太消耗内存。
  2. URL经过MD5或SHA-1等哈希算法生成摘要，再存到HashSet中。MD5处理后摘要长度128位，SHA-1摘要长度160位，这样占用内存比直接存小很多。
  3. 采用Bit-Map方法，建立一个BitSet，每个URL经过一个哈希函数映射到一位，消耗内存最少，但是发生冲突概率太高，易误判。

综上，比较好的方式为：内存去重第二种方式+缓存数据库。基本可以满足大多数中型爬虫需要。数据量上亿或者几十亿时，就需要用BloomFilter算法了。

BloomFilter算法

1. 创建一个m位的位数组，所有位初始化为0。
2. 选择k个不同的哈希函数，记第i个哈希函数对字符串str哈希的结果为h(i,str),h(i,str)范围是0到m-1。
3. 字符串经过哈希函数映射为k个介于0到m-1的数字，将m位数组中下标为这k个数的位置1。这样便将字符串映射到位数组中的k个二进制位了。
4. 若判断字符串是否存在，只需将新的字符串进行哈希，检查每一个映射对应的m位位数组的值是否为1，若任何1位不为1，则一定没被记录过。若一个字符串对应的任何一位全为1，但不能说明这个字符串肯定被记录过，因为有一定的低错误率。因此布隆过滤器适用于能容忍低错误率的场合。
   python-bloomfilter开源库