文档章节

网页爬虫及其用到的算法和数据结构

renew
 renew
发布于 2014/09/30 15:57
字数 1883
阅读 3341
收藏 70



网络爬虫程序的优劣,很大程度上反映了一个搜索引擎的好差。不信,你可以随便拿一个网站去查询一下各家搜索对它的网页收录情况,爬虫强大程度跟搜索引擎好坏基本成正比。

1.世界上最简单的爬虫——三行情诗

我们先来看一个最简单的最简单的爬虫,用python写成,只需要三行。
import requests
url="http://www.cricode.com" r=requests.get(url)
上面这三行爬虫程序,就如下面这三行情诗一般,很干脆利落。

是好男人,

就应该在和女友吵架时,

抱着必输的心态。
2.一个正常的爬虫程序

上面那个最简单的爬虫,是一个不完整的残疾的爬虫。因为爬虫程序通常需要做的事情如下:
  • 1)给定的种子URLs,爬虫程序将所有种子URL页面爬取下来
  • 2)爬虫程序解析爬取到的URL页面中的链接,将这些链接放入待爬取URL集合中
  • 3)重复1、2步,直到达到指定条件才结束爬取
因此,一个完整的爬虫大概是这样子的:
import requests                       #用来爬取网页 
from bs4 import BeautifulSoup         #用来解析网页 
seds = ["http://www.hao123.com",      #我们的种子               
        "http://www.csdn.net",              
         http://www.cricode.com] 
sum = 0                               #我们设定终止条件为:爬取到100000个页面时,就不玩了   
while sum < 10000 :     
    if sum < len(seds):          
        r = requests.get(seds[sum])          
        sum = sum + 1          
        do_save_action(r)         
        soup = BeautifulSoup(r.content)               
         
        urls = soup.find_all("href",.....)                     //解析网页          
        for url in urls:               
            seds.append(url)  
                else:          
                    break
3.现在来找茬

上面那个完整的爬虫,不足20行代码,相信你能找出20个茬来。因为它的缺点实在是太多。下面一一列举它的N宗罪:
  • 1)我们的任务是爬取1万个网页,按上面这个程序,一个人在默默的爬取,假设爬起一个网页3秒钟,那么,爬一万个网页需要3万秒钟。MGD,我们应当考虑开启多个线程(池)去一起爬取,或者用分布式架构去并发的爬取网页。
  • 2)种子URL和后续解析到的URL都放在一个列表里,我们应该设计一个更合理的数据结构来存放这些待爬取的URL才是,比如队列或者优先队列。
  • 3)对各个网站的url,我们一视同仁,事实上,我们应当区别对待。大站好站优先原则应当予以考虑。
  • 4)每次发起请求,我们都是根据url发起请求,而这个过程中会牵涉到DNS解析,将url转换成ip地址。一个网站通常由成千上万的URL,因此,我们可以考虑将这些网站域名的IP地址进行缓存,避免每次都发起DNS请求,费时费力。
  • 5)解析到网页中的urls后,我们没有做任何去重处理,全部放入待爬取的列表中。事实上,可能有很多链接是重复的,我们做了很多重复劳动。
  • 6)…..
4.找了这么多茬后,很有成就感,真正的问题来了,学挖掘机到底哪家强?

现在我们就来一一讨论上面找茬找出的若干问题的解决方案。

1)并行爬起问题

我们可以有多重方法去实现并行。

多线程或者线程池方式,一个爬虫程序内部开启多个线程。同一台机器开启多个爬虫程序,如此,我们就有N多爬取线程在同时工作。能大大减少时间。

此外,当我们要爬取的任务特别多时,一台机器、一个网点肯定是不够的,我们必须考虑分布式爬虫。常见的分布式架构有:主从(Master——Slave)架构、点对点(Peer to Peer)架构,混合架构等。

说道分布式架构,那我们需要考虑的问题就有很多,我们需要分派任务,各个爬虫之间需要通信合作,共同完成任务,不要重复爬取相同的网页。分派任务我们要做到公平公正,就需要考虑如何进行负载均衡。负载均衡,我们第一个想到的就是Hash,比如根据网站域名进行hash。

负载均衡分派完任务之后,千万不要以为万事大吉了,万一哪台机器挂了呢?原先指派给挂掉的哪台机器的任务指派给谁?又或者哪天要增加几台机器,任务有该如何进行重新分配呢?

一个比较好的解决方案是用一致性Hash算法。

2)待爬取网页队列

如何对待待抓取队列,跟操作系统如何调度进程是类似的场景。

不同网站,重要程度不同,因此,可以设计一个优先级队列来存放待爬起的网页链接。如此一来,每次抓取时,我们都优先爬取重要的网页。

当然,你也可以效仿操作系统的进程调度策略之多级反馈队列调度算法。

3)DNS缓存

为了避免每次都发起DNS查询,我们可以将DNS进行缓存。DNS缓存当然是设计一个hash表来存储已有的域名及其IP。

4)网页去重

