实测可用的宽度优先爬虫的实现

参考文献：自己动手写网络爬虫，罗刚，王振东著（我感觉这本书对我还是蛮有用的，爬虫大杂烩啊）

前面写了一篇利用HttpClient来获取单个网页的灌水文，现在希望在此基础之上可以通过一个种子网页能够爬更多的相关网页。

由于互联网的页面上都是相互链接的，可以看成一个超级大的图，每个页面都可以看成是一个节点，而页面中的链接可以看成是图的有向边。

因此能够通过遍历的方式对互联网这个超级大的图进行访问。

突然就把很具体的问题用数据结构抽象的方法给表述出来的了，果然还是抽象牛叉。

图的遍历常可以分为宽度优先遍历和深度优先遍历两种方式。

大多数网络爬虫都是通过宽度优先的方式爬取，爬得太深了反而不太好。

图的宽度优先遍历

图的宽度优先遍历是一个分层搜索的过程，和树的层序遍历算法相同。

从图中选中一个节点，作为起始节点，然后按照层次遍历的方式，一层一层的访问。

首先需要一个队列作为保存当前节点的子节点的数据结构。

1. 顶点V入队列
2. 当队列非空时继续执行，否则停止计算
3. 出队列，获得队头节点V，访问顶点V并标记V已经被访问
4. 查找顶点V的第一个邻接顶点col
5. 若V的邻接顶点col未被访问过，则col进队列
6. 继续查找V的其他邻接顶点col，转到步骤5，如果V的所有邻接顶点都已经被访问过，则转到步骤2

下图是一个待遍历的图，看看这个图通过宽度优先是如何遍历的？

这里如果以A为种子节点的话，

A进队列

A出队列

A的子节点为：BCDEF，进队列

B出队列，由于B没有子节点，所以没有节点入队列，剩下CDEF

同理C和D由于没有子节点，也都出队列了，剩下EF

E出队列，队列中还剩下F

E的子节点H入队列，队列中还剩下FH

F，出队列，队列中还剩下H

F的子节点G入队列，还剩下HG

H出队列，还剩下G

H的子节点I入队列，还剩下GI

G出队列，还剩下I

I出队列，队列为空，遍历结束

遍历顺序为A->B->C->D->E->F->H->G->I

层次遍历的示意图如下图

宽度优先爬虫过程

在网页中如果HTML文档中存在超链接，那么这些超链接所指向的网页可以看成是该网页的子节点，

而那些不是指向HTML文档的超链接则可以看成是终端，它们是没有子节点的。

爬虫的种子几点也可以有多个。

整个宽度优先爬虫的过程就是从一些列的种子节点开始，把这些网页中的子节点（超链接）提取出来，放入队列中依次进行抓去。

被处理过的超链接需要放入到一张表中（visited表中）。每次在处理一个新的链接之前都要查看是否已经存在于visited表中。

如果存在则证明链接已经处理过，跳过不作处理，否则进行下一步处理。

初始的URL地址是作为爬虫系统的种子URL（一般在配置文件中指定）

然后解析这个URL，产生新的URL

爬虫过程为：

1. 把解析出的链接和Visited表中的链接进行比较，若Visited表中不存在此链接，表示其未被访问过；
2. 把链接放入到TODO表中；
3. 处理完毕后，再次从TODO列表中取出一条链接，直接放入到Visited列表中；
4. 针对这个链接所表示的网页，继续上述过程，如此循环。

宽度优先爬虫的好处

• 重要的网页往往离种子比较近，随着不断的深入网页的重要性越来越低；
• 万维网的实际深度最多能达到17层，但到达某个网页总存在一条很近的路径，而宽度优先能以最快的速度到达这个网页；
• 宽度优先有利于多爬虫合作抓取，多爬虫合作通常先抓取网站内的链接

宽度优先爬虫实现

具体流程如下：

涉及到四个类

Queue类：用于保存将要访问的URL

LinkQueue类：保存以访问的URL，并判断给定的URL是否被访问过

DownLoadFile类：下载给定的URL指向的网页，以及进行一些列设置

HtmlParserTool类：对已获取的HTML页面进行处理，用来过滤链接，获得新的链接

MyCrawler类：爬虫的主程序

书上给的代码用的HttpClient搞不清楚是哪个版本的，然后码了字之后也执行不了，各种出错，主要好似HttpClient这个类中方法变动太大。

Queue类：用于保存将要访问的URL

