温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

​Python爬虫怎么实现url去重

发布时间:2021-11-22 16:41:07 阅读:288 作者:iii 栏目:编程语言
Python开发者专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

这篇文章主要介绍“Python爬虫怎么实现url去重”,在日常操作中,相信很多人在Python爬虫怎么实现url去重问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python爬虫怎么实现url去重”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

一、前言

Python爬虫里url去重策略及实现。

二、url去重及策略简介

1.url去重

    从字面上理解,url去重即去除重复的url,在爬虫中就是去除已经爬取过的url,避免重复爬取,既影响爬虫效率,又产生冗余数据。

2.url去重策略

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

11.将访问过的ur保存到数据库中22.将访问过的ur保存到set(集合)中,只需要o(1)的代价就可以查询url3#       10000000*2byte*50个字符/1024/1024/1024=9G4# 3.url经过md5等方法哈希后保存到set54.用 bitmap方法,将访问过的ur通过hash函数映射到某一位65. bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突

三、看代码,边学边敲边记url去重策略

1.将访问过的ur保存到数据库中(初学使用)

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

2.将访问过的ur保存到set内存中

将访问过的ur保存到set中,只需要o(1)的代价就可以查询url,取url方便快速,基本不用查询,但是随着存储的url越来越多,占用内存会越来越大。

1# 简单计算:假设有1亿条url,每个url平均长度为50个字符,python里unicode编码,每个字符16位,占22# 个字节(byte3# 计算式:10^8 x 50个字符 x 2byte / 1024 / 1024 / 1024 = 9G4#                                    B      M      G5如果是2亿个url,那么占用内存将达18G,也不是特别方便,适合小型爬虫。
3.url经过md5缩减到固定长度
 1'''
 2简单计算:一个url经MD5转换,变成一个128bit(位)的字符串,占16byte(字节),方法二中一个url保守
 3估计占50个字符 x 2 = 100byte(字节),
 4计算式: 这样一比较,MD5的空间节省率为:(100-16)/100 = 84%(相比于方法二)
 5(Scrapy框架url去重就是采用的类似方法)
 6'''
 7# 维基百科看MD5算法
 8'''
 9MD5概述10设计者 : 罗纳德·李维斯特11首次发布 : 1992年4月12系列 : MD, MD2, MD3, MD4, MD513编码长度 : 128位14结构 : Merkle–Damgård construction15    MD5消息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可16以产生出一个128位(16字节)的散列值(hash value),用于确保信息传输完整一致。MD5由美国密码学家17罗纳德·李维斯特(Ronald Linn Rivest)设计,于1992年公开,用以取代MD4算法。这套算法的程序在 18RFC 1321 中被加以规范。19将数据(如一段文字)运算变为另一固定长度值,是散列算法的基础原理。20'''

MD5使用实例:


 1# 在python3中使用hashlib模块进行md5操作
 2import hashlib
 3
 4# 待加密信息
 5str01 = 'This is your md5 password!'
 6# 创建md5对象
 7md5_obj = hashlib.md5()
 8# 进行MD5加密前必须 encode(编码),python里默认是unicode编码,必须转换成utf-8
 9# 否则报错:TypeError: Unicode-objects must be encoded before hashing10md5_obj.update(str01.encode(encoding='utf-8'))1112print('XksA的原话为 :' + str01)13print('MD5加密后为 :' + md5_obj.hexdigest())1415# result :16#        XksA的原话为 :This is your md5 password!17#        MD5加密后为 :0a5f76e7b0f352e47fed559f904c9159
4.用 bitmap方法,将访问过的ur通过hash函数映射到某一位
 1'''
 2实现原理:通过hash函数,将每个url映射到一个hash位置中,一个hash位可以只占用一个bit(位)大小,那
 3么相对于方法三:一个url占128bit(位),hash函数法的空间节省成百倍增长。
 4计算式:这样一比较,bitmap方法的空间节省率为:
 5(128-1)/128= 99.2%(相比于方法三)
 6(100 * 8 - 1)/(100*8)= 99.88%(相比于方法一)
 7                       ##   (缺点:容易产生冲突)  ##
 8'''
 9# 维基百科看Hash 函数10'''11hash函数:12散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”13的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混14合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常15用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数16据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。17'''
