⽹页爬⾍及其⽤到的算法和数据结构
⽹络爬⾍，是⼀种按照⼀定的规则，⾃动的抓取万维⽹信息的程序或者脚本。⽹络爬⾍是 搜索引擎系统中⼗分重要的组成部分，它负责从互 联⽹中搜集⽹页，采集信息，这些⽹页信息⽤于建⽴索引从⽽为搜索 引擎提供⽀持，它决定着整个引擎系统的内容是否丰富，信息是否即 时，因此其性能的优劣直接影响着搜索引擎的效果。
⽹络爬⾍程序的优劣，很⼤程度上反映了⼀个搜索引擎的好差。不信，你可以随便拿⼀个⽹站去查询⼀下各家搜索对它的⽹页收录情况，爬⾍强⼤程度跟搜索引擎好坏基本成正⽐。
1.世界上最简单的爬⾍——三⾏情诗
我们先来看⼀个最简单的最简单的爬⾍，⽤python写成，只需要三⾏。 import requests
url="icode"
(url)
上⾯这三⾏爬⾍程序，就如下⾯这三⾏情诗⼀般，很⼲脆利落。
是好男⼈，
就应该在和⼥友吵架时，
抱着必输的⼼态。
2.⼀个正常的爬⾍程序
上⾯那个最简单的爬⾍，是⼀个不完整的残疾的爬⾍。因为爬⾍程序通常需要做的事情如下：威廉姆森
1）给定的种⼦URLs，爬⾍程序将所有种⼦URL页⾯爬取下来 2）爬⾍程序解析爬取到的URL页⾯中的链接，将这些链接放⼊待爬取URL集合中
3）重复1、2步，直到达到指定条件才结束爬取
因此，⼀个完整的爬⾍⼤概是这样⼦的：
import requests #⽤来爬取⽹页
from bs4 import BeautifulSoup #⽤来解析⽹页
seds = ["www.hao123", #我们的种⼦
"www.csdn",
"icode"]
sum = 0 #我们设定终⽌条件为：爬取到100000个页⾯时，就不玩了
while sum < 10000 :
if sum < len(seds):
r = (seds[sum])
sum = sum + 1
do_save_action(r)
soup = t)
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）……
废话说了那么多，真正的问题来了，问题不是学挖掘机到底哪家强？⽽是如何实现上⾯这些东西！：）
实现的过程中，你会发现，我们要考虑的问题远远不⽌上⾯这些。纸上得来终觉浅，觉知此事要躬⾏！
来⾃：快课⽹
链接：
