前言
遍历策略是爬虫的核心问题,在爬虫系统中,待抓取URL队列是很重要的一部分。待抓取URL队列中的URL以什么样的顺序排列也是一个很重要的问题,因为这涉及到先抓取那个页面,后抓取哪个页面。而决定这些URL排列顺序的方法,叫做抓取策略。爬虫策略主要有以下几种:
一、深度优先遍历策略:
深度优先遍历测试是指网络爬虫会从起始页开始,一个链接一个链接跟踪下去,处理完这条线路的链接之后,在再转入下一个起始页,继续跟踪链接,我们以下面的图为例:
遍历的路径是:A-F-G E-H-I B C D
![image.png](https://ask.hellobi.com/uploads/article/20180510/2cc8f85d8e0da6c4c3fe00bb4b379ef9.png)
不过,我们在做爬虫时,深度优先策略不一定能适用于所有情况,深度优先如果误入无穷分枝(深度无限),则不可能找到目标节点。
二、广度优先遍历策略:
广度优先策略是按照树的层次进行搜索,如果此层没有搜索完成,不会进入下一层搜索。即,首先完成一个层次的搜索,其次在进行下一层次,也称之为分层处理。我们还以上面的图为例:
遍历的路径是:第一层遍历:A-B-C-D-E-F,第二层遍历:G-H,第三层则遍历:I
不过,广度优先遍历策略属于盲目搜索,它并不考虑结果存在的可能位置,会彻底地搜索整张图,因而效率较低,但是,如果你要尽可能的覆盖较多的网页,广度优先搜索方法是较好的选择。
三、Partial PageRank策略:
PageRank算法的思想:对于已经下载的网页,连同待抓取URL队列中的URL,形成网页集合,计算每个页面的PageRank值(PageRank算法参考:PageRank算法--从原理到实现),计算完之后,将待抓取队列中的URL按照PageRank值的大小排列,并按照顺序依次抓取URL页面。
如果每次新抓取一个网页,就重新计算PageRank值,明显效率太低。折中办法是网页攒够K个计算一次。
下图即为PageRank策略示意图:
设定每下载3个网页进行新的PageRank计算,此时已经有{1,2,3}3个网页下载到本地。这三个网页包含的链接指向{4,5,6},即待抓取URL队列,如何决定下载顺序?
将这6个网页形成新的集合,对这个集合计算PageRank的值,这样4、5、6就获得自己对应的PageRank值,由大到小排序,即可得出下载顺序。假设顺序为5,4,6,当下载55页面后抽取出链接,指向页面8,此时赋予8临时PageRank值,如果这个值大于4和6的PageRank,则接下来优先下载页面8,如此不断循环,即形成了非完全PageRank策略的计算思路。
![image.png](https://ask.hellobi.com/uploads/article/20180510/a270da18ec8d45b76c855e33d2de84ea.png)
四、OPIC策略策略(Online Page Importance Computation):
基本思路:在算法开始前,给所有页面一个相同的初始现金(cash)。当下载了某个页面P之后,将P的现金分摊给所有从P中分析出的链接,并且将P的现金清空。对于待抓取URL队列中的所有页面按照现金数进行排序。
与PageRank的区别在于:PageRank每次需要迭代计算,而OPIC策略不需要迭代过程。所以计算速度远远快与PageRank,适合实时计算使用。
五、大站优先策略:
策略思路: 以网站为单位来选题网页重要性,对于待爬取URL队列中的网页,根据所属网站归类,如果哪个网站等待下载的页面最多,则优先下载这些链接,其本质思想倾向于优先下载大型网站。因为大型网站往往包含更多的页面。鉴于大型网站往往是著名企业的内容,其网页质量一般较高,所以这个思路虽然简单,但是有一定依据。实验表明这个算法效果也要略优先于宽度优先遍历策略。
六、参考资料:
https://blog.csdn.net/zolalad/article/details/16344661
https://blog.csdn.net/y396397735/article/details/49817133
https://wenku.baidu.com/view/526b94305acfa1c7aa00cc70.html
https://blog.csdn.net/rubinorth/article/details/52215036
结语:
个人学习总结,若有误,欢迎指正,欢迎读者访问及交流: QQ:575553272