5.bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突
 1# 维基百科看Bloomfilter
 2'''
 3# 基本概述
 4   如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。
 5链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,
 6我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为:
 7                            O(n),O(log n),O(n/k)
 8# 原理概述
 9   布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个10点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点11有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。12# 优缺点13    布隆过滤器可以用于检索一个元素是否在一个集合中。14    优点是空间效率和查询时间都远远超过一般的算法。15    缺点是有一定的误识别率和删除困难。16'''17# Bloomfilter介绍还可以看这里:https://blog.csdn.net/preyta/article/details/72804148

Bloomfilter底层实现:

 1# 源码地址:https://github.com/preytaren/fastbloom/blob/master/fastbloom/bloomfilter.py
 2import math
 3import logging
 4import functools
 5
 6import pyhash
 7
 8from bitset import MmapBitSet
 9from hash_tools import hashes101112class BloomFilter(object):13    """14    A bloom filter implementation,15    which use Murmur hash and Spooky hash16    """17    def __init__(self, capacity, error_rate=0.0001, fname=None,18                 h2=pyhash.murmur3_x64_128(), h3=pyhash.spooky_128()):19        """20        :param capacity: size of possible input elements21        :param error_rate: posi22        :param fname:23        :param h2:24        :param h3:25        """26        # calculate m & k27        self.capacity = capacity28        self.error_rate = error_rate29        self.num_of_bits, self.num_of_hashes = self._adjust_param(4096 * 8,30                                                                  error_rate)31        self._fname = fname32        self._data_store = MmapBitSet(self.num_of_bits)33        self._size = len(self._data_store)34        self._hashes = functools.partial(hashes, h2=h2, h3=h3, number=self.num_of_hashes)3536    def _adjust_param(self, bits_size, expected_error_rate):37        """38        adjust k & m through 4 steps:39        1. Choose a ballpark value for n40        2. Choose a value for m41        3. Calculate the optimal value of k42        4. Calculate the error rate for our chosen values of n, m, and k.43           If it's unacceptable, return to step 2 and change m;44           otherwise we're done.45        in every loop, m = m * 246        :param bits_size:47        :param expected_error_rate:48        :return:49        """50        n, estimated_m, estimated_k, error_rate = self.capacity, int(bits_size / 2), None, 151        weight, e = math.log(2), math.exp(1)52        while error_rate > expected_error_rate:53            estimated_m *= 254            estimated_k = int((float(estimated_m) / n) * weight) + 155            error_rate = (1 - math.exp(- (estimated_k * n) / estimated_m)) ** estimated_k56            logging.info(estimated_m, estimated_k, error_rate)57        return estimated_m, estimated_k5859    def add(self, msg):60        """61        add a string to bloomfilter62        :param msg:63        :return:64        """65        if not isinstance(msg, str):66            msg = str(msg)67        positions = []68        for _hash_value in self._hashes(msg):69            positions.append(_hash_value % self.num_of_bits)70        for pos in sorted(positions):71            self._data_store.set(int(pos))7273    @staticmethod74    def open(self, fname):75        with open(fname) as fp:76            raise NotImplementedError7778    def __str__(self):79        """80        output bitset directly81        :return:82        """83        pass8485    def __contains__(self, msg):86        if not isinstance(msg, str):87            msg = str(msg)88        positions = []89        for _hash_value in self._hashes(msg):90            positions.append(_hash_value % self.num_of_bits)91        for position in sorted(positions):92            if not self._data_store.test(position):93                return False94        return True9596    def __len__(self):97        return self._size

到此,关于“Python爬虫怎么实现url去重”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:http://blog.itpub.net/31556503/viewspace-2216250/

AI

开发者交流群×