package com.abc.bfs;
import java.util.LinkedList;
import java.util.Scanner;

//用链表实现队列
public class Queue {
	//realize queue with linklist
	private LinkedList<String> queue = new LinkedList<String>();
	//入队列
	public void enQueue(String t) {
		queue.add(t);
	}
	//出队列
	public Object deQueue() {
		return queue.removeFirst();
	}
	//判断队列是否为空
	public boolean isQueueEmpty() {
		return queue.isEmpty();
	}
	//判断队列是否包含t
	public boolean contains(String t) {
		return queue.contains(t);
	}

	//用于测试这个类
	public static void main(String[] args) {
		Queue qqq = new Queue();
		Scanner sc = new Scanner(System.in);
		System.out.println("[0] Input a object to Queue: ");
		System.out.println("[1] Output a object from Queue: ");
		System.out.println("[2] Test a object in or not in Queue: ");
		System.out.println("[3] If the Queue is empty: ");
		System.out.println("[4] Exit!"); 
		System.out.print("Enter a number: ");
		int opt = sc.nextInt();
		while (true) {
			switch (opt) {
				case 0: {
					System.out.print("[0] Input a object to Queue: ");
					sc = new Scanner(System.in);
					String a = sc.nextLine();
					qqq.enQueue(a);
					break;
				}
				case 1: {
					System.out.print("[1] Output a object from Queue: ");
					String a = (String)qqq.deQueue();
					System.out.println(a);
					break;
				}
				case 2: {
					System.out.print("[2] Test a object in or not in Queue: ");
					sc = new Scanner(System.in);
					String a = sc.nextLine();
					if (qqq.contains(a))
						System.out.print("true");
					else
						System.out.print("false");
					break;
				}
				case 3: { 
					System.out.println("[3] If the Queue is empty: ");
					if (qqq.isQueueEmpty())
						System.out.print("true");
					else
						System.out.print("false");
					break;
				}
				case 4: return;
			}
			System.out.println("[0] Input a object to Queue: ");
			System.out.println("[1] Output a object from Queue: ");
			System.out.println("[2] Test a object in or not in Queue: ");
			System.out.println("[3] If the Queue is empty: ");
			System.out.println("[4] Exit!"); 
			System.out.print("Enter a number: ");
			sc = new Scanner(System.in);
			opt = sc.nextInt();
		}	
	}
}

LinkQueue类：保存以访问的URL，并判断给定的URL是否被访问过

package com.abc.bfs;
import java.util.HashSet;
import java.util.Set;
public class LinkQueue {
	//collection of used URL
	private static Set<String> visitedUrl = new HashSet<String>();
	//collection of ready-to-visit URL
	private static Queue unVisitedUrl = new Queue();
	//get queue of URL
	public static Queue getUnVisitedUrl() {
		return unVisitedUrl;
	}
	//add the visited URL
	public static void addVisitedUrl(String url) {
		visitedUrl.add(url);
	}
	//remove visited URL
	public static void removeVisitedUrl(String url) {
		visitedUrl.remove(url);
	}
	//pop unvisited URL
	public static Object unVisitedUrlDeQueue() {
		return unVisitedUrl.deQueue();
	}
	//ensure each URL only visited once
	public static void addUnvisitedUrl(String url) {
		if (url != null && !url.trim().equals("")
				&& !visitedUrl.contains(url)
				&& !unVisitedUrl.contains(url))
			unVisitedUrl.enQueue(url);
	}
	public static int getVisitedUrlNum() {
		return visitedUrl.size();
	}
	//judge the unvisited URL empty or not
	public static boolean unVisitedUrlIsEmpty() {
		return unVisitedUrl.isQueueEmpty();
	}
}

DownLoadFile类：下载给定的URL指向的网页，以及进行一些列设置

package com.abc.bfs;

import java.io.IOException;
import java.net.UnknownHostException;
import java.io.InputStream;
import java.io.FileOutputStream;
import java.io.DataOutputStream;
import java.io.File;

import org.apache.http.HttpEntity;
import org.apache.http.HttpStatus;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.impl.client.CloseableHttpClient;
import org.apache.http.impl.client.HttpClients;
import org.apache.http.client.methods.CloseableHttpResponse;
import org.apache.http.client.config.RequestConfig;
public class DownLoadFile {

