网上很著名的一本爬虫教程《自己手动写网络爬虫》,该书所有源码是用java编写的,
其中提到了宽度优先遍历算法,闲来无事我把他用python实现了一遍。代码量少了将近一半,呵呵。
宽度优先算法介绍
参考:http://book.51cto.com/art/201012/236668.htm
整个的宽度优先爬虫过程就是从一系列的种子节点开始,把这些网页中的"子节点"(也就是超链接)提取出来,放入队列中依次进行抓取。被处理过的链接需要放
入一张表(通常称为Visited表)中。每次新处理一个链接之前,需要查看这个链接是否已经存在于Visited表中。如果存在,证明链接已经处理过,
跳过,不做处理,否则进行下一步处理。
初始的URL地址是爬虫系统中提供的种子URL(一般在系统的配置文件中指定)。当解析这些种子URL所表示的网页时,会产生新的URL(比如从页面中的<a href= "http://www.admin.com
"中提取出http://www.admin.com
这个链接)。然后,进行以下工作:
(1) 把解析出的链接和Visited表中的链接进行比较,若Visited表中不存在此链接,表示其未被访问过。
(2) 把链接放入TODO表中。
(3) 处理完毕后,再次从TODO表中取得一条链接,直接放入Visited表中。
(4) 针对这个链接所表示的网页,继续上述过程。如此循环往复。
表1.3显示了对图1.3所示的页面的爬取过程。
表1.3 网络爬取
TODO
表
|
Visited
表
|
A
|
空
|
BCDEF
|
A
|
CDEF
|
A,B
|
DEF
|
A,B,C
|
续表
TODO
表
|
Visited
表
|
EF
|
A,B,C,D
|
FH
|
A,B,C,D,E
|
HG
|
A,B,C,D,E,F
|
GI
|
A,B,C,D,E,F,H
|
I
|
A,B,C,D,E,F,H,G
|
空
|
A,B,C,D,E,F,H,G,I
|
宽度优先遍历是爬虫中使用最广泛的一种爬虫策略,之所以使用宽度优先搜索策略,主要原因有三点:
重要的网页往往离种子比较近,例如我们打开新闻网站的时候往往是最热门的新闻,随着不断的深入冲浪,所看到的网页的重要性越来越低。
万维网的实际深度最多能达到17层,但到达某个网页总存在一条很短的路径。而宽度优先遍历会以最快的速度到达这个网页。
宽度优先有利于多爬虫的合作抓取,多爬虫合作通常先抓取站内链接,抓取的封闭性很强。
宽度优先遍历爬虫的python实现
#encoding=utf-8
from BeautifulSoup import BeautifulSoup
import socket
import urllib2
import re
class MyCrawler:
def __init__(self,seeds):
#使用种子初始化url队列
self.linkQuence=linkQuence()
if isinstance(seeds,str):
self.linkQuence.addUnvisitedUrl(seeds)
if isinstance(seeds,list):
for i in seeds:
self.linkQuence.addUnvisitedUrl(i)
print "Add the seeds url \"%s\" to the unvisited url list"%str(self.linkQuence.unVisited)
#抓取过程主函数
def crawling(self,seeds,crawl_count):
#循环条件:待抓取的链接不空且专区的网页不多于crawl_count
while self.linkQuence.unVisitedUrlsEnmpy() is False and self.linkQuence.getVisitedUrlCount()<=crawl_count:
#队头url出队列
visitUrl=self.linkQuence.unVisitedUrlDeQuence()
print "Pop out one url \"%s\" from unvisited url list"%visitUrl
if visitUrl is None or visitUrl=="":
continue
#获取超链接
links=self.getHyperLinks(visitUrl)
print "Get %d new links"%len(links)
#将url放入已访问的url中
self.linkQuence.addVisitedUrl(visitUrl)
print "Visited url count: "+str(self.linkQuence.getVisitedUrlCount())
#未访问的url入列
for link in links:
self.linkQuence.addUnvisitedUrl(link)
print "%d unvisited links:"%len(self.linkQuence.getUnvisitedUrl())
#获取源码中得超链接
def getHyperLinks(self,url):
links=[]
data=self.getPageSource(url)
if data[0]=="200":
soup=BeautifulSoup(data[1])
a=soup.findAll("a",{"href":re.compile(".*")})
for i in a:
if i["href"].find("http://")!=-1:
links.append(i["href"])
return links
#获取网页源码
def getPageSource(self,url,timeout=100,coding=None):
try:
socket.setdefaulttimeout(timeout)
req = urllib2.Request(url)
req.add_header('User-agent', 'Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)')
response = urllib2.urlopen(req)
if coding is None:
coding= response.headers.getparam("charset")
if coding is None:
page=response.read()
else:
page=response.read()
page=page.decode(coding).encode('utf-8')
return ["200",page]
except Exception,e:
print str(e)
return [str(e),None]
class linkQuence:
def __init__(self):
#已访问的url集合
self.visted=[]
#待访问的url集合
self.unVisited=[]
#获取访问过的url队列
def getVisitedUrl(self):
return self.visted
#获取未访问的url队列
def getUnvisitedUrl(self):
return self.unVisited
#添加到访问过得url队列中
def addVisitedUrl(self,url):
self.visted.append(url)
#移除访问过得url
def removeVisitedUrl(self,url):
self.visted.remove(url)
#未访问过得url出队列
def unVisitedUrlDeQuence(self):
try:
return self.unVisited.pop()
except:
return None
#保证每个url只被访问一次
def addUnvisitedUrl(self,url):
if url!="" and url not in self.visted and url not in self.unVisited:
self.unVisited.insert(0,url)
#获得已访问的url数目
def getVisitedUrlCount(self):
return len(self.visted)
#获得未访问的url数目
def getUnvistedUrlCount(self):
return len(self.unVisited)
#判断未访问的url队列是否为空
def unVisitedUrlsEnmpy(self):
return len(self.unVisited)==0
def main(seeds,crawl_count):
craw=MyCrawler(seeds)
craw.crawling(seeds,crawl_count)
if __name__=="__main__":
main(["http://www.baidu.com","http://www.google.com.hk"],50)
分享到:
相关推荐
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [实现提示] 设图的结点不超过30个,每个结点用一个编号表示(如果...
数据结构中的图结构,其中最重要的两个遍历算法——深度优先遍历与广度优先遍历
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
无向图的连接表存储结构的创建...从编号为v的顶点出发,深度优先遍历图的算法 对具有G.vexnum个顶点的图的深度优先遍历的算法 从图G的v顶点出发,广度优先遍历图的算法 对具有G.vexnum个顶点的图的广度优先遍历的算法
深度优先遍历和广度优先遍历 建立图的应用等等
图的深度优先遍历和广度优先遍历-Java实现
C++实现,数据结构,图的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现
图的广度优先遍历.doc 图的广度优先遍历.doc
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
图的深度遍历和广度遍历是两个重要的算法,这也是我们理解并掌握图这一数据结构的基础。通过此程序算法可以进一步掌握图的构造以及遍历的相关知识。
python实现图数据的遍历,需pip install networkx,采用邻接矩阵,邻接表,实现图数据深度遍历dfs,广度遍历bfs。
c++实现图的邻接表深度优先遍历,广度优先遍历
深度优先遍历的实现; 广度优先遍历的实现;
个人新项目可作毕设基于python实现的广度优先遍历搜索(BFS)源码含实验结果及总结操作说明.zip个人新项目可作毕设基于python实现的广度优先遍历搜索(BFS)源码含实验结果及总结操作说明.zip个人新项目可作毕设基于...
程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
抓取策略web信息检索与数据抓取宽度优先遍历拓展PPT资料.pptx
抓取策略Web信息检索与数据抓取宽度优先遍历策略PPT资料.pptx
使用邻接表表示法创建无向图,然后使用非递归算法进行深度优先遍历和广度优先遍历