今天打算写点小东西来练练手,看了知乎一些老司机的建议,决定从爬虫开始练起。
网络爬虫的介绍
之前刚注册好博客,访客数量巨多,我有点兴奋,唉我是不是太火了咋啥都没写就这么多访客?某人一脸淡然回答:搜索引擎的爬虫啦。什么是爬虫?你写的程序就像一只轻盈的蜘蛛,在internet这个巨大的网上飞快的爬行,获取你需要的信息。这些被广泛用于互联网搜索引擎。
“它们可以自动采集所有其能够访问到的页面内容,以供搜索引擎做进一步处理(分检整理下载的页面),而使得用户能更快的检索到他们需要的信息。”——wiki
种子的介绍
首先先介绍下种子,可能和主题关系不太紧密,不过宝宝可是连种子的定义都不知道的人啊!【捂脸】
-
BitTorrent is a communications protocol of peer-to-peer file sharing which is used to distribute data over the Internet.——wiki
-
种子就是个文本文件,种子文件内容=Tracker信息+文件信息。
-
Tracker信息:用种子下载的时候先解析这个信息得到Tracker地址,然后连接Traker服务器,提供其他下载的人的IP,然后你就找他们要文件的信息。
-
文件信息:种子下载最大的好处就是把文件虚拟分成大小相等的block,不过块大小必须是2k的整数次方,然后把每个块的检索信息和Hash验证码写入种子文件中。
-
所以你就知道,种子下载就是找好多下载过这个资源的人一小块一小块的要,用P2P协议传输,最后用好快的速度下到想要的资源~(正在用种子蹭学校网下电影)
-
现在还有用DHT网络技术实现种子下载,可以不用Tracker直接下载,这样连Tracker服务器都不要了嘛,用户可以更快的通过哈希表寻址储存,找到前人开始下载
-
网络爬虫的工作原理
终于进入正题了!网络爬虫的工作流程大致如下:
-
选取一部分精心挑选的种子的URL
-
把这些种子URL放在待处理的队列中,作为将来要爬取得入口
-
从待处理的URL队列中取出URLs,解析DNS,得到主机IP,然后将网页下载,放在已下载的网页库中,同时,将这些URL放在已抓取的URL队列。
-
从已抓取的URL队列中,分析存在URL,从而探索更多的URL,将它们放在待处理队列中,这里就进入了步骤2的循环。
从爬虫角度对互联网进行划分
-
已下载未过期网页
-
已下载已过期网页,这些网页有了更新
-
可知网页,还有抓取下来,也没有在我们的待处理URL队列中,但是可以通过已抓取页面或者待分析URL获取到的URL,认为是可知网页
-
待下载网页,在待处理URL中的那些网页
-
不可知网页,爬虫无法直接抓取下载的网页
搜索策略
不明白的朋友去看数据结构:)
-
广度优先搜索,一层一层搜索(用队列和树实现)
-
深度优先搜索,一条路走到黑,再回头换条路再走到黑(现实生活中用得少)
-
最佳搜索,是一种改进型,使用设计好的网页分析算法,预测待抓取URL与目标网页内容的相关度,从中选择较优的进行搜索。缺点是会自动舍弃它认为“不合适”的URL,它的判断可能会出错噢。这是一种局部最优算法。
-
Partial PageRank策略:有一个Rank值,对已下载和URL队列中的URL形成网页集合,计算PageRank,按照大小进行排序,并按照顺序抓取
-
OPIC策略策略:“该算法实际上也是对页面进行一个重要性打分。在算法开始前,给所有页面一个相同的初始现金(cash)。当下载了某个页面P之后,将P的现金分摊给所有从P中分析出的链接,并且将P的现金清空。对于待抓取URL队列中的所有页面按照现金数进行排序。”
-
大站优先策略:对待分析URL中网站进行分类,对待下载页面多的网站进行优先下载
更新策略
-
历史参考策略,根据页面以往的更新数据,判断未来何时会发生变化(泊松过程进行建模)
-
用户体验策略,我们通常只会看谷歌出来的前几页的资料啦,一样的道理,优先更新查询结果前几页的的网页,“用户体验策略保留网页的多个历史版本,并且根据过去每次内容变化对搜索质量的影响,得出一个平均值,用这个值作为决定何时重新抓取的依据。”
-
聚类抽样策略,将目标网页分成一个个cluster,对每个cluster进行抽样,确定更新周期,作为整个类别的更新周期。(在Reference3的博客中有详细的图片说明哦)
分布式抓取系统结构
对于这一部分我是蛮感兴趣的。依旧是wawlian博客中的图说的非常清楚,我在这里也引用一下:
每个数据中心有多台服务器,你写的程序让不同的服务器协同工作,抓取需要的页面,那么他们怎么能一起好好工作呢?现在主要有三种方法:
-
主从式,一个主人,一群奴隶。奴隶们负责抓取网页,主人负责待处理URL队列,分发工作,以及统治好奴隶们。主从式最大的瓶颈就是这个主人,要是他很蠢或者生病了,全部玩完。
-
对等式,是个平等的社会,大家地位都一样,都是屁儿(peer),每个URL有对应的hash值,假设有n个服务器,每个都有自己的编号,那么通过hash值mod3就可以得出是谁来处理各自URL。对等式的缺陷就是,要是一个服务器坏了,那么n就会减一,所有hashmod的结果都会变噢,是不是又得重来?拓展性不好。
-
哈希法,对等式的改进,“一致性哈希将URL的主域名进行哈希运算,映射为一个范围在0-232之间的某个数。而将这个范围平均的分配给m台服务器,根据URL主域名哈希运算的值所处的范围判断是哪台服务器来进行抓取。如果某一台服务器出现问题,那么本该由该服务器负责的网页则按照顺时针顺延,由下一台服务器进行抓取。这样的话,及时某台服务器出现问题,也不会影响其他的工作。”
Reference:
-
https://en.wikipedia.org/wiki/BitTorrent
-
http://www.laitaolun.com/243.html
-
http://www.cnblogs.com/wawlian/archive/2012/06/18/2553061.html