	//根据URL和网页类型生成需要保存的网页的文件名，去除URL中的非文件名字符
	public String getFileNameByUrl(String url, String contentType) {
		//移除http://
		url=url.substring(7);	//返回从第7个到最后一个字符之间的子串
		//text/html类型
		if (contentType.indexOf("html") != -1) {	//如果是html类型的文本
			url=url.replaceAll("[\\?/:*|<>\"]", "_")+".html";
			return url;
		}
		else {	//如果不是html类型的文本
			return url.replaceAll("[\\?/:*|<>\"]","_")+"."+
				contentType.substring(contentType.lastIndexOf("/")+1);
		}
	}
	//保存网页字节数到本地文件,filepath为要保存文件的相对地址
	private void saveToLocal(HttpEntity entity, String filePath) {
		try {
			
			if(filePath.indexOf("JPG") != -1 || filePath.indexOf("png") != -1
					 || filePath.indexOf("jpeg") != -1) {
				File storeFile = new File(filePath);
				FileOutputStream output = new FileOutputStream(storeFile);

				// 得到网络资源的字节数组,并写入文件
				if (entity != null) {
					InputStream instream = entity.getContent();
					byte b[] = new byte[1024];
					int j = 0;
					while( (j = instream.read(b))!=-1){
						output.write(b,0,j);
						}
					}
				output.flush();
				output.close();
				return;
			}
			
			 if (entity != null) {
	                InputStream input = entity.getContent();
	                DataOutputStream output = new DataOutputStream(
	        				new FileOutputStream(new File(filePath)));
	 
	                int tempByte=-1;
	                while ((tempByte=input.read())>0) {
	                    output.write(tempByte);
	                }
	 
	                if (input != null) {
	                    input.close();
	                }
	 
	                if (output != null) {
	                    output.close();
	                }
	            }
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	//下载URL指定的网页
	public String downloadFile(String url) throws IOException {
		String filePath = null;
		
		//生成CloseableHttpClient对象并设置参数
		CloseableHttpClient httpclient = HttpClients.createDefault();
		

		
		//执行请求
		try {
			
			//生成GetMethod并设置参数
			HttpGet httpget = new HttpGet(url);
			
			//设置请求时间5秒钟
			RequestConfig requestConfig = RequestConfig.custom().setConnectTimeout(5000)
				.setConnectionRequestTimeout(1000).setSocketTimeout(5000).build();
			
			httpget.setConfig(requestConfig);
			
			CloseableHttpResponse response = httpclient.execute(httpget);
			//判断返回状态
			int statusCode = response.getStatusLine().getStatusCode();
			
			//System.out.println("得到的结果:" + response.getStatusLine().getStatusCode());//得到请求结果  
			HttpEntity entity = response.getEntity();//得到请求回来的数据
			
			
			if (statusCode != HttpStatus.SC_OK) {
				System.err.println("Method failed: " + response.getStatusLine());
				//System.err.println("Method failed: " + getMethod.getStatusLine());
				filePath = null;
			}
			//处理HTTP响应内容
			// read byte array
			
			filePath = "D:\\temp\\"
					+ getFileNameByUrl(url, entity.getContentType().getValue());

			saveToLocal(entity, filePath);
		} catch (IllegalArgumentException e) {
			System.out.println("Illegal URL!");
		}
		
		catch (UnknownHostException e) {
			// fatal error
			System.out.println("Please check your provided http address!");
		} catch (IOException e) {
			// web error
			e.printStackTrace();
		} finally {
			// realease connection
			httpclient.close();
		}
		return filePath;
	}
	public static void main(String[] args) throws IOException {
		DownLoadFile a = new DownLoadFile();
		String tmp=null;
		tmp = a.downloadFile("http://www.lietu.com");
		System.out.println(tmp);
	}
}

HtmlParserTool类：对已获取的HTML页面进行处理，用来过滤链接，获得新的链接

package com.abc.bfs;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.htmlparser.Node;
import org.htmlparser.NodeFilter;
import org.htmlparser.Parser;
import org.htmlparser.filters.NodeClassFilter;
import org.htmlparser.filters.OrFilter;
import org.htmlparser.tags.LinkTag;
import org.htmlparser.util.NodeList;
import org.htmlparser.util.ParserException;



public class HtmlParserTool {
	//获取一个网站上的链接,filter用来过滤链接
	public static Set<String> extractLinks(String url, LinkFilter filter) {
		Set<String> links = new HashSet<String>();
		try {
			Parser parser = new Parser(url);
			parser.setEncoding("utf-8");
			//过滤<frame>标签的filter,用来提取frame标签里的src属性
			NodeFilter frameFilter = new NodeFilter() {
				/**
				 * 
				 */
				private static final long serialVersionUID = 1L;

				public boolean accept(Node node) {
					if (node.getText().startsWith("frame src=")) {
						return true;
					}
					else {
						return false;
					}
				}
			};
			
			OrFilter linkFilter = new OrFilter(new NodeClassFilter(LinkTag.class), frameFilter);
			//得到所有经过过滤的标签
			NodeList list = parser.extractAllNodesThatMatch(linkFilter);
			for (int i=0; i<list.size(); i++) {
				Node tag = list.elementAt(i);
				if (tag instanceof LinkTag) {
					LinkTag link = (LinkTag)tag;
					String linkUrl = link.getLink();
					if (filter.accept(linkUrl))
						links.add(linkUrl);
				}
				else {
					String frame = tag.getText();
					int start = frame.indexOf("src=");
					frame = frame.substring(start);
					int end = frame.indexOf(" ");
					if (end == -1)
						end = frame.indexOf(">");
					String frameUrl = frame.substring(5, end-1);
					if (filter.accept(frameUrl))
						links.add(frameUrl);
				}
			}
		} catch (ParserException e) {
			e.printStackTrace();
		}
		return links;
	}
	
	public static void main(String args[]) {
		System.out.println("This is a test for main function!");
		LinkFilter filter = new LinkFilter() {
			public boolean accept(String url) {
				if(url.startsWith("http://www.lietu.com"))
					return true;
				else
					return false;
			}
		};
		Set<String> links = HtmlParserTool.extractLinks("http://www.lietu.com", filter);
		
		Iterator<String> it = links.iterator();
		while (it.hasNext()) {
			String str = it.next();
			System.out.println(str);
		} 
	}
}

MyCrawler类：爬虫的主程序

package com.abc.bfs;
import java.io.IOException;
import java.util.Set;

public class MyCrawler {
	/**
	 * 使用种子初始化URL队列
	 * @return
	 * @param seeds 种子URL
	 */
	
	private void initCrawlerWithSeeds(String[] seeds) {
		for(int i=0; i<seeds.length; i++)
			LinkQueue.addUnvisitedUrl(seeds[i]);
	}
	
	/**
	 * 抓去过程
	 * @return
	 * @param seeds
	 * @throws IOException 
	 */
	public void crawling(String[] seeds) throws IOException {
		//定义过滤器,提取以http://www.lietu.com开头的链接
		LinkFilter filter = new LinkFilter() {
			public boolean accept(String url) {
				if(url.startsWith("http://www.lietu.com"))
					return true;
				else
					return false;
			}
		};
		
		//初始化URL队列
		initCrawlerWithSeeds(seeds);
		//循环条件: 待抓去的链接不空且抓去的网页不多于1000
		while(!LinkQueue.unVisitedUrlIsEmpty() && LinkQueue.getVisitedUrlNum() <= 1000) {
			//队头URL出队列
			String visitUrl = (String)LinkQueue.unVisitedUrlDeQueue();
			if(visitUrl == null)
				continue;
			DownLoadFile downLoader = new DownLoadFile();
			//下载网页
			downLoader.downloadFile(visitUrl);
			System.out.println("下载的网页为: " + visitUrl);
			//该URL放入已访问的URL中
			LinkQueue.addVisitedUrl(visitUrl);
			//提取下载网页中的URL
			Set<String> links = HtmlParserTool.extractLinks(visitUrl, filter);
			//新的未访问的URL入队
			for(String link:links) {
				LinkQueue.addUnvisitedUrl(link);
			}
		}
	}
	
	//main入口方法
	public static void main(String args[]) throws IOException {
		MyCrawler crawler = new MyCrawler();
		crawler.crawling(new String[]{"http://www.lietu.com"});
		System.out.println("爬完了\n");
	}
}

接口LinkFilter：对解析出来的URL进行过滤，什么样的url要，什么样的不要

package com.abc.bfs;

public interface LinkFilter {
	public boolean accept(String url);
}

 

 

小结：中间还改了一点东西，可以下一些jpeg或者bmp的图片了，感觉还是蛮有意思的

爬虫运行：

要把java学的更好，爬取页面只是进行挖掘的第一步，后的应该是还要进一步学习与页面解析有关的，提取到更多的有用信息，然后放到数据库中

接下来什么hadoop，spark都拿过来用下

任我来挖掘吧，挖掘技术哪家强，反正现在我不强，嘻嘻