文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Scrapy爬虫去重效率优化之Bloom Filter的算法的对接

当爬取达到亿级别规模时，Scrapy-Redis提供的集合去重已经不能满足我们的要求。所以我们需要使用一个更加节省内存的去重算法Bloom Filter。 1....利用这个算法我们可以实现去重效果。 本节我们来了解Bloom Filter的基本算法，以及Scrapy-Redis中对接Bloom Filter的方法。 2....Bloom Filter的算法 在Bloom Filter中使用位数组来辅助实现检测判断。在初始状态下，我们声明一个包含m位的位数组，它的所有位都是0，如下图所示。 ?...接下来，我们将Bloom Filter算法应用到Scrapy-Redis分布式爬虫的去重过程中，以解决Redis内存不足的问题。 3....这样就成功利用Bloom Filter替换了Scrapy-Redis的集合去重。

3.8K72
您找到你想要的搜索结果了吗？
是的
没有找到

海量数据处理算法—Bloom Filter

Bloom-Filter算法简介 Bloom-Filter，即布隆过滤器，1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。...因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。...Bloom Filter的详细介绍：Bloom Filter 2、 Bloom-Filter的基本思想 Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。...所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。 此外，Bloom Filter的hash函数选择会影响算法的效果。...此时，Bloom-Filter算法是最好的选择。

68910

布隆过滤器(bloom filter)的原理及在推荐去重中的应用

遇到的问题 在业务中,我需要给每个用户保存1w条浏览记录,之后每一次的返回值都要和历史记录做一个去重,即保证用户不会重复看到同一篇文章....布隆过滤器 介绍 以下摘自维基百科: 布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。...它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。 说直白一点就是:布隆过滤器用自己的算法,实现了快速的检索一个元素是否在一个较大的元素列表之中....我的解决方案 1. hbase部分 hbase负责存储用户浏览记录的原始数据,只保存用户浏览的文章的id或者url,这里以id为例....布隆过滤器部分 主要是添加以及查询两个操作,从hbase拿到数据之后,构造过滤器,然后对当前返回的10条内容进行判重.之后将新的10条内容加入过滤器,再次写入redis. 流程图 ?

2.1K30

快速入门网络爬虫系列 Chapter04 | URL管理

三、Bloom Filter Bloom Filter是在1970年代由Bloom出的一种多哈希函数映射的快速查找算法 它是一种空间效率高的随机数据结构 使用位数组表示一个集合 判断一个元素是否属于这个集合...Bloom Filter的基本思路是：通过多个不同的Hash函数来解决“冲突” Bloom Filter主要包含以下两个部分： 1个比特数组：长度为m，并初始化为0 k个hash函数：进行URL哈希，...w是要判断的URL： 可以看到，w经过hash之后三个对应的位置上有一个不是1，我们可以肯定这个URL没有被抓取过 3.1、Bloom Filter的缺点 Bloom Filter的查询时间和空间效率虽高...，但是有以下缺点： Bloom Filter集合中的元素无法删除 如何确定位数组的大小以及hash函数的个数 Bloom Filter会出现错误判断，无法达到零错误 3.2、Bloom Filter通常的应用场景...B 不会因为域名更换而不收录 五、简单小结 1、URL去重的方法 Hash去重方法速度快，实现简单，但无法应对大数据量 使用Bloom Filter来对URL进行去重 2、URL重定向 Dispatch

1.5K30

海量数据处理利器之布隆过滤器

看见了海量数据去重，找到停留时间最长的IP等问题，有博友提到了Bloom Filter，我就查了查，不过首先想到的是大叔，下面就先看看大叔的风采。...一、布隆过滤器概念引入       （Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。...它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难...方法1：基本的排序方法包括冒泡，快排等。      方法2：使用BitMap算法      方法1就不介绍了，方法2中所谓的BitMap是一个位数组，跟平时使用的数组的唯一差别在于操作的是位。...不过有一种布隆过滤器的变体Counter Bloom Filter，可以支持删除元素，感兴趣的读者可以查阅相关文献资料。

1.3K50

Redis缓存雪崩、缓存穿透、缓存预热、缓存更新、缓存降级等问题

思考 5TB的硬盘上放满了数据，请写一个算法将这些数据进行排重。如果这些数据是一些32bit大小的数据该 如何解决？如果是64bit的呢？...对于空间的利用到达了一种极致，那就是Bitmap和布隆过滤器(Bloom Filter)。...它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。 Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。...Hash存在一个冲突（碰撞）的问题，用同一个Hash得到的两个URL的值有可能相同。...这便是Bloom-Filter的基本思想。 Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。

2.2K20

使用bloomfilter修改scrapy-redis去重

