爬虫的广度优先和深度优先算法
- 格式：pdf
- 大小：101.60 KB
- 文档页数：2
爬⾍的⼴度优先和深度优先算法⼴度优先算法介绍 整个的⼴度优先爬⾍过程就是从⼀系列的种⼦节点开始，把这些⽹页中的"⼦节点"(也就是超链接)提取出来，放⼊队列中依次进⾏抓取。被处理过的链接需要放 ⼊⼀张表(通常称为Visited表)中。每次新处理⼀个链接之前，需要查看这个链接是否已经存在于Visited表中。如果存在，证明链接已经处理过， 跳过，不做处理，否则进⾏下⼀步处理。把解析出的链接和Visited表中的链接进⾏⽐较，若Visited表中不存在此链接，表⽰其未被访问过。把链接放⼊TODO表中。处理完毕后，再次从TODO表中取得⼀条链接，直接放⼊Visited表中。针对这个链接所表⽰的⽹页，继续上述过程。如此循环往复。⼴度优先遍历是爬⾍中使⽤最⼴泛的⼀种爬⾍策略，之所以使⽤⼴度优先搜索策略，主要原因有三点：重要的⽹页往往离种⼦⽐较近，例如我们打开新闻⽹站的时候往往是最热门的新闻，随着不断的深⼊冲浪，所看到的⽹页的重要性越来越低。万维⽹的实际深度最多能达到17层，但到达某个⽹页总存在⼀条很短的路径。⽽⼴度优先遍历会以最快的速度到达这个⽹页。⼴度优先有利于多爬⾍的合作抓取，多爬⾍合作通常先抓取站内链接，抓取的封闭性很强。爬⾍深度优先搜索 深度优先搜索是⼀种在开发爬⾍早期使⽤较多的⽅法。它的⽬的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML⽂件) 。在⼀个HTML⽂件中，当⼀个超链被选择后，被链接的HTML⽂件将执⾏深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的⼀条链。深度优先搜索沿着HTML⽂件上的超链⾛到不能再深⼊为⽌，然后返回到某⼀个HTML⽂件，再继续选择该HTML⽂件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历⼀个Web 站点或深层嵌套的⽂档集合；缺点是因为Web结构相当深,，有可能造成⼀旦进去，再也出不来的情况发⽣。 1 #encoding=utf-8
2 from bs4 import BeautifulSoup
3 import socket
4 import urllib2
5 import re
6 import zlib
7
8 class MyCrawler:
9 def __init__(self,seeds):
10 #初始化当前抓取的深度
11 self.current_deepth = 1
12 #使⽤种⼦初始化url队列
13 self.linkQuence=linkQuence()
14 if isinstance(seeds,str):
15 self.linkQuence.addUnvisitedUrl(seeds)
16 if isinstance(seeds,list):
17 for i in seeds:
18 self.linkQuence.addUnvisitedUrl(i)
19 print "Add the seeds url \"%s\" to the unvisited url list"%str(self.linkQuence.unVisited)
20 #抓取过程主函数
21 def crawling(self,seeds,crawl_deepth):
22 #循环条件：抓取深度不超过crawl_deepth
23 while self.current_deepth <= crawl_deepth:
24 #循环条件：待抓取的链接不空
25 while not self.linkQuence.unVisitedUrlsEnmpy():
26 #队头url出队列
27 visitUrl=self.linkQuence.unVisitedUrlDeQuence()
28 print "Pop out one url \"%s\" from unvisited url list"%visitUrl
29 if visitUrl is None or visitUrl=="":
30 continue
31 #获取超链接
32 links=self.getHyperLinks(visitUrl)
33 print "Get %d new links"%len(links)
34 #将url放⼊已访问的url中
35 self.linkQuence.addVisitedUrl(visitUrl)
36 print "Visited url count: "+str(self.linkQuence.getVisitedUrlCount())
37 print "Visited deepth: "+str(self.current_deepth)
38 #未访问的url⼊列
39 for link in links:
40 self.linkQuence.addUnvisitedUrl(link)
41 print "%d unvisited links:"%len(self.linkQuence.getUnvisitedUrl())
42 self.current_deepth += 1
43
44 #获取源码中得超链接
45 def getHyperLinks(self,url):
46 links=[]
47 data=self.getPageSource(url)
48 if data[0]=="200":
49 soup=BeautifulSoup(data[1])
50 a=soup.findAll("a",{"href":re.compile('^http|^/')})
51 for i in a:
52 if i["href"].find("http://")!=-1:
53 links.append(i["href"])
54 return links
55
56 #获取⽹页源码
57 def getPageSource(self,url,timeout=100,coding=None):
58 try:
59 socket.setdefaulttimeout(timeout)
60 req = urllib2.Request(url)
61 req.add_header('User-agent', 'Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)')
62 response = urllib2.urlopen(req)
63 page = ''
64 if response.headers.get('Content-Encoding') == 'gzip':
65 page = zlib.decompress(page, 16+zlib.MAX_WBITS)
66
67 if coding is None:
68 coding= response.headers.getparam("charset")
69 #如果获取的⽹站编码为None
70 if coding is None:
71 page=response.read()
72 #获取⽹站编码并转化为utf-8
73 else:
74 page=response.read()
75 page=page.decode(coding).encode('utf-8')
76 return ["200",page]
77 except Exception,e:
78 print str(e)
79 return [str(e),None]
80
81 class linkQuence:
82 def __init__(self):
83 #已访问的url集合
84 self.visted=[]
85 #待访问的url集合
86 self.unVisited=[]
87 #获取访问过的url队列
88 def getVisitedUrl(self):
89 return self.visted
90 #获取未访问的url队列
91 def getUnvisitedUrl(self):
92 return self.unVisited
93 #添加到访问过得url队列中
94 def addVisitedUrl(self,url):
95 self.visted.append(url)
96 #移除访问过得url
97 def removeVisitedUrl(self,url):
98 self.visted.remove(url)
99 #未访问过得url出队列
100 def unVisitedUrlDeQuence(self):
101 try:
102 return self.unVisited.pop()
103 except:
104 return None
105 #保证每个url只被访问⼀次
106 def addUnvisitedUrl(self,url):
107 if url!="" and url not in self.visted and url not in self.unVisited:
108 self.unVisited.insert(0,url)
109 #获得已访问的url数⽬
110 def getVisitedUrlCount(self):
111 return len(self.visted)
112 #获得未访问的url数⽬
113 def getUnvistedUrlCount(self):
114 return len(self.unVisited)
115 #判断未访问的url队列是否为空
116 def unVisitedUrlsEnmpy(self):
117 return len(self.unVisited)==0
118
119 def main(seeds,crawl_deepth):
120 craw=MyCrawler(seeds)
121 craw.crawling(seeds,crawl_deepth)
122
123 if __name__=="__main__":
124 main(["http://www.baidu.com", "http://www.google.com.hk", "http://www.sina.com.cn"],10)
