精华内容
下载资源
问答
  • 爬虫之URL去重

    千次阅读 2019-04-07 10:04:08
    URL去重 我们在协爬虫时为什么需要进行URL去重? 在爬虫启动工作的过程中,我们不希望同一个url地址被多次请求,因为重复请求不仅会浪费CPU,还会降低爬虫的效率,加大对方服务器的压力。而想要控制这种重复请求的...

    URL去重

    我们在写爬虫时为什么需要进行URL去重?

    1. 在爬虫启动工作的过程中,我们不希望同一个url地址被多次请求,因为重复请求不仅会浪费CPU,还会降低爬虫的效率,加大对方服务器的压力。而想要控制这种重复请求的问题,就要考虑请求所依据的url,只要能够控制待下载的URL不重复,基本可以解决同一个网页重复请求的问题。
    2. 对于已经抓取过的url,进行持久化,并且在启动的时候加载进入去重队列,是一个比较强的需求。 它主要应对爬虫故障重跑,不需要重新请求所有链接

    URL去重及策略简介

    从表面上看,url去重策略就是消除url重复的方法,常见的url去重策略有五种,如下:

    # 1.将访问过的ur保存到数据库中
    # 2.将访问过的ur保存到set(集合)中,只需要o(1)的代价就可以查询url
    #       10000000*2byte*50个字符/1024/1024/1024=9G
    # 3.url经过md5等方法哈希后保存到set(或者Redis中)中
    # 4. bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突
    
    方式一:将访问过的ur保存到数据库中

    实现起来最简单,但效率最低。
    其核心思想是,把页面上爬取到的每个url存储到数据库,为了避免重复,每次存储前都要遍历查询数据库中当前url是否存在(即是否已经爬取过了),若存在,则不保存,否则,保存当前url,继续保存下一条,直至结束。

    方式二:将访问过的ur保存到set内存中

    实现简单,原理和方式一类似,使用这种方式存取方便,基本不用查询,但是如果url过多,则会占用极大的内存,浪费空间。

    # 简单计算:假设有1亿条url,每个url平均长度为50个字符,python里unicode编码,每个字符16位,占2
    # 个字节(byte)
    # 计算式:10^8 x 50个字符 x 2个byte / 1024 / 1024 / 1024 = 9G
    #                                    B      M      G
    如果是2亿个url,那么占用内存将达18G,也不是特别方便,适合小型爬虫。
    

    方式三.url经过md5等方法哈希后保存到set(或者Redis中)中(实现方法如下)

    简单计算:一个url经MD5转换,变成一个128bit(位)的字符串,占16byte(字节),方法二中一个url保守估
    计占50个字符 x 2 = 100byte(字节),
    计算式: 这样一比较,MD5的空间节省率为:(100-16)/100 = 84%(相比于方法二)
    (Scrapy框架url去重就是采用的类似方法)
    
        def request_fingerprint(self, url):
            """Returns a fingerprint for a given url
            Parameters
            ----------
            url : 待请求的url地址
            Returns: str
            """
            #根据url生成指纹
            print('未加密之前:',url)
            md5_obj = hashlib.md5()
            # 进行MD5加密前必须 encode(编码),python里默认是unicode编码,必须转换成utf-8
            # 否则报错:TypeError: Unicode-objects must be encoded before hashing
            md5_obj.update(url.encode(encoding='utf-8'))
            md5_url = md5_obj.hexdigest()
            print('MD5加密后:',md5_url)
            return md5_url
    
    方式四: bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突
    原理概述

    布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个
    点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点
    有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

    在这里插入图片描述

    优缺点
    • 布隆过滤器可以用于检索一个元素是否在一个集合中。
    • 优点是空间效率和查询时间都远远超过一般的算法。
    • 缺点是有一定的误识别率(随着数据的变大,误识概率变大)和不允许删除。
    # 设置散列函数的个数
    BLOOMFILTER_HASH_NUMBER = 6
    # 布隆过滤器设置bit参数,默认30,占用128M空间,去重量在1亿左右
    此参数决定了位数组的位数,如果BLOOMFILTER_BIT为30,则位数组
    位2的30次方,这将暂用Redis 128MB的存储空间,url去重数量在1亿左右,
    如果爬取的量在10亿,20亿或则更高,则需要将此参数调高
    BLOOMFILTER_BIT = 30
    
    class HashMap(object):
        def __init__(self, m, seed):
            self.m = m
            self.seed = seed
        
        def hash(self, value):
            """
            Hash Algorithm
            :param value: Value
            :return: Hash Value
            """
            ret = 0
            for i in range(len(value)):
                ret += self.seed * ret + ord(value[i])
            return (self.m - 1) & ret
    
    
    class BloomFilter(object):
        def __init__(self, server, key, bit=BLOOMFILTER_BIT, hash_number=BLOOMFILTER_HASH_NUMBER):
            """
            Initialize BloomFilter
            :param server: Redis Server
            :param key: BloomFilter Key
            :param bit: m = 2 ^ bit
            :param hash_number: the number of hash function
            """
            # default to 1 << 30 = 10,7374,1824 = 2^30 = 128MB, max filter 2^30/hash_number = 1,7895,6970 fingerprints
            self.m = 1 << bit
            self.seeds = range(hash_number)
            self.server = server
            self.key = key
            self.maps = [HashMap(self.m, seed) for seed in self.seeds]
        
        def exists(self, value):
            """
            if value exists
            :param value:
            :return:
            """
            if not value:
                return False
            exist = True
            for map in self.maps:
                offset = map.hash(value)
                exist = exist & self.server.getbit(self.key, offset)
            return exist == 1
        
        def insert(self, value):
            """
            add value to bloom
            :param value:
            :return:
            """
            for f in self.maps:
                offset = f.hash(value)
                self.server.setbit(self.key, offset, 1)
    
    单独使用如下
    	client = redis.StrictRedis(host='118.24.255.219',port=6380)
        bl = BloomFilter(client,'bl:url')
        url = 'http://www.wanfangdata.com.cn/details/detaype=conference&id=7363410'
        bl.insert(url)
        result = bl.exists(url)
        print(result)
        url1 = 'http://www.wanfangdata.com.cn/details/detaype=conference&id=73634101'
        result = bl.exists(url1)
        print(result)
    
    为了方便使用我们还可以和scrpay-redis对接,这里不需要重复造轮子,我们可以直接使用pip3 来安装ScrapyRedisBloomFilter:
    • Installation

    pip3 install scrapy-redis-bloomfilter

    • Usage
    # Ensure use this Scheduler(使用自定义的调度器组件)
    SCHEDULER = "scrapy_redis_bloomfilter.scheduler.Scheduler"
    
    # Ensure all spiders share same duplicates filter through redis(使用自定义的去重组件)
    DUPEFILTER_CLASS = "scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter"
    
    # Redis URL(设置去重指纹需要保存的redis数据库信息)
    REDIS_URL = 'redis://:foobared@localhost:6379'
    
    # Number of Hash Functions to use, defaults to 6
    #设置散列函数的个数
    BLOOMFILTER_HASH_NUMBER = 6
    
    # Redis Memory Bit of Bloomfilter Usage, 30 means 2^30 = 128MB, defaults to 30
    # 布隆过滤器设置bit参数,默认30,占用128M空间,去重量在1亿左右
    此参数决定了位数组的位数,如果BLOOMFILTER_BIT为30,则位数组
    位2的30次方,这将暂用Redis 128MB的存储空间,url去重数量在1亿左右,
    如果爬取的量在10亿,20亿或则更高,则需要将此参数调高
    BLOOMFILTER_BIT = 30
    
    # Persist
    #是否支持断点爬取
    SCHEDULER_PERSIST = True
    

    其实ScrapyRedisBloomFilter就是在scrapy-redis的基础上将DUPEFILTER去重组件中的去重部分代码判断修改了,如下图所示:
    在这里插入图片描述
    在这里插入图片描述
    学习了本小结之后,再也不用担心url的去重了,感谢阅读。

    展开全文
  • URL去重的几种方法

    千次阅读 2018-07-06 16:08:26
    在爬虫启动工作的过程中,我们不希望同一个网页被多次下载,因为... 非常容易想到,在搜索引擎系统中建立一个全局的专门用来检测,是否某一个URL对应的网页文件曾经被下载过的URL存储库,这就是方案。 接着要考...
       在爬虫启动工作的过程中,我们不希望同一个网页被多次下载,因为重复下载不仅会浪费CPU机时,还会为搜索引擎系统增加负荷。而想要控制这种重复性下载问题,就要考虑下载所依据的超链接,只要能够控制待下载的URL不重复,基本可以解决同一个网页重复下载的问题。 
    
       非常容易想到,在搜索引擎系统中建立一个全局的专门用来检测,是否某一个URL对应的网页文件曾经被下载过的URL存储库,这就是方案。 
    接着要考虑的就是如何能够更加高效地让爬虫工作,确切地说,让去重工作更加高效。如果实现去重,一定是建立一个URL存储库,并且已经下载完成的URL在进行检测时候,要加载到内存中,在内存中进行检测一定会比直接从磁盘上读取速度快很多。 
    我们先从最简单的情况说起,然后逐步优化,最终得到一个非常不错的解决方案。 


    第一,基于磁盘的顺序存储。 
        这里,就是指把每个已经下载过的URL进行顺序存储。你可以把全部已经下载完成的URL存放到磁盘记事本文件中。每次有一个爬虫线程得到一个任务URL开始下载之前,通过到磁盘上的该文件中检索,如果没有出现过,则将这个新的URL写入记事本的最后一行,否则就放弃该URL的下载。 
        这种方式几乎没有人考虑使用了,但是这种检查的思想是非常直观的。试想,如果已经下载了100亿网页,那么对应着100亿个链接,也就是这个检查URL是否重复的记事本文件就要存储这100亿URL,况且,很多URL字符串的长度也不小,占用存储空间不说,查找效率超级低下,这种方案肯定放弃。


    第二,基于Hash算法的存储。 
        对每一个给定的URL,都是用一个已经建立好的Hash函数,映射到某个物理地址上。当需要进行检测URL是否重复的时候,只需要将这个URL进行Hash映射,如果得到的地址已经存在,说明已经被下载过,放弃下载,否则,将该URL及其Hash地址作为键值对存放到Hash表中。 
        这样,URL去重存储库就是要维护一个Hash表,如果Hash函数设计的不好,在进行映射的时候,发生碰撞的几率很大,则再进行碰撞的处理也非常复杂。而且,这里使用的是URL作为键,URL字符串也占用了很大的存储空间。
        为了尽快把整个爬虫搭建起来,最开始的URL去重采用方案是一个内存中的HashSet,这是最直观的方法,所有人都能想得到。HashSet中放置的就是URL的字符串,任何一个新的URL首先在HashSet中进行查找,如果HashSet中没有,就将新的URL插入HashSet,并将URL放入待抓取队列。


    优势:去重效果精确,不会漏过一个重复的URL。
    劣势:Out Of Memory。因为随着抓取网页的增加,HashSet会一直无限制的增长。


    另外,网络中的很多URL其实是很长的,有大量的URL长度达到上百个字符。
       简单估算一下,假设单个URL的平均长度是100 byte(我觉着这已经非常保守了),那么抓取1000万的URL就需要:
        100 byte * 10 000 000 = 1 GB
    而1000万URL在整个互联网中实在是沧海一粟。可以了解,需要多大的内存才能装下所有URL的HashSet。


    第三,基于MD5压缩映射的存储。 
        MD5算法是一种加密算法,同时它也是基于Hash的算法。这样就可以对URL字符串进行压缩,得到一个压缩字符串,同时可以直接得到一个Hash地址。另外,MD5算法能够将任何字符串压缩为128位整数,并映射为物理地址,而且MD5进行Hash映射碰撞的几率非常小,这点非常好。从另一个方面来说,非常少的碰撞,对于搜索引擎的爬虫是可以容忍的。况且,在爬虫进行检测的过程中,可以通过记录日志来保存在进行MD5时发生碰撞的URL,通过单独对该URL进行处理也是可行的。
        貌似有不少paper中讨论过如何对URL进行压缩,包括新浪微博中的短URL其实也是个不错的方案,为了偷懒,我直接用MD5对URL做编码。
        MD5的结果是128 bit也就是16 byte的长度。相比于之间估计的URL平均长度100byte已经缩小了好几倍,可以多撑好多天了。
        当然,哪怕找个一个可以压缩到极致的算法,随着URL越来越多,终有一天会Out Of Memory。所以,这个方案不解决本质问题。


       在Java中有一个Map类非常好,你可以将压缩后的URL串作为Key,而将Boolean作为Value进行存储,然后将工作中的Map在爬虫停止工作后序列化到本地磁盘上;当下一次启动新的爬虫任务的时候,再将这个Map反序列化到内存中,供爬虫进行URL去重检测。 


    第四,基于嵌入式Berkeley DB的存储。 


       Berkeley DB的特点就是只存储键值对类型数据,这和URL去重有很大关系。去重,可以考虑对某个键,存在一个值,这个值就是那个键的状态。 


       使用了Berkeley DB,你就不需要考虑进行磁盘IO操作的性能损失了,这个数据库在设计的时候很好地考虑了这些问题,并且该数据库支持高并发,支持记录的顺序存储和随机存储,是一个不错的选择。 


       URL去重存储库使用Berkeley DB,压缩后的URL字符串作为Key,或者直接使用压缩后的URL字节数组作为Key,对于Value可以使用Boolean,一个字节,或者使用字节数组,实际Value只是一个状态标识,减少Value存储占用存储空间。 
       我终于明白我所需要的其实是一个可以放在disk上的去重方案,这样,内存溢出将永远成不了可能。很早就知道有BerkeleyDB这么一个东西,但第一次真正了解还是在Amazon的Dynamo那篇论文中提到过采用了BerkeleyDB作为单机上的底层存储。当时觉着这东西真另类,原来还有叫做“DB”的东西却不支持SQL。那时候还没有NOSQL这词,把这样的东西叫做non-relational database。
    BerkeleyDB是一个key-value database,简单的说,就是一个在disk上的hash表,这也是为什么它可以被用来做URL去重的原因。它另外一个另类的地方是,它是和程序运行在同一个进程空间中的,而不像一般的db,是做为单独的程序运行。
    这里附上Heritrix中使用BerkeleyDB做URL去重的代码,一探究竟:(代码位于Heritrix源代码的org.archive.crawler.util.BdbUriUniqFilter)
       有一堆做初始化和配置的函数就直接忽略了,真正相关的函数就只有两个:
       [java] view plaincopy 
    /** 
     * Create fingerprint. 
     * Pubic access so test code can access createKey. 
     * @param uri URI to fingerprint. 
     * @return Fingerprint of passed <code>url</code>. 
     */  
    public static long createKey(CharSequence uri) {  
        String url = uri.toString();  
        int index = url.indexOf(COLON_SLASH_SLASH);  
        if (index > 0) {  
            index = url.indexOf('/', index + COLON_SLASH_SLASH.length());  
        }  
        CharSequence hostPlusScheme = (index == -1)? url: url.subSequence(0, index);  
        long tmp = FPGenerator.std24.fp(hostPlusScheme);  
        return tmp | (FPGenerator.std40.fp(url) >>> 24);  
    }  




    [java] view plaincopy 
        /** 
         * value: only 1 byte 
         */  
        private static DatabaseEntry ZERO_LENGTH_ENTRY = new DatabaseEntry(  
                new byte[0]);  


        protected boolean setAdd(CharSequence uri) {  
            DatabaseEntry key = new DatabaseEntry();  
            LongBinding.longToEntry(createKey(uri), key);  
            long started = 0;  


            OperationStatus status = null;  
            try {  
                if (logger.isLoggable(Level.INFO)) {  
                    started = System.currentTimeMillis();  
                }  
                status = alreadySeen.putNoOverwrite(null, key, ZERO_LENGTH_ENTRY);  
                if (logger.isLoggable(Level.INFO)) {  
                    aggregatedLookupTime +=  
                        (System.currentTimeMillis() - started);  
                }  
            } catch (DatabaseException e) {  
                logger.severe(e.getMessage());  
            }  
            if (status == OperationStatus.SUCCESS) {  
                count++;  
                if (logger.isLoggable(Level.INFO)) {  
                    final int logAt = 10000;  
                    if (count > 0 && ((count % logAt) == 0)) {  
                        logger.info("Average lookup " +  
                            (aggregatedLookupTime / logAt) + "ms.");  
                        aggregatedLookupTime = 0;  
                    }  
                }  
            }  
            if(status == OperationStatus.KEYEXIST) {  
                return false; // not added  
            } else {  
                return true;  
            }  
        }  
    简单解释一下:


    第一个函数createKey是在做URL的压缩,它将任意长度的URL转换成一个long型的值。long型的取值范围有2^64,因此两个URL映射成同一个long型值的概率应该挺低的。但我也没太细看这个函数,所以它的效果到底如何不确定。


    第二个函数setAdd就是将被压缩的URL写入到BerkeleyDB。之前说过,BerkeleyDB是一个key-value database,它的每条记录都包括了一个key和一个value。但是在URL去重中,value不重要(比如我们之前内存中用的也是HashSet而不是HashMap),因此这里统一用一个byte长度的值来表示value,就是这个static变量ZERO_LENGTH_ENTRY。


    别看setAdd有这么多行,真正有用的就这一行:


    [java] view plaincopy 
    status = alreadySeen.putNoOverwrite(null, key, ZERO_LENGTH_ENTRY);  
    将压缩后得到的long型值作为key,ZERO_LENGTH_ENTRY作为value插入到BerkeleyDB中,如果db中已经有了这个long型值,就会返回OperationStatus.KEYEXIST,表示对应的URL之前已经抓取到了,那么这个URL就不会放入待抓取队列中。
    第五,基于布隆过滤器(Bloom Filter)的存储。 


        使用布隆过滤器,设计多个Hash函数,也就是对每个字符串进行映射是经过多个Hash函数进行映射,映射到一个二进制向量上,这种方式充分利用了比特位。 
        基于内存的HashSet的方法存在一个本质的问题,就是它消耗的内存是随着URL的增长而不断增长的。除非能够保证内存的大小能够容纳下所有需要抓取的URL,否则这个方案终有一天会到达瓶颈。
       这时候就会想,要找一个类似于HashSet的但所消耗的内存相对固定而不会不断增长的方案,于是自然想到了Bloom Filter。关于Bloom Filter的概念这里就不多谈了,网上随处可以找到。我简单尝试了一下Bloom Filter,但是很快就放弃了。基于Bloom Filter的方案有几个问题:
    第一个是理论上的。Bloom Filter会将一些正常的样本(在我这就是没有抓取过的URL)过滤掉,即所谓的False Positive。当然,这概率有多大,取决于Bloom Filter的参数设置。但这引出了下一个问题;
    第二个是实践中的,即Bloom Filter的那几个参数应该如何设置?m,k,n应该设置成多少才合适,这个我没有经验,而且可能需要反复的实验和测试才能够比较好的确定下来;
        以上两个问题还不是我放弃Bloom Filter的根本原因,真实的原因是我在做的是一个爬虫框架,上面可以会启动很多的爬虫任务,每个任务可能抓取自己特定的URL,而且任务之间是独立的。这样,对于每个任务都需要有一个Bloom Filter,虽然对于单一任务它使用Bloom Filter所消耗的内存是固定的,但是任务的增多会导致更多的Bloom Filter,从而导致更多的内存消耗。仍然存在内存溢出的可能。
        但如果只是一个抓取任务,那么采用Bloom Filter应该是一个非常不错的选择。


    可以参考Google的
    http://www.googlechinablog.com/2007/07/bloom-filter.html






    转自:
    http://hi.baidu.com/shirdrn/blog/item/40ed0fb1ceac4d5c0923029d.html
    http://blog.csdn.net/f81892461/article/details/8592505
    展开全文
  • URL去重

    2021-02-16 10:52:24
    URL去重问题 URL 去重思路 在不考虑业务场景和数据量的情况下,我们可以使用以下方案来实现 URL 的重复判断: 1.使用 STL的 Set 集合,根据添加时的结果来判断 URL 是否重复(添加成功表示 URL 不重复); 2.使用 ...

    URL去重问题

    URL 去重思路
    在不考虑业务场景和数据量的情况下,我们可以使用以下方案来实现 URL 的重复判断:
    1.使用 STL的 Set 集合,根据添加时的结果来判断 URL 是否重复(添加成功表示 URL 不重复);
    2.使用 Redis 中的 Set 集合,根据添加时的结果来判断 URL 是否重复;
    3.将 URL 都存储在数据库中,再通过 SQL 语句判断是否有重复的 URL;
    4.把数据库中的 URL 一列设置为唯一索引,根据添加时的结果来判断 URL 是否重复;
    5.使用 Guava 的布隆过滤器来实现 URL 判重;(谷歌)
    6.使用 Redis 的布隆过滤器来实现 URL 判重。

    Set 集合天生具备不可重复性,使用它只能存储值不相同的元素,如果值相同添加就会失败,因此我们可以通过添加 Set 集合时的结果来判定 URL 是否重复
    其他的就不做多解释 我们主要了解Redis的布隆过滤器
     比如有如下几个需求:
      ①、原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中?
      解决办法一:将10亿个号码存入数据库中,进行数据库查询,准确性有了,但是速度会比较慢。
      解决办法二:将10亿号码放入内存中,比如Redis缓存中,这里我们算一下占用内存大小:10亿*8字节=8GB,通过内存查询,准确性和速度都有了,但是大约8gb的内存空间,挺浪费内存空间的。
      ②、接触过爬虫的,应该有这么一个需求,需要爬虫的网站千千万万,对于一个新的网站url,我们如何判断这个url我们是否已经爬过了?
      解决办法还是上面的两种,很显然,都不太好。
      ③、同理还有垃圾邮箱的过滤。
      那么对于类似这种,大数据量集合,如何准确快速的判断某个数据是否在大数据量集合中,并且不占用内存,布隆过滤器应运而生了
    省空间: 不需要存储完整的元素,只需要对元素进行hash然后将bit向量表中的某个位设为1即可(先不考虑碰撞问题)
    布隆过滤器:一种数据结构,是由一串很长的二进制向量组成,可以将其看成一个二进制数组。既然是二进制,那么里面存放的不是0,就是1,但是初始默认值都是0。bitmaps
    查找快: 只需要对查找的元素进行hash然后看bit向量表中对应的位是否为1。
    我们可以得到一个结论:布隆过滤器可以判断某个数据一定不存在,但是无法判断一定存在。
      优点:优点很明显,二进制组成的数组,占用内存极少,并且插入和查询速度都足够快。
      缺点:随着数据的增加,误判率会增加;还有无法判断数据一定存在;另外还有一个重要缺点,无法删除数据。
    1.因为碰撞,会有一定的误报率( 不在集合的一定不在, 在的不一定在 )。这个可以通过使用多个hash函数减少误报,但无法完全消除。
    2.不支持删除操作(还是因为碰撞,会出现误删的问题)。

    展开全文
  • 对网络爬虫有一定了解的小伙伴们应该都知道,网络爬虫在爬取信息的时候,为了避免爬虫爬到重复数据、爬虫陷入死循环等问题,我们就需要对URL去重。 目录 1、什么是URL去重? 2、为什么要进行URL去重? 2.1、先...

    对网络爬虫有一定了解的小伙伴们应该都知道,网络爬虫在爬取信息的时候,为了避免爬虫爬到重复数据、爬虫陷入死循环等问题,我们就需要对URL去重。

    目录

     

    1、什么是URL去重?

    2、为什么要进行URL去重?

    2.1、先了解爬虫的基本框架:

    2.2、URL为什么会重复,爬虫又为什么会陷入死循环?

    3、URL去重的5种方式

    3.1、列表

    3.2、set集合

    3.3、set+md5

    3.4、bitmap(位图)

    3.5、boomfilter(布隆过滤器)


    1、什么是URL去重?

    字面意思,去除相同的URL,使得爬虫在爬取过程中尽可能少的爬取重复数据。

    2、为什么要进行URL去重?

    反过来说,就是不对URL进行去重,会产生那些问题呢?

    • 1、数据重复爬取
    • 2、爬虫陷入死循环
    • 3、爬取效率低下
    • .....

    上面的问题是怎么产生的呢?

    首先,我们要明确一点,URL去重是应用于网络爬虫(不知道什么是网络爬虫自己度娘一下)的。

    2.1、先了解爬虫的基本框架:

    单机版 (这里的单机版指的是一台机器):

    单机版中URL去重体现在: 爬取每一个页面前,先看看以前是否已经爬取过这个页面,如果没有爬取过就爬取,否则直接跳过。

    分布式

    分布式爬虫中URL去重体现在:维护一个不重复的请求队列。

    2.2、URL为什么会重复,爬虫又为什么会陷入死循环?

    这里以3个url为例:一个页面中会包括多个超链接,而所有的超链接都是我们可能要爬取的目标。

    我们假设url1中有url2的超链接,url2有url3的超链接,url3又有url1的超链接,那么这三个页面就可以构成下面的关系。

    相信聪明的你已经看出了端倪,如果再多几个页面,那么这些页面就形成了一个网(有回路),这是网络爬虫不对url去重而会陷入死循环的原因。

     

    所以,要想编写出功能强大的网络爬虫,url去重是必不可少的。

    3、URL去重的5种方式

    3.1、列表

    列表优点:简单易操作

    缺点:每次添加URL到列表之前,都要先查询一下是否已存在,非常耗费时间和内存空间。

    3.2、set集合

    集合优点:对比list来说,省去了过多的查询,节省了一些时间和内存空间

    缺点:耗费内存空间较大,如果有一亿条URL,一个URL50字符:

                  100000000 * 50字符 * 2byte / 1024 / 1024 / 1024 约= 9.3GB 

    3.3、set+md5

    优点:对比单纯使用set来说,md5加密方式大大缩小了占用内存空间

    缺点:耗费内存空间还是很大,如果有一亿条URL,一个URL16字节:

                  100000000 * 16byte / 1024 / 1024 / 1024 约= 1.4GB 

    3.4、bitmap(位图)

    优点:对比使用set+md5来说,位图的方式将空间占用缩小到了极限。如果有一亿条URL,一个URL1位:
                  100000000 / 8bit / 1024 / 1024 / 1024 约= 12M

    缺点:产生哈希冲突的可能性很大。

    3.5、boomfilter(布隆过滤器)

    优点:对比使用bitmap来说,BloomFilter降低了的哈希冲突的出现率。

    缺点:对比bitmap方式来说,BloomFilter较多的耗费内存空间,有一定的误识别率和删除困难。

                 不存在漏报(False Negative),即某个元素在某个集合中,肯定能报出来。
                 可能存在误报(False Positive),即某个元素不在某个集合中,可能也被爆出来。

     

    总结一下:

    1、list : 简单易操作,耗费内存空间多,耗费资源多

    2、set:比list耗费资源少

    3、set+md5:比set耗费内存空间少(scrapy-redis中使用的就是类似这种的)

    4、bitmap: 耗费内存空间最少,产生hash冲突的概率极大。

    5、boomfilter: 耗费内存空间比bitmap多一点,产生hash冲突的概率比bitmap小一些,但是可能存在误报,而且删除困难。

     

    最后多说一点:去重是一种思想,去重并不是只能用在url上,还可以用在任何东西上。比如说:爬取100万首音乐,就可以用去重来保证爬取到的音乐的内容不重复。

    展开全文
  • 基于bloomfilter算法的c语言实验的url去重。使用的时候被去重的文件需要是txt格式的。
  • python爬虫url去重

    2019-09-24 19:41:21
    1.url去重     从字面上理解,url去重即去除重复的url,在爬虫中就是去除已经爬取过的url,避免重复爬取,既影响爬虫效率,又产生冗余数据。 2.url去重策略     从表面上看,url去重策略就是消除url重复的...
  • scrapy-redis实现url去重

    2020-05-18 14:33:34
    #一个去重的类,用来将url去重 DUPEFILTER_CLASS = "scrapy_redis.dupefilter.RFPDupeFilter" #一个队列 SCHEDULER = "scrapy_redis.scheduler.Scheduler" #是否持久化(爬完后不会再爬了,像一些固定的数据) ...
  • 封面:image本期我们来聊聊URL去重那些事儿。以前我们曾使用Python的字典来保存抓取过的URL,目的是将重复抓取的URL去除,避免多次抓取同一网页。爬虫会将待抓取的URL放在todo队列中,从抓取到的网页中提取到新的URL...
  • python url去重

    2019-04-14 21:32:20
    python url去重 记录一些,总是忘记,感觉习惯写博客还不错 1,保存文件(数据库)中,一个一个查找是否有重复 2,压缩,将url进行压缩,放到hashset(set接口)中 3,布隆去重,原理:对于一个元素,经过m个散列...
  • url去重技术

    2013-03-05 17:35:28
    URLQUCHONGJISHU ,哈希表的简历和网络爬虫的工作机制 能够在信息采集项目开发商
  • url去重方案 1.去重方案 将url保存到数据库中,检查时在数据库中查找。效率太低,频繁的切换内外存。 将url保存到程序内存set集合中,查询速度快,但是占用内存太大。 与第二种方法类似,只是进一步改进之后...
  • scrapy通过自定义类给爬取的url去重

    千次阅读 2018-10-16 11:23:54
    之前我们是通过在parse函数里设置集合来解决url去重的问题。 首先先在根目录中建立一个新的duplication的py文件,在from scrapy.dupefilter import RFPDupeFilter,在RFPDupeFilter源码中把BaseDupeFilter类复制到...
  • https://blog.csdn.net/Mr__lqy/article/details/85859361
  • 用redis实现scrapy的url去重与增量爬取

    千次阅读 2018-07-13 20:11:16
    scrapy 自带了去重方案,通过RFPDupeFilter类完成去重,查看源码。 def request_seen(self, request): fp = self.request_fingerprint(request) if fp in self.fingerprints: return True self.fin...
  • 面试题 :10亿url去重只给4G内存

    千次阅读 2019-09-30 12:04:52
    可以用树和折半的思想将10亿url,变成单元最小化的树,然后用ex表去重 ex表去重时也可以用树的思想让内存最大利用! (ps:当然要花费大量时间和精力)! 转载于:https://www.cnblogs.com/yongqi-wang/p/1...
  • 初识 python 装饰器 以及 通过url去重 今天写爬虫遇到去重问题。在管理多个爬虫时,单独写函数太过冗余,想起了原来带我做项目的大哥极力推荐的装饰器!自己也来试试 主要目的是通过set对爬取的网页进行去重,...
  • 爬虫如何对URL去重

    2019-09-07 15:58:44
    URL去重: 就是爬虫将重复抓取的url去除,避免多次抓取同一个网页,因为重复抓取不仅会浪费CPU,还会为搜索引擎系统增加负荷。爬虫一般会将待抓取的url放在一个队列中,从抓取后的网页中提取到新的url,在它们被放入...
  • scrapy的url去重原理

    千次阅读 2018-07-13 21:34:58
    1.需要将dont_filter设置为False开启去重,默认是True,没有开启去重;2.对于每一个url的请求,调度器都会根据请求得相关信息加密得到一个指纹信息,并且将指纹信息和set()集合中的指纹信息进行比对,如果set()集合...
  • 主要介绍几个常用和...当需要进行检测URL是否重复的时候,只需要将这个URL进行Hash映射,如果得到的地址已经存在,说明已经被下载过,放弃下载,否则,将该URL及其Hash地址作为键值对存放到Hash表中。这样,URL去...
  • 针对双结构网络的特点及其URL去重面临的挑战,根据Bloom Filter的工作原理,提出一种基于可扩展的动态可分裂Bloom Filter的URL去重机制,并在原型系统中进行实现和部署。实验结果表明,该机制能够有效适用于大规模、高...
  • Python | URL去重策略

    2021-02-03 00:26:50
    一、前言今天给大家分享的是,Python爬虫里url去重策略及实现。二、url去重及策略简介1. url去重从字面上理解,url去重即去除重复的url,在爬虫中就是去除已经爬取过的url,避免重复爬取,既影响爬虫效率,又产生冗余...
  • url去重

    2016-01-26 11:20:26
    为了尽快把整个爬虫搭建起来,最开始的URL去重采用方案是一个内存中的HashSet,这是最直观的方法,所有人都能想得到。HashSet中放置的就是URL的字符串,任何一个新的URL首先在HashSet中进行查找,如果HashSet中没有...
  • 自定义过滤器: import hashlib from redis import StrictRedis from scrapy.dupefilters import RFPDupeFilter ...from w3lib.url import canonicalize_url class URLRedisFilter(RFPDupeFilter):...
  • 不简单的URL去重

    千次阅读 2014-03-29 09:28:10
    所谓的Url去重(我一直没找到对应的英文,URL Filtering ?),就是爬虫将重复抓取的URL去除,避免多次抓取同一网页。爬虫一般会将待抓取的URL放在一个队列中,从抓取后的网页中提取到新的URL,在他们被放入队列之前...
  • #资源达人分享计划#
  • 在进行URL去重的时候,我们的基本思路是将拿到的URL与已经抓取过的URL队列进行比对,看当前URL是否在此队列中,如果在已抓取过的队列中,则将此URL进行舍弃,如果没有在,则对此URL进行抓取。看到这,如果有哈希表...
  • 关于URL去重-MD5算法步骤

    千次阅读 2018-12-16 14:58:43
    URL去重-MD5算法学习笔记 URL去重-MD5算法学习笔记 在网络爬虫过程中,会爬取到很多相同的url,这个时候就需要我们去掉重复的URL。关于URL去重的算法有很多,刚刚学习了MD5算法。MD5算法是基于Hash的算法。所以首先...
  • 来源 | Java中文社群(ID:javacn666)URL 去重在我们日常工作中和面试中很常遇到,比如这些:可以看出,包括阿里,网易云、优酷、作业帮等知名互联网公司都出现过类似的面试题...
  • 爬虫url去重策略

    2020-04-25 16:19:44
    爬虫url去重策略 1、将访问过的url保存到数据库中 最简单的方式,但是用的很少 2、将访问过的url保存到内存(set)中,只需要O(1)的代价就可以查询url 这样内存的占用会越来越大。 当有1亿条url时,假设每个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,881
精华内容 12,752
关键字:

url去重