在这种情况下，我们要么通过增加内存来提高爬取上限，要么就改变去重算法来减少内存占用。增加内存对于我们来说不太合适（qiong），那么就要改变去重算法了。bloomfilter就是这样一个算法。...Bloomfilter算法简介 Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。...Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，Bloom Filter不适合那些“零错误”的应用场合。...而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。 集合表示和元素查询 下面我们具体来看Bloom Filter是如何用位数组表示集合的。...初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

1.3K20

Bloom Filter的对接

14.4 Bloom Filter 的对接 首先回顾一下 Scrapy-Redis 的去重机制。...当爬取达到亿级别规模时，Scrapy-Redis 提供的集合去重已经不能满足我们的要求。所以我们需要使用一个更加节省内存的去重算法 Bloom Filter。 1....Bloom Filter 的空间利用效率很高，使用它可以大大节省存储空间。Bloom Filter 使用位数组表示一个待检测集合，并可以快速地通过概率算法判断一个元素是否存在于这个集合中。...利用这个算法我们可以实现去重效果。 本节我们来了解 Bloom Filter 的基本算法，以及 Scrapy-Redis 中对接 Bloom Filter 的方法。 2....BloomFilter 的算法 在 Bloom Filter 中使用位数组来辅助实现检测判断。在初始状态下，我们声明一个包含 m 位的位数组，它的所有位都是 0，如图 14-7 所示。

44020

【算法】BloomFilter概念和原理以及业务中的应用场景

Filter将标准 Bloom Filter位数组的每一位扩展为一个小的计数器（counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter...Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。...，根据业务数据量设置位数组的大小，将位数组全部设置为0；将每个URL地址通过哈希算法处理，获得相应的哈希值；根据哈希值计算出位数组中的位置，将位数组中的位置设置为1；当新的URL地址进入时，重复上述步骤计算出对应的位置检查位数组中的位置是否为...0，如果是0，则表示该URL地址一定没被爬取过；如果URL地址不存在，经过爬虫处理后，则将其对应的位置设置为1，以表示该URL地址已经存在；重复上述步骤，直到所有的URL地址都处理完毕，完成去重。...具体的SpringBoot整合案例请看我的另外一篇文章：【案例实战】爬虫URL去重实战-SpringBoot2.x+Guava布隆过滤器图片（4）海量数据下-分库分表下手机号重复注册解决方案一般业务里面的

46900

由散列表到BitMap的概念与应用（二）

本文将会具体讲解BitMap的扩展：布隆过滤器（Bloom filter）。...算法描述 集合表示与元素查询 具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。 ?...因此他有如下三个使用场景: 网页爬虫对URL的去重，避免爬取相同的URL地址 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信） 缓存击穿，将已存在的缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及...这里只要增加一个bloom算法的服务，服务端插入一个key时，在这个服务中设置一次。需要查询服务端时，先判断key在后端是否存在，这样就能避免服务端的压力。...参考 大量数据去重：Bitmap和布隆过滤器(Bloom Filter) https://blog.csdn.net/zdxiq000/article/details/57626464 布隆过滤器 (Bloom

58530

内存受限下找出亿级整数集合中的不重复元素

这时就需要设计适合内存受限环境的算法,来解决问题。本文将以在内存不足的情况下,找出亿级规模整数集合中的不重复元素为例,探讨一种基于Bloom Filter的数据结构的解决方案。...Bloom Filter解法针对上述问题,我们可以考虑使用Bloom Filter这种空间效率极高的概率数据结构。Bloom Filter本质是一个很长的二进制向量和一系列随机映射函数。...具体地,思路是:初始化一个225MB大小的Bloom Filter分批读取整数数据,每次处理1万个对每批数据,将元素存入Bloom Filter再次遍历数据,检查每个元素是否在Bloom Filter中命中未命中的元素即为不重复元素代码实现...二次遍历时只检查元素是否在Bloom Filter中,而不需要加载集合本身。总结对于内存无法容纳的超大数据集,使用Bloom Filter可以实现高效地去重和查询。...本文给出了一种基于Bloom Filter解决大整数去重问题的设计思路。虽然无法覆盖所有场景,但希望可以作为算法设计的一个模板

17830

布隆过滤器Bloom Filter简介

因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。...去重 垃圾邮件过滤 黑名单 问题实例： 给你A，B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。...具体做法就是：将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url...5、如何解决布隆过滤器不支持删除的问题： （1）counting bloom filter： Counting Bloom Filter将标准 Bloom Filter位数组的每一位扩展为一个小的计数器...Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。

39220

