首页 > 代码库 > 宽度优先遍历爬虫的python实现

宽度优先遍历爬虫的python实现

 

爬虫 宽度优先遍历 python 

网上很著名的一本爬虫教程《自己手动写网络爬虫》,该书所有源码是用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实现

Python代码  
  1. #encoding=utf-8  
  2. from BeautifulSoup import BeautifulSoup  
  3. import socket  
  4. import urllib2  
  5. import re  
  6.   
  7. class MyCrawler:  
  8.     def __init__(self,seeds):  
  9.         #使用种子初始化url队列  
  10.         self.linkQuence=linkQuence()  
  11.         if isinstance(seeds,str):  
  12.             self.linkQuence.addUnvisitedUrl(seeds)  
  13.         if isinstance(seeds,list):  
  14.             for i in seeds:  
  15.                 self.linkQuence.addUnvisitedUrl(i)  
  16.         print "Add the seeds url \"%s\" to the unvisited url list"%str(self.linkQuence.unVisited)  
  17.     #抓取过程主函数  
  18.     def crawling(self,seeds,crawl_count):  
  19.         #循环条件:待抓取的链接不空且专区的网页不多于crawl_count  
  20.         while self.linkQuence.unVisitedUrlsEnmpy() is False and self.linkQuence.getVisitedUrlCount()<=crawl_count:  
  21.             #队头url出队列  
  22.             visitUrl=self.linkQuence.unVisitedUrlDeQuence()  
  23.             print "Pop out one url \"%s\" from unvisited url list"%visitUrl  
  24.             if visitUrl is None or visitUrl=="":  
  25.                 continue  
  26.             #获取超链接  
  27.             links=self.getHyperLinks(visitUrl)  
  28.             print "Get %d new links"%len(links)  
  29.             #将url放入已访问的url中  
  30.             self.linkQuence.addVisitedUrl(visitUrl)  
  31.             print "Visited url count: "+str(self.linkQuence.getVisitedUrlCount())  
  32.             #未访问的url入列  
  33.             for link in links:  
  34.                 self.linkQuence.addUnvisitedUrl(link)  
  35.             print "%d unvisited links:"%len(self.linkQuence.getUnvisitedUrl())  
  36.               
  37.     #获取源码中得超链接  
  38.     def getHyperLinks(self,url):  
  39.         links=[]  
  40.         data=http://www.mamicode.com/self.getPageSource(url)
  41.         if data[0]=="200":  
  42.             soup=BeautifulSoup(data[1])  
  43.             a=soup.findAll("a",{"href":re.compile(".*")})  
  44.             for i in a:  
  45.                 if i["href"].find("http://")!=-1:  
  46.                     links.append(i["href"])   
  47.         return links  
  48.       
  49.     #获取网页源码  
  50.     def getPageSource(self,url,timeout=100,coding=None):  
  51.         try:  
  52.             socket.setdefaulttimeout(timeout)  
  53.             req = urllib2.Request(url)  
  54.             req.add_header(‘User-agent‘, ‘Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)‘)  
  55.             response = urllib2.urlopen(req)  
  56.             if coding is None:  
  57.                 coding= response.headers.getparam("charset")  
  58.             if coding is None:  
  59.                 page=response.read()  
  60.             else:  
  61.                 page=response.read()  
  62.                 page=page.decode(coding).encode(‘utf-8‘)  
  63.             return ["200",page]  
  64.         except Exception,e:  
  65.             print str(e)  
  66.             return [str(e),None]  
  67.           
  68. class linkQuence:  
  69.     def __init__(self):  
  70.         #已访问的url集合  
  71.         self.visted=[]  
  72.         #待访问的url集合  
  73.         self.unVisited=[]  
  74.     #获取访问过的url队列  
  75.     def getVisitedUrl(self):  
  76.         return self.visted  
  77.     #获取未访问的url队列  
  78.     def getUnvisitedUrl(self):  
  79.         return self.unVisited  
  80.     #添加到访问过得url队列中  
  81.     def addVisitedUrl(self,url):  
  82.         self.visted.append(url)  
  83.     #移除访问过得url  
  84.     def removeVisitedUrl(self,url):  
  85.         self.visted.remove(url)  
  86.     #未访问过得url出队列  
  87.     def unVisitedUrlDeQuence(self):  
  88.         try:  
  89.             return self.unVisited.pop()  
  90.         except:  
  91.             return None  
  92.     #保证每个url只被访问一次  
  93.     def addUnvisitedUrl(self,url):  
  94.         if url!="" and url not in self.visted and url not in self.unVisited:  
  95.             self.unVisited.insert(0,url)  
  96.     #获得已访问的url数目  
  97.     def getVisitedUrlCount(self):  
  98.         return len(self.visted)  
  99.     #获得未访问的url数目  
  100.     def getUnvistedUrlCount(self):  
  101.         return len(self.unVisited)  
  102.     #判断未访问的url队列是否为空  
  103.     def unVisitedUrlsEnmpy(self):  
  104.         return len(self.unVisited)==0  
  105.       
  106. def main(seeds,crawl_count):  
  107.     craw=MyCrawler(seeds)  
  108.     craw.crawling(seeds,crawl_count)  
  109. if __name__=="__main__":  
  110.     main(["http://www.baidu.com","http://www.google.com.hk"],50) 

宽度优先遍历爬虫的python实现