说到网页去重,第一个想到的是垃圾邮件过滤。垃圾邮件过滤一个经典的解决方案是Bloom Filter(布隆过滤器)。布隆过滤器原理简单来说就是:建立一个大的位数组,然后用多个Hash函数对同一个url进行hash得到多个数字,然后将位数组中这些数字对应的位置为1。下次再来一个url时,同样是用多个Hash函数进行hash,得到多个数字,我们只需要判断位数组中这些数字对应的为是全为1,如果全为1,那么说明这个url已经出现过。如此,便完成了url去重的问题。当然,这种方法会有误差,只要误差在我们的容忍范围之类,比如1万个网页,我只爬取到了9999个,剩下那一个网页,who cares!

5)数据存储的问题

数据存储同样是个很有技术含量的问题。用关系数据库存取还是用NoSQL,抑或是自己设计特定的文件格式进行存储,都大有文章可做。

6)进程间通信

分布式爬虫,就必然离不开进程间的通信。我们可以以规定的数据格式进行数据交互,完成进程间通信。

7)……
 
废话说了那么多,真正的问题来了,问题不是学挖掘机到底哪家强?而是如何实现上面这些东西!:)

实现的过程中,你会发现,我们要考虑的问题远远不止上面这些。纸上得来终觉浅,觉知此事要躬行!

本文转载自:http://www.cricode.com/3622.html

renew
粉丝 4
博文 19
码字总数 13554
作品 0
丰台
程序员
私信 提问
加载中

评论(4)

M
MemoryMa
希望有后续更详细的文章
g
genliu777
期待后续
小克898
小克898

引用来自“min_fancy”的评论

有没有好的开源爬虫项目推荐呢?

scrapy,很不错
m
min_fancy
有没有好的开源爬虫项目推荐呢?
【转】网页爬虫及其用到的算法和数据结构

 网络爬虫,是一种按照一定的规则,自动的抓取万维网信息的程序或者脚本。网络爬虫是搜索引擎系统中十分重要的组成部分,它负责从互 联网中搜集网页,采集信息,这些网页信息用于建立索引从...

一只死笨死笨的猪
2014/09/30
76
0
Python实现简易Web爬虫

简介: 网络爬虫(又被称为网页蜘蛛),网络机器人,是一种按照一定的规则,自动地抓信息的程序或者脚本。假设互联网是一张很大的蜘蛛网,每个页面之间都通过超链接这根线相互连接,那么我们的...

洛荷
2017/03/16
0
0
网络爬虫基础

网络爬虫 网络爬虫(Computer Robot)(又被称为网页蜘蛛,网络机器人,在FOAF社区中间,更经常的称为网页追逐者),是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本。另外一些不...

白志华
2016/01/05
329
0
dota玩家与英雄契合度的计算器,python语言scrapy爬虫的使用

首发:个人博客,更新&纠错&回复 演示地址在这里,代码在这里。 一个dota玩家与英雄契合度的计算器(查看效果),包括两部分代码: 1.python的scrapy爬虫,总体思路是page->model->result,从...

祁达方
2015/12/01
105
0
20161121 Spider 之 爬虫 基本工作原理

网络爬虫是捜索引擎抓取系统的重要组成部分。爬虫的主要目的是将互联网上的网页下载到本地形成一个或联网内容的镜像备份。这篇博客主要对爬虫以及抓取系统进行一个简单的概述。 一、网络爬虫...

seven先生
2016/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈Visitor访问者模式

一、前言 什么叫访问,如果大家学过数据结构,对于这点就很清晰了,遍历就是访问的一般形式,单独读取一个元素进行相应的处理也叫作访问,读取到想要查看的内容+对其进行处理就叫作访问,那么...

青衣霓裳
20分钟前
4
0
JS内嵌多个页面,页面之间如何更快捷的查找相关联的页面

假设parent为P页面, P页面有两个子页面,分别为B页面和C页面; B页面和C页面分别内嵌一个iframe,分别为:D页面和E页面 现在通过B页面的内嵌页面D的方法refreshEpage(eUrl)来加载内嵌页面E的内容...

文文1
21分钟前
6
0
Hibernate 5 升级后 getProperties 错误

升级到 Hibernate 5 后,提示有错误: org.hibernate.engine.spi.SessionFactoryImplementor.getProperties()Ljava/util/Map; 完整的错误栈为: java.lang.NoSuchMethodError: org.hibernate......

honeymoose
23分钟前
4
0
mysql-connector-java升级到8.0后保存时间到数据库出现了时差

在一个新项目中用到了新版的mysql jdbc 驱动 <dependency>     <groupId>mysql</groupId>     <artifactId>mysql-connector-java</artifactId>     <version>8.0.18</version> ......

ValSong
26分钟前
6
0
Spring中BeanFactory与FactoryBean的区别

在Spring中有BeanFactory和FactoryBean这2个接口,从名字来看很相似,比较容易搞混。 一、BeanFactory BeanFactory是一个接口,它是Spring中工厂的顶层规范,是SpringIoc容器的核心接口,它定...

大王叫下
28分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部