深度剖析各种BloomFilter的原理、改进、应用场景

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。 一....若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。 　　实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！...Bloom Filter的算法 　　废话说到这里，下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。...Bloom Filter算法如下： 　 创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。...Bloomier Filters Decaying Bloom Filters Stable Bloom Filter Space Code Bloom Filter Filter Banks Scalable

1.5K20

高级算法篇：布隆过滤器？非也，布谷鸟过滤器是也

过滤器在数据科学中的应用十分广泛，包括数据库查询、数据快速检索，数据去重等等。过滤器的出现是为了解决在大量数据的环境下，能够更好更快的（节省计算资源或者存储资源）筛查数据的需求。...实际的应用场景有： 爬虫程序的URL识别：即爬虫在访问 URL 时对 URL 进行判断，如果访问过(在集合中)就不访问，如果没有访问过那么就访问然后放入已访问集合，提高爬虫效率。...Bloom filter Bloom filter 使用 hash 函数的散列技术存储信息的存在状态而不是存储信息本身，常常用于判断一个信息是否在一个集合中，这样只需要几个bit的空间就能解决问题。...基本原理 bloom filter作为一种海量数据处理算法，其要点在于用于存储的位数组和用于处理的hash函数（一般有多个，并且为了精确度和数据量增加）。...Cuckoo filter理解 原理 Cuckoo filter 同样使用哈希表来实现数据到实际存储区域的映射，不同于 Bloom filer 的是Cuckoo filter中只采用两个哈希映射函数 H1

3.2K10

详解大规模数据处理利器 BloomFilter 算法

转自：heaad http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法...若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。 实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！...也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。 Bloom Filter的算法 废话说到这里，下面引入本篇的主角——Bloom Filter。...Bloom Filter算法如下： 创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。...Bloom filter. http://en.wikipedia.org/wiki/Bloom_filter 觉得本文有帮助？请分享给更多人 关注「算法爱好者」，修炼编程内功

74970

scrapy去重与scrapy_redis去重与布隆过滤器

很典型的做法是事先定义一个去重队列，判断抓取的url是否在其中，如下： crawled_urls = set() def check_url(url): if url not in crawled_urls...scrapy的去重 scrapy对request不做去重很简单，只需要在request对象中设置dont_filter为True，如 yield scrapy.Request(url, callback...其实就是说：scrapy使用sha1算法，对每一个request对象加密，生成40为十六进制数，如：'fad8cefa4d6198af8cb1dcf46add2941b4d32d78'。...return request_fingerprint(request) 首先拿到scrapy.http.Request会先调用self.request_fingerprint去计算，也就是scrapy的sha1算法去加密...（因为可能会有其它的元素也映射到相应的比特位上） 同时这也导致不能从 Bloom filter 中删除某个元素，无法确定这个元素一定在集合中。

2.3K20

如何让爬虫一天抓取100万张网页

对机器内存，硬盘空间，URL去重，网络性能，抓取间隙时间调优一般都不会在意。...优化内存，URL去重 再来说内存占用问题，做爬虫程序为了防止重复抓取URL，一般要把URL都加载进内存里，放在set()里面。...就还需要想办法压缩URL的内存占用，可以使用BloomFilter算法，是一个很经典的算法，非常适用海量数据的排重过滤，占用极少的内存，查询效率也非常的高。...BloomFilter调用也非常简单，当然需要先install 安装bloom_filter： from bloom_filter import BloomFilter# 生成一个装1亿大小的...__contains__('https://www.tianyancha.com/company/23402373') 不过奇怪，bloom里没有公有方法来判断URL是否重复，我用的__contains

1.6K20

如何让爬虫一天抓取100万张网页

对机器内存，硬盘空间，URL去重，网络性能，抓取间隙时间调优一般都不会在意。...优化内存，URL去重 再来说内存占用问题，做爬虫程序为了防止重复抓取URL，一般要把URL都加载进内存里，放在set()里面。...就还需要想办法压缩URL的内存占用，可以使用BloomFilter算法，是一个很经典的算法，非常适用海量数据的排重过滤，占用极少的内存，查询效率也非常的高。...BloomFilter调用也非常简单，当然需要先install 安装bloom_filter： from bloom_filter import BloomFilter # 生成一个装1亿大小的 bloombloom...= BloomFilter(max_elements=100000000, error_rate=0.1) # 向bloom添加URL bloom.add('https://www.tianyancha.com

1.7K30
点击加载更多

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

更多标签

活动推荐

    运营活动

    活动名称
    广告关闭

    腾讯云开发者

    扫码关注腾讯云开发者

    扫码关注腾讯云开发者

    领取腾讯云代金券

    热门产品

    热门推荐

    更多推荐

    Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

    腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

    领券