`
cjnetwork
  • 浏览: 178859 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

web爬虫的广度优先算法

阅读更多
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;
    	}
    }
    





    分享到:
    评论
    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地址加入到地址池的最前面。

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

    深度索引
    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
    不知道深度优先有没有什么好的算法???



    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的方式判断重复效率上好不好?

    相关推荐

      基于广度优先算法的多线程网络爬虫本科论文.doc

      基于广度优先算法的多线程网络爬虫本科论文 以下是从给定的文件中生成的相关知识点: 一、计算机网络基础 * TCP/IP 协议族:TCP/IP 协议族是互联网的基础协议族,包括 TCP、UDP、广播等相关技术。 * 网络协议:...

      一个信息网络爬虫算法

      网络爬虫(Web Crawler),也被称作网络蜘蛛(Web ...随着Web爬虫技术的不断进步,新的算法和优化方法将不断涌现,以应对网络环境的变化和搜索需求的演进。因此,网络爬虫算法的研究是一个持续的、动态发展的领域。

      基于广度优先算法的多线程网络爬虫毕业(设计)论文.doc

      网络爬虫,又称为网络蜘蛛或Web爬虫,是自动化地从互联网上抓取信息的程序。它们通过遵循HTML链接来遍历网页,收集所需的数据。爬虫在搜索引擎优化、市场分析、新闻监测等领域具有重要应用。 【广度优先算法与多...

      基于web爬虫基本原理的新技术专题课程论文

      在当今信息化社会,网络数据的海量增长为信息获取带来了挑战,而Web爬虫作为自动提取网络信息的重要工具,对于数据挖掘、学术研究以及商业分析等领域具有重大价值。本篇论文旨在深入探讨基于Web爬虫的基本原理及其新...

      搜索引擎Web爬虫

      常见的有深度优先搜索(DFS)和广度优先搜索(BFS)。DFS会沿着某一条路径深入,直到尽头再返回;而BFS则先抓取一层的所有链接,再进入下一层。在实际应用中,BFS更常见,因为它能更好地保证网页的覆盖率。 **爬虫...

      java实现的爬虫算法 web版本的实现

      【Java实现的爬虫算法与Web版本的实现】 在信息技术领域,网络爬虫是一种自动提取网页数据的程序,广泛应用于搜索引擎、数据分析以及信息监控。Java作为一种广泛应用的编程语言,其强大的类库和跨平台特性使其成为...

      Python网络爬虫与推荐算法新闻推荐平台.zip

      网络爬虫:通过Python实现新浪新闻的爬取,可爬取新闻页面上的标题、文本、图片、视频链接(保留排版) 推荐算法:权重衰减+标签推荐+区域推荐+热点推荐 爬虫(Web Crawler)是一种自动化程序,用于从互联网上收集...

      heriterix爬虫与pagerank算法实现

      Heritrix是一款开源的Web爬虫工具,常用于大规模网页抓取,而PageRank是Google创始人拉里·佩奇提出的一种网页排名算法,它通过计算网页之间的链接关系来评估其重要性。在这个项目中,Heritrix爬虫被用来抓取网页并...

      基于Web的网络爬虫的设计与实现.pdf

      5. **遍历URL队列**:采用广度优先搜索算法遍历URL队列,确保每个链接都被访问一次。 为了提高效率,可以在多台高性能计算机上部署爬虫程序,实现并行工作。例如,每个节点运行多个爬虫实例,每个实例有自己的待...

      广域网分布式Web爬虫

      **广域网分布式Web爬虫概述** 广域网分布式Web爬虫是一种用于大规模网络数据抓取的技术,相较于局域网爬虫,它具有更广泛的数据覆盖能力、更高的爬取效率和更好的可扩展性。分布式爬虫通过将爬取任务分散到多个节点...

      广域网分布式Web爬虫.pdf

      此外,随着人工智能技术的发展,如何将深度学习等技术应用于Web爬虫中,也是未来研究的热点之一。通过这些技术,爬虫系统可能实现更高级的爬取策略和行为决策,以适应日益复杂的网络环境。 在实践方面,广域网...

      crawler spider web爬虫

      【标题】"Crawler Spider Web爬虫"是一个基于C++实现的网络爬虫项目,它旨在高效地抓取和处理互联网上的网页数据。在互联网的世界里,爬虫是一种自动化程序,能够按照一定的规则遍历网站,收集所需信息,是数据分析...

      智能Web算法书本代码

      比如,爬虫算法用于高效地获取网页信息,链接分析算法用于确定网页的重要性,而搜索排序算法则决定了用户在搜索结果中的看到的内容顺序。 3. **代码实践**:书中提供的"iWeb2"代码可能包含多种编程语言实现的智能...

      基于ID3分类算法的深度网络爬虫设计.pdf

      网络爬虫的工作机制通常是基于超链接的,即从一组初始URL出发,通过宽度优先或深度优先的方式递归地下载网页。然而,这种机制对于深度网络来说存在明显的局限性,因为它们无法识别和处理表单等非超链接元素。 #### ...

      [智能Web算法].(玛若曼尼斯).阿稳等.扫描版-带完整目录书签

      《智能Web算法》是一本深度探讨现代Web技术中核心算法的书籍,由玛若曼尼斯与阿稳等专家合著。这本书旨在为读者提供全面的Web智能算法理解,包括推荐系统、搜索引擎、网络爬虫、数据聚类以及分类器等多个重要领域的...

      C# 网络爬虫-做了算法优化和连接优化

      - **深度优先搜索(DFS)与广度优先搜索(BFS)**:根据目标选择合适的遍历策略,DFS适合深度挖掘,BFS适合获取全局信息。 4. **连接优化**: - **连接池管理**:使用连接池可以复用已建立的连接,减少建立新连接的...

      爬虫技术在大数据领域中的应用分析.pdf

      当前,应用最广泛的爬虫算法主要有三种:深度优先算法、广度优先算法和最佳优先算法。 - 深度优先算法从起始网页出发,选择URL后进入分析阶段,逐步完成线路的处理,对于门户网站的影响较大。 - 广度优先算法在当前...

      网络爬虫简介ppt课件.ppt

      网络爬虫的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题,目前常见的是广度优先和最佳优先方法。广度优先搜索策略是指在抓取过程中,在完成当前层次的...

    Global site tag (gtag.js) - Google Analytics