论坛首页 Java企业应用论坛

web爬虫的广度优先算法

浏览 8187 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2010-12-10   最后修改:2010-12-12
web爬虫中需要设计一个广度优先的算法,以控制爬虫爬行网址的先后顺序,这里用一个链表实现,用链表是因为链表的插入速度够快。

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

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

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

深度索引
25
36

当加入一个这样的URL地址(new URL(1,"http://www.sina.com.cn"))之后
深度索引
11
26
37

当加入一个这样的URL地址(new URL(2,"http://www.baidu.cn"))之后
深度索引
11
27
38

当加入一个这样的URL地址(new URL(4,"http://tieba.baidu.cn"))之后
深度索引
11
27
38
49




实现的核心代码(代码不完整,无下载及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;
    	}
    }
    





       发表时间:2010-12-12   最后修改:2010-12-12
    请教楼主,用将list转map的方式判断重复效率上好不好?
    0 请登录后投票
       发表时间:2010-12-12  
    javabkb 写道
    请教楼主,用将list转map的方式判断重复效率上好不好?

       这个方法并没有将list转换为map,两个容器的用处各不相同,list用于从未爬取的url地址中取出爬行深度最浅的一个,而map(urls这个map)的作用是用于验证url地址是否已被加入采集计划或是否已完成的采集计划。若要说有效率问题,就是有map的方法containsKey方法有一定的效率问题。
    0 请登录后投票
       发表时间:2010-12-12  
    cjnetwork 写道
    web爬虫中需要设计一个广度优先的算法,以控制爬虫爬行网址的先后顺序,这里用一个链表实现,用链表是因为链表的插入速度够快。

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

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

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

    深度索引
    25
    36

    当加入一个这样的URL地址(new URL(1,"http://www.sina.com.cn"))之后
    深度索引
    11
    26
    37

    当加入一个这样的URL地址(new URL(2,"http://www.baidu.com"))之后
    深度索引
    11
    27
    38

    当加入一个这样的URL地址(new URL(4,"http://tieba.baidu.cn"))之后
    深度索引
    11
    27
    38
    49




    实现的核心代码(代码不完整,无下载及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
    不知道深度优先有没有什么好的算法???



    0 请登录后投票
       发表时间:2010-12-12  
    chaoren3166 写道


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



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

    至于深度优先,个人觉得在爬虫系统中不是一个好的策略。要实现,似乎不需要要控制加入uncrawedUrl中的顺序,只要将找的url地址直接加入到列表uncrawedUrl的最后,就是实现的深度优先了。
    0 请登录后投票
       发表时间:2010-12-13  
    哎..没弄过web爬虫..不太明白为什么这样弄...我的意思是..如果用10个List分别装1-10级的url...是不是也可以?
    0 请登录后投票
       发表时间:2010-12-13  
    by5739 写道
    哎..没弄过web爬虫..不太明白为什么这样弄...我的意思是..如果用10个List分别装1-10级的url...是不是也可以?


    爬行深度是不固定的,不是简单的10或简单的是100,有的时候从一个爬行种子开始不到深度10就结束了,那开10个list就不合适,如果有的时候从一个爬行种子开始不止10个深度,那么开10个list就不够。。。
    0 请登录后投票
       发表时间:2010-12-13  
    楼主是否是专门做web爬虫设计的
    0 请登录后投票
       发表时间:2010-12-13  
    haolei92 写道
    楼主是否是专门做web爬虫设计的


    不是,偶尔看看别的技术。。。 
    人不学要落后啊。。。
    0 请登录后投票
    论坛首页 Java企业应用版

    跳转论坛:
    Global site tag (gtag.js) - Google Analytics