在爬虫系统中,在内存中维护着两个关于URL的队列,ToDo队列和Visited队列,ToDo队列存放的是爬虫从已经爬取的网页中解析出来的即将爬取的URL,但是网页是互联的,很可能解析出来的URL是已经爬取到的,因此需要VIsited队列来存放已经爬取过的URL。当爬虫从ToDo队列中取出一个URL的时候,先和Visited队列中的URL进行对比,确认此URL没有被爬取后就可以下载分析来。否则舍弃此URL,从Todo队列取出下一个URL继续工作。
然后,我们知道爬虫在爬取网页时,网页的量是比较大的,直接将所有的URL直接放入Visited队列是很浪费空间的。因此引入bloom filter!
(关于使用bloomfilter的原因:
visited队列中url过多,消耗内存空间是一方面。还有一个重要的原因,在从todo队列中取出一个新的URL时,必须和 visited中所有URL比较,确保没有处理过。那么如果直接比较的话,是要比较N(visited中所有url个数)次的,而且这个N相当大,效率明 显不够。采用bloom filter,最多只要比较K(我在文章中写的,相互独立的散列函数的个数)次,因为只要一个散列函数的散列值对应的位是0,就可以确定这个URL没有处 理过。
)
我们把bloom filer设置为m个bit,全部初始为0。
对每一个URL,进行K(K<m)次相互独立的哈希,一共得到K个值,将这K个值在bloom filter中对应的bit位置1。
经过上述处理的bloom filter实际上构成了我们所说的Visited队列,当我们从ToDo队列中取出一个新的URL时,同样,进行相同的K次哈希,每进行一次哈希,查看bloom filter中对应位,只要发现某位是0,就可以确定这个URL是没有处理过的,可以继续下载处理。
那么,原理清楚之后,还有几个问题没有解决。
1、bloom filter是有可能发生错误的,因为不处理碰撞,也就是说,有可能把不属于这个集合的元素误认为属于这个集合
错误率的计算:
在n个URL都进行k次散列加入之后,bloomfilter中某位是0的概率
错误率(即一个新的URL恰好k次散列的值对应的位都已经是1的概率)
2、哈希函数个数K的确定
k = ln2· (m/n)时(具体数学分析见http://blog.csdn.net/jiaomeng/article/details/1495500)
3、bloomfilter位数M的确定
我们可以想到,M的大小越大,错误率就会越小,但是数学证明给出了一个下界。即M = log2 e N = 1.44N。
附上java代码
/**屈永泉 布隆过滤器 快速确定哪些网页已经被下载过*/ package crawler; import java.util.BitSet; public class BloomFilter {
private int defaultSize = << ;
private int basic = defaultSize - ;
private BitSet bits = new BitSet(defaultSize); private int[] lrandom(String key) { // 产生八个随机数并返回
int[] randomsum = new int[];
for (int i = ; i < ; i++)
randomsum[] = hashCode(key, i + );
return randomsum;
} // 将一个URL加入
public synchronized void add(String key) {
int keyCode[] = lrandom(key);
for (int i = ; i < ; i++)
bits.set(keyCode[i]); // 将指定索引处的位设置为 true
}
} // 判断一个URL是否存在
public boolean exist(String key) {
int keyCode[] = lrandom(key);
if (bits.get(keyCode[])
&& bits.get(keyCode[]) // 返回指定索引处的位值。
&& bits.get(keyCode[]) && bits.get(keyCode[])
&& bits.get(keyCode[]) && bits.get(keyCode[])
&& bits.get(keyCode[]) && bits.get(keyCode[])) {
return true;
}
return false;
} private int hashCode(String key, int Q) {
int h = ;
int off = ;
char val[] = key.toCharArray(); // 将此URl转换为一个新的字符数组
int len = key.length();
for (int i = ; i < len; i++) {
h = ( + Q) * h + val[off++];
}
return basic & h;
} /* public static void main(String[] args) { // TODO Auto-generated method
long pre = 0;
long post = 0;
pre = System.nanoTime();
BloomFilter f = new BloomFilter(); //初始化
f.add("http://www.agrilink.cn/"); f.add("http://www.baidu.com/");
System.out.println(f.exist("http://www.baidu.com/"));
System.out.println(f.exist("http://www.baidud.com/"));
post = System.nanoTime();
System.out.println("Time: " + (post - pre)); }
*/ }
爬虫技术之——bloom filter(含java代码)的更多相关文章
-
golang学习笔记17 爬虫技术路线图,python,java,nodejs,go语言,scrapy主流框架介绍
golang学习笔记17 爬虫技术路线图,python,java,nodejs,go语言,scrapy主流框架介绍 go语言爬虫框架:gocolly/colly,goquery,colly,chrom ...
-
十大经典排序算法最强总结(含JAVA代码实现)(转)
十大经典排序算法最强总结(含JAVA代码实现) 最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每 ...
-
十大经典排序算法最强总结(含JAVA代码实现)
最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每个桶进行排序直接使用了Collection.sort ...
-
JAVA十大经典排序算法最强总结(含JAVA代码实现)
十大经典排序算法最强总结(含JAVA代码实现) 最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每 ...
-
百度语音识别REST API用法(含JAVA代码)——不须要集成SDK的方法
版权声明:本文为博主原创文章,未经博主同意不得转载. https://blog.csdn.net/zpf8861/article/details/32329457 上一篇文章http://blog.c ...
-
十大经典排序算法详细总结(含JAVA代码实现)
原文出处:http://www.cnblogs.com/guoyaohua/p/8600214.html 0.排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序. 0.2 术语说明 ...
-
JAVA十大经典排序算法最强总结(含JAVA代码实现)
0.排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序. 0.2 术语说明 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面: 不稳定:如果a原本在b的前面,而a=b,排 ...
-
Bloom Filter:海量数据的HashSet
Bloom Filter一般用于数据的去重计算,近似于HashSet的功能:但是不同于Bitmap(用于精确计算),其为一种估算的数据结构,存在误判(false positive)的情况. 1. 基本 ...
-
十大经典排序算法最强总结(含Java、Python码实现)
引言 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.排序算法,就是如何使得记录按照要求排列的方法.排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面 ...
随机推荐
-
浅谈iOS开发中方法延迟执行的几种方式
Method1. performSelector方法 Method2. NSTimer定时器 Method3. NSThread线程的sleep Method4. GCD 公用延迟执行方法 - (vo ...
-
2016,Raym
Hello,2016: 这是承上启下的一年! Raym
-
(Builder)创建者模式
定义: 建造模式:将一个复杂对象的构建与他的表示相分离,使得同样的构建过程可以创建不同的表示. 适用性: 当流程算法可以固定几个步骤,步骤的算法步骤执行顺序固定,且制造的产品可以唯一确定,这时使用创建 ...
-
通过登入IP记录Linux所有用户登录所操作的日志
通过登入IP记录Linux所有用户登录所操作的日志 对于Linux用户操作记录一般通过命令history来查看历史记录,但是如果在由于误操作而删除了重要的数据的情况下,history命令就不会有什么作 ...
-
linux jdk bin安装
1.jdk-1_5_0_06-linux-i586.bin下载到/usr/soft,赋予可执行权限:chmod 755jdk-1_5_0_06-linux-i586.bin 2.执行:./jdk-1_ ...
-
oracle 行转列 分析函数
oracle 行转列 首先看一下源数据: 方法一:WM_CONCAT group by 这个方法没有问题. SELECT CODE_TS, WMSYS.WM_CONCAT(S_NUM + || ':' ...
-
XCOPY: Access denied
用 XCOPY 拷贝文件,出现 “Access denied” 提示信息. 原因: 在如上拷贝的目标路径下,存在 ReadMe.txt, 并且是 只读 文件,这种情况下,需要增加一个 拷贝选项: /R ...
-
CKfinder中文乱码的解决.
最近在写一个类似博客的系统,使用了ckeditor和ckfinder,但是发现ckfinder在上传中文文件名的文件过程中会出现中文乱码的情况. 于是百度google乎,发现大多数的解决办法都是将文件 ...
-
黄聪:JQUERY判断操作CHECKBOX选中、取消选中、反选、第二次无法选中的问题
用JQuery做CheckBox全选和反选的时候,遇到一个问题.当用JQ控制全选,全取消一次以后,再次点击全选,发现代码变了,但是CheckBox没有处于选中状态. $("#id" ...
-
JVM各垃圾收集器对比
本随笔是<深入理解Java虚拟机 JVM高级特性与最佳实践>读书笔记. 1.JDK1.7之后的HotSpot虚拟机所包含的所有收集器如下: 解读: 1. 总共有7种垃圾收集器 2.Seri ...