神刀安全网

爬虫课堂(十四)|URL的去重方法

所谓的URL去重,就是爬虫将重复抓取的URL去除,避免多次抓取同一网页。爬虫一般会将待抓取的URL放在一个队列中,从抓取后的网页中提取到新的URL,在他们被放入队列之前,首先要确定这些新的URL没有被抓取过,如果之前已经抓取过了,就不再放入队列。

爬虫课堂(十四)|URL的去重方法

URL的去重方法有很多种,从次到优依次可以分为以下5种:

1、将URL保存到数据库进行去重(假设单个URL的平均长度是100 byte)。

2、将URL放到HashSet中去重(一亿条占用10G内存)。

3、将URL经过MD5之后保存到HashSet(MD5的结果是128 bit也就是16 byte的长度,一亿条占用1.6G的内存,Scrapy采用的就是类似方法)。

4、使用Bitmap或Bloomfilter方法去重(URL经过hash后映射到bit的每一个位上,一亿URL占用约12M,问题是存在冲突)。

去重方法介绍

一、将URL保存到数据库进行去重

为了尽快把整个爬虫搭建起来,最开始的URL去重采用方案是直接利用数据库的唯一约束进行去重,这是最省时的做法,所有人都能想得到和做到。

二、将URL放到HashSet中去重

在数据库中去重,每次比较都有一次请求数据库的过程,这里对数据库的性能消耗是很大的。于是可以使用将URL放到内存中的HashSet中去重,HashSet中放置的就是URL的字符串,任何一个新的URL首先在HashSet中进行查找,如果HashSet中没有,就将新的URL插入HashSet,并将URL放入待抓取队列。 

这个方案的好处是它的去重效果精确,不会漏过一个重复的URL。它的缺点是,随着数据的增加会出现Out Of Memory。

假设单个URL的平均长度是100 byte,那么一亿条数据占用10G内存,大部分的电脑内存在4G和8G,那么留给JVM的内存就更少啦,那么出现内存泄漏是迟早的事。

3、将URL经过MD5之后保存到HashSet

迟早到底有多早呢?也许是一个月,那么我们可以把这一个月扩展到半年。

这里的处理方式就是HashSet中不存储原始的URL,而是将URL压缩后再放进去。压缩的方式有很大,用MD5对URL做编码是比较省时的一种方式。 

MD5的结果是128 bit也就是16 byte的长度,相比于之间估计的URL平均长度100byte已经缩小了6倍多,一亿条数据占用1.6G的内存,Scrapy采用的就是类似方法。

当然,不管使用那种压缩算法,随着URL越来越多,终有一天还是会Out Of Memory。所以,这个方案不解决本质问题。 

MD5另外一个问题是,有可能两个相同的URL被映射成同一个MD5值,这样的话,它们中有一个就永远不会被抓取了。

4、使用Bitmap方法去重

使用Bitmap方法去重的原理是把URL经过hash后映射到bit的每一个位上,一亿URL占用约12M,主要缺点是去重没那么精准,存在冲突。

总结

关于1、2、3我是有实践过,4的话没有实践,同时为了解决内存的问题,现在也可以使NoSQL的方案去解决,具体的没有操作过就不多讲啦。

不过我们马上就要去实践啦,回头我把实践的结果再同步到这篇文章中来,欢迎关注。

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 爬虫课堂(十四)|URL的去重方法

分享到:更多 ()

评论 抢沙发