1 爬虫:Crawler
中文:爬虫或者蜘蛛
爬虫演进过程:逐渐多策略,负载均衡及大规模增量抓取等方向发展
2 万维网及其网页分析
1)静态结构:
就将万维网定义为一个相互联通的连通图,网页为节点,链接为边,那么任意一个网页都可能被其他网页链接,称为反向链接(back link)
也可能主动连接其他网页,称为正向链接
遍历方案:
(正向)深度优先遍历:按照网页到网页的链接进行遍历
(反向)宽度遍历:按照网页到网页的反向链接进行遍历
遍历得到结论:万维网具有蜘蛛结型(bowtie)
得到的4个类型:
a.中部(SCC)这部分网页彼此相连,任意去掉有限个网页,不会影响连通.
(正向/反向遍历都可以遍历3/4的网页)
b.左部(IN)
这种类型网页指向中心部分,称为"目录型网页"
正向遍历全部的3/4
反向只能遍历有限个(可忽略)
c.右部(OUT)
被中心部分指向,称为"权威性网页"
被引用次数多,表示但大多数网页对其认可度高,
正向遍历有限个
反向3/4
d.须脚(Tendrils)
单向连通于整个网页体,(非连通分量)
正/反都只能遍历有限个网页
所以::
爬虫尽可能选择蝴蝶结的左部或者中部分作为其实访问节点集合(start set of URLs)进行遍历,这样可以得到尽可能多的网页
网页分为目录型网页和权威性网页,目录型网页为普通网民服务,便于点击从而继续浏览更多网页.该部分对于深入抓取权威性网页有重大意义;
权威性网页是中部或者右部的网页,反向链接据多,正向叫少,比较重要.
3.1 万维网的直径
如果d表示一条从网页u到网页v的路径,那么对这些万维网上的所有不同的连通网页对所构成的最短路径的平均长度即web直径
当前网页的平均出度为25.7,即平均每个网页含有25.7个指向其他网页的链接.
所以::
遍历的方式很大程度上影响了爬虫的效率,万维网的网页结构并没有那么深,那么爬虫的遍历方式多采用宽度优先的遍历方式,这种方式可以较好的抓取重要性高的网页.
万维网错综复杂,抓取路线并不一定能保证最优.为了防止爬虫一路走到黑,采用"深度策略"控制抓取深度,从而完美解决.
3.2 万维网的规模(10亿数量级上)
网页的特征
对于搜索引擎来说,网页的3大特征:
挥发型(volatile):诞生与消亡
半结构性:html描述的网页是半结构化的数据
隐蔽性:除了静态网页还有隐藏的动态网页.
3.3 爬虫的基本概念
爬虫:是一组运行在计算机中的程序,在搜索引擎中负责抓取时新的且公共的客房问的web网页,图片等,这个过程通过哦下载网页,分析链接,继续漫游指向的网页,循环往复
种子站点:爬虫开始爬去的起点,一般为门户网站和官方网站的首页
URL:同一资源定位符
Backlinks:除了自身之外执行自身链接的集合,是衡量网页受"欢迎"程度的衡量方式
4 网页抓取原理
4.1 telnet和wget
telnet www.nju.edu.cn 80
GET / index.html
或者
wget www.nju.edu.cn/index.html
4.2 从种子站点开始逐层抓取
目录型网页作为种子,爬去网页,提取链接分析(绝对路径与相对路径问题)
爬取顺序:
a.深度优先
b.宽度优先
抓取策略选择宽度优先,原因:
(1)重要的网页离种子站点比较近,符合直觉,eg,首页,头条----都是重要的
(2)万维网没有那么深,到达某一网页的路径通常比较多,总有最短的一条可以达到
ps:研究表明,中文万维网的直径长度为17
(3)宽度优先有利于多爬虫合作爬取,且封闭型较强
抓取过程中借助队列保存网页内部链接以便进行宽度优先的执行
问题:对于网页的图多出度,入度问题,需要记录循环,以及是否抓取过的问题;
对于死循环问题,采用"不重复抓取策略"和一个称为"深度策略"的方法来解决.
4.3 不重复抓取策略(宽度优先与深度策略)
重点在于记住过去的抓取历史,从而确定不重复,eg:迷宫求解使用数据结构栈来处理
而爬虫记录历史使用哈希表.(也称"砸凑表")
MD5签名算法原理
MD5优点:安全性和公开性.
MD5签名是一个哈希函数,可以将任意长度的数据流转换为一个固定长度的数字(通常为4个整型,128位),这个数字称为"数据流的签名"或者"指纹",并且数据流中任意一个微小的变化都会导致签名值的变化.
标准MD5签名的整数空间很大,128位.
实际在处理中,将签名值进行模运算映射到实际的hash表中.
hash函数可以表示为MD5(URL)%n,使得URL被映射到大小为n的哈希表的某个槽位上
hash表过于占空间,所以改用bitmap进行处理
介于bitmap的空间节省以及冲突率问题,改进使用bloom filter(过滤器处理)
假如从种子站点A、种子站点B及种子站点C开始均存在一条到达网页P的路径，路径长度分别为3、27和143。那么在通过A访问了P之后的很长时间之后,还会有不必要的检测P是否访问
这个会有效率影响,为了防止无限制的宽度优先问题,必须在莫各深度上进行限制,达到这个深度后停止抓取,这个深度的取值就是万维网直径长度.
深度策略和宽度优先遍历的组合可以有效的保证抓取过程的封闭性
4.4 网页抓取优先策略
也称页面选择问题:尽可能先抓取重要性的网页.重要性由网页的链接欢迎读,连接重要度和平均深度三个方面决定.
定义连接欢迎读IB(P),主要由反向连接的数目和质量决定;其次,质量,越多重要性高的网页指向他,那么其重要性就越高.
定义连接重要读IL(P),一个关于URL字符串的函数,仅考察字符串本身.主要由一些模式,eg:包含.com或者home的URL,以及具有较少斜杠的URL等
定义平均连接深度ID(P),表示在一个种子站点集合中,深度越小,那么越重要(广度遍历的特定)
I(P)=a*IB(p)+b*IL(p)
4.5 网页重访策略
通过重新访问使得网页与万维网的变化与时俱进
网页变化慢则松柏过程模型.
在松柏模型的理论上,结合直观感知,目前网页重放策略大致归结为:
a.统一重访策略:爬虫以相同的频率重访已经访问过得全部网页.
b.个体重访策略:不同网页的改变频率不同,爬虫根据其更新频率来决定重访页面的频率.即对每一个页面定做一个爬虫重访频率 ,并且网页的变化频率和重访频率对等的.
研究表明对于更新快的重访快反而有害,所以,策略b还增加了子策略eg:限定最大重抓频率等.
给于不同类型的网页不同的重访频率是科学的.
其次,爬虫需要礼貌的按照对方给予的权限执行,这就是著名的Robots协议(权限,~敏感目录等问题),
4.6 Robots协议
是web站点和搜索引擎爬虫交互的一种方式,将一个robots.txt的文件放在网站的根目录上,告知公开性和非公开性目录
(1)User-agent:*:表示对一切搜索引擎爬虫 有效,如果特别针对某个爬虫,则可以写明
(2)Disallow:/2004/onter/tet:表示禁止抓取这个目录
通过遵守Robots协议,表示出爬虫尊重和执行web站点的要求,所以:爬虫需要有一个分析Robots协议的模块,并且严格按照Robots协议的规定,只抓取允许访问的目录和网页
4.7 重要性网页优先抓取策略
对于爬虫算法,当我们需要进行重要网页优先抓取时,那么应当在爬去过程中,选择适当的时机进行重排
这个问题除了类似堆方案进行动态处理之外
在规模扩大后,可以选择多队列的方式,队列分时间片的方式处理.类似系统消息队列方式处理.(优先级链.)
4.8 抓取提速策略(合作抓取策略)
可以考虑三个方面的提速
1]提高抓取单个网页的速度(难)
2]尽可能减少不必要的抓取任务(难)
3]增加同时工作的爬虫数量.
对于第三种方案,可以有两种分解方案
1)通过web主机IP地址进行分解
2)通过网页的域名来分解.
ps:又因为同一ip可能对应多个域名,所以通常采用域名分解任务
为了照顾大站点域名分解策略更加合理,在下载系统中,按照域名分解抓取任务的工作由一个"调度员"的模块完成,通过将域名分解为不同的网页调度给不同的爬虫进行抓取.因此,下载系统由爬虫和调度员构成
说明:
1对任意URL,利用domain函数提取URL域名
2用MD5签名函数进行签名
3将MD5签名进行%n处理
4分配该URL的爬去任务给spider_no.
实际应用中,多采用多爬虫,多调度员的下载系统
![]()
多调度多爬虫下载系统
5 网页库
对于抓取到的网页需要及时的保存在硬盘上,因此首要挑战:快速存储大规模网页;其次这个网页必须能够被其他模块快速读取,因此主要围绕读写问题进行
网页库的特性需求:
1)可伸缩性:网页库的存储必须具有可伸缩性,可以将大规模的网页平滑的分布在一组计算机的硬盘中
2)双向访问模式:必须有效支持两种不同的访问模式,随机访问和顺序访问
a.随机访问:任意一个网页的标签即可读取相应的网页(搜索系统的查询系统中网页缓存部分提供随机的读取顺序)
b.顺序读取:全部网页或者网页中的一部分网页.(主要用在索引系统中顺序读取网页按序索引的过程)
3)大规模更新,删除老版本(产生空洞),更新添加新版本,顺序添加网页库中,所以必须采用磁盘空间紧缩技术回收存储空洞,同时保持互斥更新和访问
为了照顾这些特性,网页的存储方式大致分为3种
1)日志结构:将磁盘看作连续存储介质,只能顺序读写,对网页增加有力不利随机访问(随机访问,必须通过B-+树索引方式,两次读取,同时维护索引的代价)
2)基于哈希的结构:类似一个哈希桶集合,利于随机访问,不利顺序读写(对于一次网页增加,读入内存一个hash桶,然后写入新增部分,再写入磁盘.)
3)哈希日志:是将哈希和日志的优势结合,hash作为索引找到文件块后,顺序写入.
对于新增网页,通过URL计算获得签名,然后模运算,将网页映射到一个hashtable单元,
每个hash单元对应一个日志文件的位置.这个新增网页通过hashfunc映射到hash[1]上,继而顺序写入log1文件.如果随机读取某个URL已存储的网页,或者通过hash得到具体日志文件,然后通过读取日志文件上的B-树索引,进而读取响应的网页文件..等价于日志文件
注:hash日志方式可以支持文件批处理吸写入,从而大大改进了纯hash结构.::在每个日志文件中增加一个写入队列,当积累到一定数量文件后,才批量写入.
这种方式,将新增一个网页插入的不确定性变为确定性,因此增加一个插入队列可以批处理方式插入到目标日志文件中.
只要不是存在大量的随机访问机会,日志结构被认为是最佳的网页存储方式.对于大量的新增网页的需要,hash日志被认为是较为理想的网页存储方式.此外,hash日志能够支持分布式的网页存储.
6著名的关于爬虫的代码
web sphinx
heritrix等
internet Archive使用多级合作爬去网页的方式,每个爬虫进程只分配64个站点,每个站点只分配给一个爬虫,每个单线程爬虫进程读取一个种子URL的列表,并且为每个站点建立一个Queue,接下来使用异步IO的方式从这些队列中并行的爬去网页.当一个网页下载完成后,爬虫提取该网页包含的链接,如果该连接是64个管辖站点时,则该连接将会放到64个queue中的某一个,否则辉存放在磁盘中,同时系统定期将这些磁盘中的跨站连接归并到管辖这些爬虫的队列中,并同时做相应的去重工作.
