web爬虫的广度优先算法

web爬虫中需要设计一个广度优先的算法，以控制爬虫爬行网址的先后顺序，这里用一个链表实现，用链表是因为链表的插入速度够快。

设计思路：
1、取下一个地址：从链表的头部取出一个，并将头部元素删除
2、加入地址池：将URL地址加入到适当的位置

   为了保证加入的时候能够加入到合适的地址，最容易想到的办法就是遍历那个地址池，但遍历的效率确实不高，当地址池中数量增大的时候，消耗在遍历上的cpu资源过多，导致爬行效率降低。还有一种方法就是记录每一个深度的URL地址的最后一个元素在地址池中索引，当加入的时候就不需要遍历地址池，只需通过需要加入的URL地址，找到同级URL地址在地址池中的索引，然后加入到地址池中，加入位置为这个索引的后面一个，并且更新索引表，当然如果没有找到同级别的索引，这依次找上一级的索引，若在回溯的过程中，都没有找到，这可以确定索引为0，即将该URL地址加入到地址池的最前面。

下面是一个索引表内容变化的例子：

深度	索引
2	5
3	6

当加入一个这样的URL地址(new URL(1,"http://www.sina.com.cn"))之后

深度	索引
1	1
2	6
3	7

当加入一个这样的URL地址(new URL(2,"http://www.baidu.cn"))之后

深度	索引
1	1
2	7
3	8

当加入一个这样的URL地址(new URL(4,"http://tieba.baidu.cn"))之后

深度	索引
1	1
2	7
3	8
4	9

实现的核心代码(代码不完整，无下载及url地址提取等)

Crawler.java

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


public class Crawler {

	private List<Url> uncrawedUrl = new LinkedList<Url>();// 待爬行网址集合

	private Map<String, Url> urls = new HashMap<String, Url>(10000);// 去重网址集合，防止重复爬

	private Map<Integer, Integer> urlsIndexPointor = new HashMap<Integer, Integer>();//索引表

	
	/**
	 * 
	 * 将URL地址添加到未采集池
	 * 
	 * 
	 * @param url
	 * @return
	 */
	private boolean addUrlToPool(Url url) {
		boolean result = false;
		try {
			if (!urls.containsKey(url.getUrl())) {
				int index = 0;//默认为0，当下面的搜索过程没有找到index的时候
				for (int i = 0; url.getDepth() - i > 0; i++) {// 从索引表中寻找需要插入的位置
					if (urlsIndexPointor.containsKey(url.getDepth() - i)) {
						index = urlsIndexPointor.get(url.getDepth() - i) + 1;
						break;
					}
				}

				uncrawedUrl.add(index, url);
				urlsIndexPointor.put(url.getDepth(), index);
				urls.put(url.getUrl(), url);
				
				//更新索引表(这个表的内容不会扩展很大，因此遍历效率可以忽略)
				Iterator<Entry<Integer, Integer>> iter = urlsIndexPointor.entrySet().iterator();
				while (iter.hasNext()) {
					Entry<Integer, Integer> entry = iter.next();
					if (entry.getKey() > url.getDepth()) {
						entry.setValue(entry.getKey() + 1);
					}
				}
				
				result = true;
			}
		} catch (Exception e) {			
			e.printStackTrace();
		}
		return result;
	}
	
	
	/**
	 * 
	 * 从URL池中取出一条未爬去过的地址
	 * 
	 * 
	 * @return 没有则返回null
	 */
	private Url getUrlFromPool() {
		Url result = null;
		if (uncrawedUrl.size() > 0) {
			result = uncrawedUrl.get(0);
			uncrawedUrl.remove(0);
			
			// 更新索引表，将所有的位置指针向前移动一位
			Iterator<Entry<Integer, Integer>> iter = urlsIndexPointor.entrySet().iterator();
			while (iter.hasNext()) {
				Entry<Integer, Integer> entry = iter.next();
				if (entry.getValue() == 0) {
					iter.remove();
				}
				entry.setValue(entry.getValue() - 1);
			}			

		}		
		return result;
	}
}

Url.java

class Url {
	private int depth;
	private String url;

	public int getDepth() {
		return depth;
	}

	public String getUrl() {
		return url;
	}

	public void setDepth(int depth) {
		this.depth = depth;
	}

	public void setUrl(String url) {
		this.url = url;
	}
}

评论

8 楼 cjnetwork 2010-12-13  

haolei92 写道

楼主是否是专门做web爬虫设计的

不是，偶尔看看别的技术。。。 
人不学要落后啊。。。

7 楼 haolei92 2010-12-13  

楼主是否是专门做web爬虫设计的

6 楼 cjnetwork 2010-12-13  

by5739 写道

哎..没弄过web爬虫..不太明白为什么这样弄...我的意思是..如果用10个List分别装1-10级的url...是不是也可以?

爬行深度是不固定的，不是简单的10或简单的是100，有的时候从一个爬行种子开始不到深度10就结束了，那开10个list就不合适，如果有的时候从一个爬行种子开始不止10个深度，那么开10个list就不够。。。

5 楼 by5739 2010-12-13  

哎..没弄过web爬虫..不太明白为什么这样弄...我的意思是..如果用10个List分别装1-10级的url...是不是也可以?

4 楼 cjnetwork 2010-12-12  

chaoren3166 写道

注：urls可以声明成一个Set。
不知道深度优先有没有什么好的算法？？？

