最近想梳理一下搜索搜索引擎相关的理论与技术,从爬虫开始,总结一下这方面的问题与解决方案。
不论是分布式爬虫还是单体爬虫、主题爬虫等,最关键的是爬行算法,而作为爬虫数据源的互联网可以抽象的看作是一张有向图,现对该图定义如下:
1.将互联网定义为图
2.每个页面定义为图节点
3.页面中的链接定义为有向边
简而言之,爬虫通过遍历这张有向图来爬取相关信息,并使用这些信息创建索引供检索程序查询。
图的遍历算法有深度优先算法与宽度优先算法,而前者容易使爬虫陷入黑洞,所以宽度优先算法被用来实现爬虫的爬行算法,但是有时也不会完全按照宽度优先算法进行爬行,而是做相应的变通,如带偏好的爬行算法。
首先来看图的宽度的优先遍历算法,
图1为要遍历的图:
图-1 要遍历的有向图
选择A为遍历的根节点,则具体的遍历过程如下表所示:
操作 | 队列 |
初始化 | 空 |
A入队 | A |
A出队 | 空 |
BCDEF入队 | BCDEF |
B出队 | CDEF |
C出队 | DEF |
D出队 | EF |
E出队 | F |
H入队 | FH |
F出队 | H |
G入队 | HG |
H出队 | G |
I入队 | GI |
G出队 | I |
I出队 | 空 |
表-1 图遍历过程
从上表中可以归纳出,图节点的遍历过程为:
A->B->C->D->E->F->H->G->I
爬虫以宽度优先算法遍历互联网
现定于如下:
1).将根URl选定为图的起始节点
2).某URL对应的页面中含有的子URL(对应的页面)为该URL的子节点。
3).通过解析->入TODO队列->入VISITED的队列这一往复过程实现遍历。
图-2 流程图
宽度优先遍历算法是爬虫中采用最为广泛的爬行算法,主要有以下几个原因:
1).重要的网页一般离种子比较近
2).互联网的实际深度最多能达到17层,但到达某个网页总存在一条很短的路径,而宽度优先遍历会以最快的速度到达这个网页。
3).宽度优先遍历有利于多爬虫合作抓取,单体爬虫往往会先抓取站内链接,封闭性很强。