Url排重Bloom Filter 算法、误差及其他 fly with me , in the perfect world --- 题记 最近看了一些书，公式和算法，用一个词把他们窜起来的话...我这里说说误差和效率的一点关系。误差和效率是一对矛盾共同体，生活中有对误差和效率的关系描述：“萝卜快了，不洗泥”；“慢工出细活”等等，都精辟的说出了误差和效率的辨证关系。...误差换效率 google黑板报上一片文章，讲Url排重用到的一个技巧：把平均长度较长的Url转换成平均长度较短的GUID来节省空间。...在Url排重方面还有一个常用的算法：Bloom Filter 算法。...weblogs.asp.net/dfindley/archive/2004/08/19/217485.aspx http://www.darkridge.com/~jpr5/archive/dads/HTML/bloomFilter.html
Bloomfilter就是将去重对象映射到几个内存“位”，通过几个位的0/1值来判断一个对象是否已经存在。...然而Bloomfilter运行在一台机器的内存上，不方便持久化（机器down掉就什么都没啦），也不方便分布式爬虫的统一去重。...如果可以在Redis上申请内存进行Bloomfilter，以上两个问题就都能解决了。 本文即是用Python，基于Redis实现Bloomfilter去重。下面先放代码，最后附上说明。...总结 基于Redis的Bloomfilter去重，既用上了Bloomfilter的海量去重能力，又用上了Redis的可持久化能力，基于Redis也方便分布式机器的去重。...另外针对基于Scrapy+Redis框架的爬虫，我使用Bloomfilter作了一些优化，只需替换scrapy_redis模块即可使用Bloomfilter去重，并且去重队列和种子队列可以拆分到不同的机器上
为什么要使用bloomfilter 首先我们先了解一下为什么要使用bloomfilter去修改scrapy的去重机制。...(to_bytes(request.method)) fp.update(to_bytes(canonicalize_url(request.url))) fp.update(request.body...在这种情况下，我们要么通过增加内存来提高爬取上限，要么就改变去重算法来减少内存占用。增加内存对于我们来说不太合适（qiong），那么就要改变去重算法了。bloomfilter就是这样一个算法。...scrapy-redis修改去重算法 我们先看一下scrapy-redis本身提供的去重方式 def request_seen(self, request): """Returns True if...使用**kwargs参数是为了保持一致，在scheduler调度中保持参数的一致性，这样我们在settings中就可以切换配置两种去重方式： settings： # 确保所有的爬虫通过Redis去重 #
使用方：Google基于此算法实现网页文件查重。 优点：相对传统文本相似性方法（欧氏距离、海明距离、余弦角度），解决计算量庞大等问题。 ...—其他简单方案： 百度大搜的去重算法比较简单，就是直接找出此文章的最长的n句话，做一遍hash签名。n一般取3。 工程实现巨简单，据说准确率和召回率都能到达80%以上。 ...2、评估指标 排重准确率（97%）： 数据集：排重新闻集 方式：人工（研发先评估、产品评估） 召回率（75%）： 数据集：训练数据集-排重新闻集 ...参考资料 中文文档simhash值计算 网页文本的排重算法介绍 海量数据相似度计算之simhash和海明距离 短文本合并重复（去重）的简单有效做法 海明距离查询方案 原文链接：https://www.cnblogs.com
更快的方式实现PHP数组去重 1 /* 创建一个包含重复值的，一共四个元素的数组 */ 2 $array = array('green','blue','orange','blue'); 3 4 /
小编说：网络爬虫让我们高效地从网页获取到信息，但网页的重复率很高，网页需要按内容做文档排重，而判断文档的内容重复有很多种方法，语义指纹是其中比较高效的方法。...即使在同一个网站，有时候不同的URL地址可能对应同一个页面，或者存在同样的内容以多种方式显示出来，所以，网页需要按内容做文档排重。 例如，一个企业商品搜索。
要处理的对象是网页链接URL，需支持： 添加一个URL和查询一个URL 还要求这两个操作执行效率尽可能高 处理上亿网页链接，内存消耗大，存储效率要尽可能高效。...为判重 2 10亿网页链接存储在散列表，需多少内存？ 假设一个URL平均64字节，10亿URL=60GB内存。因为散列表须维持较小装载因子，保证不出现过多冲突，导致操作性能下降。...也就是说，我们要让待判重的URL，跟链表中的每个URL，做字符串匹配。显然，这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。所以，基于这两点，执行效率方面肯定是有优化空间的。...除了爬虫网页去重这个例子，还有比如统计一个大型网站的每天的UV数，也就是每天有多少用户访问了网站，我们就可以使用布隆过滤器，对重复访问的用户，进行去重。...如Java中的BitSet类就是一个位图，Redis也提供了BitMap位图类，Google的Guava工具包提供了BloomFilter布隆过滤器的实现。
一、前言 今天给大家分享的是，Python爬虫里url去重策略及实现。...二、url去重及策略简介 1.url去重 从字面上理解，url去重即去除重复的url,在爬虫中就是去除已经爬取过的url,避免重复爬取，既影响爬虫效率，又产生冗余数据。...2.url去重策略 从表面上看，url去重策略就是消除url重复的方法，常见的url去重策略有五种，如下： # 1.将访问过的ur保存到数据库中 # 2.将访问过的ur保存到set(集合)中,只需要...方法,将访问过的ur通过hash函数映射到某一位 # 5. bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突 三、看代码，边学边敲边记url去重策略 1.将访问过的ur保存到数据库中...(字节)， 计算式： 这样一比较，MD5的空间节省率为：（100-16）/100 = 84%（相比于方法二） (Scrapy框架url去重就是采用的类似方法) ''' # 维基百科看MD5算法 '''
所谓的URL去重，就是爬虫将重复抓取的URL去除，避免多次抓取同一网页。...URL的去重方法有很多种，从次到优依次可以分为以下5种： 1、将URL保存到数据库进行去重（假设单个URL的平均长度是100 byte）。...4、使用Bitmap或Bloomfilter方法去重（URL经过hash后映射到bit的每一个位上，一亿URL占用约12M，问题是存在冲突）。...去重方法介绍 一、将URL保存到数据库进行去重 为了尽快把整个爬虫搭建起来，最开始的URL去重采用方案是直接利用数据库的唯一约束进行去重，这是最省时的做法，所有人都能想得到和做到。...4、使用Bitmap方法去重 使用Bitmap方法去重的原理是把URL经过hash后映射到bit的每一个位上，一亿URL占用约12M，主要缺点是去重没那么精准，存在冲突。
年关将至，在各行各业准备享受假期的时候 安全从业者却不敢有丝毫放松 因为在节假日、大型活动等“重要时刻” 网络安全的压力总是比平常大得多 一旦发生安全事件 带来的负面效应也是不能承受之重 下拉收好这份腾讯安全重保战略秘籍
在黑盒渗透中，XSS在很多网站中普遍存在，这边分享一个简单有意思的XSS三重URL编码绕过漏洞实例。 0x01 漏洞实例 某次测试中，遇到一个很奇葩的XSS，我们先来加一个双引号，看看输出： ?...如图，可以看到，双引号被转义了，这时候是不是有种想放弃的想法，抱着尝试的状态，我对双引号进行URL双重编码，再看一下输出： ?...我们再加一层URL编码，即三重url编码，再看一下输出： ? URL编码被还原为双引号，闭合了前面的双引号，并带入到html中。我们可以轻易地构造Payload实现XSS。 ?...urldecode($b); //最后，url解码输出 ?...> 这边代码逻辑中，问题根源在于最后一句的url解码输出，导致存在XSS编码绕过的情况。根据实际情况，给出的安全建议：HTML ENCODE处理后直接输出变量。
缺点 存在误差率。随着存入的元素数量增加，误算率随之增加。（比如现实中你是否遇到正常邮件也被放入垃圾邮件目录，正常短信被拦截）可以增加一个小的白名单，存储那些可能被误判的元素。 删除困难。...布隆过滤器作为一个插件加载到了Redis Server之中，给Redis提供了强大的布隆去重功能。此文就不细讲了，大家感兴趣的可到官方查看详细文档介绍。...1% BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.01)...五 扩展知识点 假如有一台服务器，内存只有4GB，磁盘上有2个大文件，文件A存储100亿个URL，文件B存储100亿个URL。请问如何模糊找出两个文件的URL交集？如何精致找出两个文件的URL交集。...模糊交集： 借助布隆过滤器思想，先将一个文件的URL通过hash函数映射到bit数组中，这样大大减少了内存存储，再读取另一个文件URL，去bit数组中进行匹配。
对机器内存，硬盘空间，URL去重，网络性能，抓取间隙时间调优一般都不会在意。...优化内存，URL去重 再来说内存占用问题，做爬虫程序为了防止重复抓取URL，一般要把URL都加载进内存里，放在set()里面。...就还需要想办法压缩URL的内存占用，可以使用BloomFilter算法，是一个很经典的算法，非常适用海量数据的排重过滤，占用极少的内存，查询效率也非常的高。...BloomFilter调用也非常简单，当然需要先install 安装bloom_filter： from bloom_filter import BloomFilter# 生成一个装1亿大小的...从上图也能看到，基本抓到120次左右就会被屏蔽，每隔6秒拨号其实误差比较大，因为网络延迟等各种问题，导致6秒内可能抓100次，也可能抓120次。
譬如： 网页爬虫对URL的去重，避免爬取相同的URL地址； 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）； 缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及...我们使用BloomFilter的目的就是想省空间，所以我们需要做的就是在错误率上做个权衡就OK。 很多时候这个错误率我们是能接受的，譬如垃圾邮箱问题，是坏人一定会被抓，这个能保证。...至于爬虫Url重复这个就更没问题了，会缺掉一些网页而已。...至于在缓存穿透上的应用，是为了避免恶意用户频繁请求缓存中不存在DB也不存在的值，会导致缓存失效、DB负载过大，可以使用BloomFilter把所有数据放到bit数组中，当用户请求时存在的值肯定能放行，部分不存在的值也会被放行...讲了这么多，可以看到，原理很简单，但要实际做一个BloomFilter可就麻烦了，已经属于科学家的范畴了，好在早早有人已经搞定了java版的实现，用法很简单，下一篇看看。
BitMap对于每一个可能的整型值，通过直接寻址的方式进行映射，相当于使用了一个哈希函数，而布隆过滤器就是引入了k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程。...那么布隆过滤器的误差有多少？我们假设所有哈希函数散列足够均匀，散列后落到Bitmap每个位置的概率均等。...当我们对某个元素进行判重时，误判即这个元素对应的k个标志位不全为1，但所有k个标志位都被置为1，误判率ε约为： ? ? ? 场景 布隆过滤器的最大的用处就是，能够迅速判断一个元素是否在一个集合中。...因此他有如下三个使用场景: 网页爬虫对URL的去重，避免爬取相同的URL地址 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信） 缓存击穿，将已存在的缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及...布隆过滤器就是引入了k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程。布隆过滤器有一个误判率的概念，误判率越低，则数组越长，所占空间越大。
BitmapBitmap，位图，首先看它的名字，比特map，首先我们听到map，一般都有去重的功能，bitmap听名字就像使用bit存储的map。...Bitmap其极致的空间用在大数据量去重非常合适的，除了QQ号去重，我们还可以用在比如订单号去重；爬取网站时URL去重，爬过的就不爬取了。...布隆过滤器（BloomFilter），布隆过滤器的基础就是使用的位图，只不过布隆过滤器使用了多个哈希函数处理，只有当全部的哈希都为1，才表示这个值存在。...String.valueOf(m), String.valueOf(5)).intValue(); long size = mNum * 1024 * 1024 * 8; filters = new BloomFilter...缺点：可能产生哈希冲突，如果判断某个位置值为1，那么可能是产生了哈希冲突，所以，布隆过滤器会有一定误差。
布隆过滤器适合处理那些对一定的误判率可以接受的场景，例如网页爬取中的URL去重、缓存穿透问题的解决等。...布隆过滤器的应用场景网页爬取中的URL去重：在爬虫系统中，布隆过滤器可以帮助快速判断一个URL是否已经被抓取过，避免重复抓取。...数据去重：对于海量数据的去重操作，布隆过滤器可以减少实际判重的开销，提高数据处理效率。...应用场景示例应用场景介绍布隆过滤器在实际应用中有很多场景，例如爬虫系统中的URL去重、缓存穿透问题的解决、拦截恶意请求等。...实际应用场景示例：URL去重在爬虫系统中，经常会遇到重复抓取同一个URL的情况，为了提高效率和节约资源，可以使用布隆过滤器来实现URL去重功能，减少重复抓取的次数。
对机器内存，硬盘空间，URL去重，网络性能，抓取间隙时间调优一般都不会在意。...优化内存，URL去重 再来说内存占用问题，做爬虫程序为了防止重复抓取URL，一般要把URL都加载进内存里，放在set()里面。...就还需要想办法压缩URL的内存占用，可以使用BloomFilter算法，是一个很经典的算法，非常适用海量数据的排重过滤，占用极少的内存，查询效率也非常的高。...= BloomFilter(max_elements=100000000, error_rate=0.1) # 向bloom添加URL bloom.add('https://www.tianyancha.com...从上图也能看到，基本抓到120次左右就会被屏蔽，每隔6秒拨号其实误差比较大，因为网络延迟等各种问题，导致6秒内可能抓100次，也可能抓120次。
在 Python 中 URL 去重可以通过以下几个方式来实现： 将 URL 保存在集合 (set) 中，使用集合的特性来去重。 使用布隆过滤器来对 URL 去重。...使用集合进行 url 去重时，只需在每次需要爬取该 url 时判断该 url 是否在集合中，若不在获取网页信息并将该 url 放入集合中，若存在则跳过该 url 即可。...://list|item.szlcsc.+')): url = link.get('href') if url not in self.bloomfilter...__max_url_count: self.bloomfilter.add(url) self....在大多数场合我们使用集合来对 url 去重已经足够使用了，以一个 url 平均长度 100 字节来算，一千万条 url 使用集合进行去重所需要用到的内存空间不过也就是 1G，对现在的服务器或台式机来说应该不算太大的压力
接下来我们就将 BloomFilter 算法应用到 Scrapy-Redis 分布式爬虫的去重过程中，以解决 Redis 内存不足的问题。 3....，这样就成功利用 BloomFilter 替换了 Scrapy-Redis 的集合去重。...去重类，要使用 BloomFilter 请替换 DUPEFILTER_CLASS DUPEFILTER_CLASS = "scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter...亿 BLOOMFILTER_BIT = 30 DUPEFILTER_CLASS 是去重类，如果要使用 BloomFilter 需要将 DUPEFILTER_CLASS 修改为该包的去重类。...of ' + response.url) 在 start_requests() 方法中首先循环 10 次，构造参数为 0-9 的 URL，然后重新循环了 100 次，构造了参数为 0-99 的 URL
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