urls之所以定义为一个map，是因为例子中的Url类目前只有两个属性，如果扩展Url类的属性，在爬取过程中需要对实例化的Url对象有一定的操作，可以方便快速的通过map定位到Url对象

至于深度优先，个人觉得在爬虫系统中不是一个好的策略。要实现，似乎不需要要控制加入uncrawedUrl中的顺序，只要将找的url地址直接加入到列表uncrawedUrl的最后，就是实现的深度优先了。

3 楼 chaoren3166 2010-12-12  

cjnetwork 写道

web爬虫中需要设计一个广度优先的算法，以控制爬虫爬行网址的先后顺序，这里用一个链表实现，用链表是因为链表的插入速度够快。

设计思路：
1、取下一个地址：从链表的头部取出一个，并将头部元素删除。
2、加入地址池：将URL地址加入到适当的位置。

   为了保证加入的时候能够加入到合适的地址，最容易想到的办法就是遍历那个地址池，但遍历的效率确实不高，当地址池中数量增大的时候，消耗在遍历上的cpu资源过多，导致爬行效率降低。还有一种方法就是记录每一个深度的URL地址的最后一个元素在地址池中索引，当加入的时候就不需要遍历地址池，只需通过需要加入的URL地址，找到同级URL地址在地址池中的索引，然后加入到地址池中，加入位置为这个索引的后面一个，并且更新索引表，当然如果没有找到同级别的索引，再依次找上一级的索引，若在回溯的过程中，都没有找到，这可以确定索引为0，即将该URL地址加入到地址池的最前面。

下面是一个索引表内容变化的例子：

深度	索引
2	5
3	6

当加入一个这样的URL地址(new URL(1,"http://www.sina.com.cn"))之后

深度	索引
1	1
2	6
3	7

当加入一个这样的URL地址(new URL(2,"http://www.baidu.com"))之后

深度	索引
1	1
2	7
3	8

当加入一个这样的URL地址(new URL(4,"http://tieba.baidu.cn"))之后

深度	索引
1	1
2	7
3	8
4	9

实现的核心代码(代码不完整，无下载及url地址提取等)

Crawler.java

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


public class Crawler {

	private List<Url> uncrawedUrl = new LinkedList<Url>();// 待爬行网址集合

	private Map<String, Url> urls = new HashMap<String, Url>(10000);// 去重网址集合，防止重复爬

	private Map<Integer, Integer> urlsIndexPointor = new HashMap<Integer, Integer>();//索引表

	
	/**
	 * 
	 * 将URL地址添加到未采集池
	 * 
	 * 
	 * @param url
	 * @return
	 */
	private boolean addUrlToPool(Url url) {
		boolean result = false;
		try {
			if (!urls.containsKey(url.getUrl())) {
				int index = 0;//默认为0，当下面的搜索过程没有找到index的时候
				for (int i = 0; i < url.getDepth(); i++) {// 从索引表中寻找需要插入的位置
					if (urlsIndexPointor.containsKey(url.getDepth() - i)) {
						index = urlsIndexPointor.get(url.getDepth() - i) + 1;
						break;
					}
				}

				uncrawedUrl.add(index, url);
				urlsIndexPointor.put(url.getDepth(), index);
				urls.put(url.getUrl(), url);
				
				//更新索引表(这个表的内容不会扩展很大，因此遍历效率可以忽略)
				Iterator<Entry<Integer, Integer>> iter = urlsIndexPointor.entrySet().iterator();
				while (iter.hasNext()) {
					Entry<Integer, Integer> entry = iter.next();
					if (entry.getKey() > url.getDepth()) {
						entry.setValue(entry.getKey() + 1);
					}
				}
				
				result = true;
			}
		} catch (Exception e) {			
			e.printStackTrace();
		}
		return result;
	}
	
	
	/**
	 * 
	 * 从URL池中取出一条未爬去过的地址
	 * 
	 * 
	 * @return 没有则返回null
	 */
	private Url getUrlFromPool() {
		Url result = null;
		if (uncrawedUrl.size() > 0) {
			result = uncrawedUrl.get(0);
			uncrawedUrl.remove(0);
			
			// 更新索引表，将所有的位置指针向前移动一位
			Iterator<Entry<Integer, Integer>> iter = urlsIndexPointor.entrySet().iterator();
			while (iter.hasNext()) {
				Entry<Integer, Integer> entry = iter.next();
				if (entry.getValue() == 0) {
					iter.remove();
				}
				entry.setValue(entry.getValue() - 1);
			}			

		}		
		return result;
	}
}

Url.java

class Url {
	private int depth;
	private String url;

	public int getDepth() {
		return depth;
	}

	public String getUrl() {
		return url;
	}

	public void setDepth(int depth) {
		this.depth = depth;
	}

	public void setUrl(String url) {
		this.url = url;
	}
}

注：urls可以声明成一个Set。
不知道深度优先有没有什么好的算法？？？

2 楼 cjnetwork 2010-12-12  

javabkb 写道

请教楼主,用将list转map的方式判断重复效率上好不好?

   这个方法并没有将list转换为map，两个容器的用处各不相同，list用于从未爬取的url地址中取出爬行深度最浅的一个，而map（urls这个map）的作用是用于验证url地址是否已被加入采集计划或是否已完成的采集计划。若要说有效率问题，就是有map的方法containsKey方法有一定的效率问题。

1 楼 javabkb 2010-12-12  

请教楼主,用将list转map的方式判断重复效率上好不好?