网站更改指定字段,长沙建网站公司,关于做美食的小视频网站,dw做的网站有域名么在爬虫系统中#xff0c;在内存中维护着两个关于URL的队列#xff0c;ToDo队列和Visited队列#xff0c;ToDo队列存放的是爬虫从已经爬取的网页中解析出来的即将爬取的URL#xff0c;但是网页是互联的#xff0c;很可能解析出来的URL是已经爬取到的#xff0c;因此需要VI…在爬虫系统中在内存中维护着两个关于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经过上述处理的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 log2eN 1.44N。附上java代码1 /**屈永泉 布隆过滤器 快速确定哪些网页已经被下载过*/23 package crawler;45 import java.util.BitSet;67 public classBloomFilter {8 private int defaultSize 5000 10000;9 private int basic defaultSize - 1;10 private BitSet bits newBitSet(defaultSize);1112 private int[] lrandom(String key) { //产生八个随机数并返回13 int[] randomsum new int[8];14 for (int i 0; i 8; i)15 randomsum[0] hashCode(key, i 1);16 returnrandomsum;17 }1819 //将一个URL加入20 public synchronized voidadd(String key) {21 int keyCode[] lrandom(key);22 for (int i 0; i 8; i)23 bits.set(keyCode[i]); //将指定索引处的位设置为 true24 }25 }2627 //判断一个URL是否存在28 publicboolean exist(String key) {29 int keyCode[] lrandom(key);30 if (bits.get(keyCode[0])31 bits.get(keyCode[1]) //返回指定索引处的位值。32 bits.get(keyCode[2]) bits.get(keyCode[3])33 bits.get(keyCode[4]) bits.get(keyCode[5])34 bits.get(keyCode[6]) bits.get(keyCode[7])) {35 return true;36 }37 return false;38 }394041 private int hashCode(String key, intQ) {42 int h 0;43 int off 0;44 char val[] key.toCharArray(); //将此URl转换为一个新的字符数组45 int len key.length();46 for (int i 0; i len; i) {47 h (30 Q) * h val[off];48 }49 return basic h;50 }515253 /*public static void main(String[] args) { // TODO Auto-generated method54 long pre 0;55 long post 0;56 pre System.nanoTime();57 BloomFilter f new BloomFilter(); //初始化58 f.add(http://www.agrilink.cn/); f.add(http://www.baidu.com/);59 System.out.println(f.exist(http://www.baidu.com/));60 System.out.println(f.exist(http://www.baidud.com/));61 post System.nanoTime();62 System.out.println(Time: (post - pre));6364 }65 */6667 }View Code
