/**
* 如何不采集重复的网页?去重可以使用布隆过滤器,每个线程使用一个bitarray,
* 里面保存本批源页面上次抓取的页面的哈希值情况,抓取下来的源页面分析链接后,
* 去这个bitarray里判断以前有没有抓过这个页面,没有的话就抓下来,抓过的话就不管了。
* 假设一个源页面有30个链接,一批10W个源页面,300w个链接的bitarray应该也不会占太大内存。
* 所以有个五六个线程同时处理也是没问题的。
* **/
public class SimpleBloomFilter {
private static final int DEFAULT_SIZE = 2 << 24;
private static final int[] seeds = new int[] { 7, 11, 13, 31, 37, 61, };
private BitSet bits = new BitSet(DEFAULT_SIZE);
private SimpleHash[] func = new SimpleHash[seeds.length];
public SimpleBloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
public static void main(String[] args) {
String value = "stone2083@yahoo.cn";
SimpleBloomFilter filter = new SimpleBloomFilter();
System.out.println(filter.contains(value));
filter.add(value);
System.out.println(filter.contains(value));
}
// 覆盖方法,把URL添加进来
public void add(CrawlUrl value) {
if (value != null)
add(value.getOriUrl());
}
// 覆盖方法,把URL添加进来
public void add(String value) {
for (SimpleHash f : func)
bits.set(f.hash(value), true);
}
// 覆盖方法,是否包含URL
public boolean contains(CrawlUrl value) {
return contains(value.getOriUrl());
}
// 覆盖方法,是否包含URL
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
}
分享到:
相关推荐
什么是『布隆过滤器』 布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某个 URL 爬虫是否宠幸过?...
针对双结构网络的特点及其URL去重面临的挑战,根据Bloom Filter的工作原理,提出一种基于可扩展的动态可分裂Bloom Filter的URL去重机制,并在原型系统中进行实现和部署。实验结果表明,该机制能够有效适用于大规模、高...
scrapy使用布隆过滤器实现增量爬取 之前看了很多关于scrapy-redis使用bloomfilter进行持久化存储进行url去重的例子,可是发现没有一种适用于scrapy,于是萌生了基于现有scrapy-redis-bloomfilter库进行改写的想法。 ...
本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器。 应用场景 1、50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog) 2、新闻客户端看...
3.URL去重采用布隆过滤器方案。 4.可以处理不完整的HTML,Scrapy已经提供了selectors(一个在lxml的基础上提供了更高级的接口), 可以高效地处理不完整的HTML代码。 pyspider 是一个用python实现的功能强大的...
* 布隆过滤器的实现要求:位数组、哈希函数、均匀的随机分布、哈希冲突低 * 布隆过滤器的添加元素:将要添加的元素给k个哈希函数,得到对应于位数组上的k个位置,将这k个位置设为1 四、爬虫反爬虫策略及应对措施 *...
在学校的时候和同学写的c语言网络爬虫,利用Libevent+nanomsg实现网页爬取和模块通信,利用DFA提取网页中的url,通过布隆过滤器对爬取的网页做url去重,过滤无效url,对url做绝对路径化处理 包含实验报告,有具体的...
为避免重复爬取新闻,设置布隆过滤器去重。由于每篇新闻的URL在网站中是唯一的,而URL中特定的数字串也是唯一的。因此将该数字串作为每篇新闻的id。每爬取一篇新闻前,先将其通过布隆过滤器检查该id是否存在,若...
让scrapy带上布隆过滤器基于settings.py -> DUPEFILTER_CLASS 配置实现1.只实现去重(BloomFilterRedis文件夹、BloomFilterRedis_ex文件夹)实现的功能仅为利用redis实现去重,不能实现增量效果,适用于代爬取链接规律...
crawler_parallel make后执行:./crawler服务器ip地址扩展号url.txt
C语言并行爬虫(epoll),爬取服务器的16W个有效网页,通过爬取页面源代码进行确定性自动机匹配和布隆过滤器去重,对链接编号并写入url.txt文件,并通过中间文件和三叉树去除掉状态码非200的链接关系,因为匹配出来...
爬虫相关知识代码 读书笔记《自己动手写网络...SimpleBloomFilter 布隆过滤器 BDBFrontier 使用Berkeley DB 来做爬虫的前端url爬取列表存储 Crawler 爬虫一只,采用了宽度优先的方式爬取网络,并且使用httpclien4.3来
2.2.2. 布隆过滤器(BloomFilter) 基于布隆算法,对欲加入队列的原始统一资源定位符进行过滤,以防止已被抓 取过的URL再次入队,降低冗余开销同时避免无限循环。 2.2.3. 原始统一资源定位符(RawUrl) 提供原始形态的...
知乎上有详细一点的介绍,如有需要请移步: ://zhuanlan.zhihu.com/p/146265932 1,数据去重问题全部的数据前期是采用布隆过滤器进行去重的,但后来发现并不需要这么麻烦,后用了一个小技巧进行去重。因为每个商品是...