搜索引擎与数据管理 Lecture3:网页抓取技术 （爬虫） 赵慧

搜索引擎的组成 WWW 网页获取 分析系统 查询系统 索引系统 提交查询 返回查询结果 网页数据库 索引库

网页的获取 搜索引擎的数据来源：网页 网页抓取——爬虫系统 爬虫系统的功能： Crawler Spider Robot 爬虫系统的功能： 漫游访问互联网，发现并搜集多种类型的文档，如HTML页面、XML文档、Newsgroup文章，FTP文件、Word文档和多媒体信息等。 第一个爬虫程序：MIT的Matthew Gray在1993年编写的Wonderer。

互联网的结构 根据互联网的静态结构，互联网是一个相互连通的连通图 正向链接：一个网页链接到其他网页 反向链接：一个网页被其他网页链接 URL 节点：网页 边：链接 正向链接：一个网页链接到其他网页 目录导航网页 正向遍历：深度/广度 反向链接：一个网页被其他网页链接 体现网页的重要程度——权威网页 反向遍历：深度/广度 URL Uniform Resource Locator(统一资源定位） 例：http://www.ecnu.edu.cn/index.html 包括 访问方式：HTTP协议 被访问服务器：www.ecnu.edu.cn 被访问文件：index.html

Web Graph http://www.touchgraph.com/TGGoogleBrowser.html

Complex Network Example: WWW ----- (K. C. Claffy) 有向网络， 结点：web页面，边：超链

网页抓取过程 从URL库（初始时包含用户指定的起始种子URL集合，可以是 1个或多个）获得输入 解析URL中标明的Web服务器地址 建立连接、发送请求和接收数据：基于Socket 将获得的网页数据存储在网页库，同时将待抓取的URL放入URL库，保证整个过程的递归进行，直到URL库为空。 引出的问题 如何收集重要的网页 如何避免网页的重复收集 如何提高抓取效率？ 。。。。。。

网页抓取策略—宽度搜索示例 重要的网页优先抓取 1 2 3 4 5 6 1 2 3 4 5 6 spider 宽度优先和深度优先 1 2 3 4 5 6 宽度优先和深度优先 通常选取宽度优先 重要的网页往往离种子站点的距离较近 互联网的深度没有想象的那么深，到达某一个网页的路径很多，但是存在一条最短路径 有利于多爬虫合作抓取。 1 2 3 4 5 6 重要的网页优先抓取

如何避免重复抓取网页？ 思考：如何不重复 技术支持 问题 例：抓取顺序为www.sohu.com www.sina.com 关键在于记录历史 如何记录？ 如何判定重复？ 技术支持 Hash函数 MD5签名函数 。。。。。。 问题 互联网的网页数量以亿为 单位，如何存放历史？ www.sohu.com www.sohu.com www.sina.com MD5签名函数 1 1 2 3 4 5 6 7 8

MD5签名算法 1992年8月，Ronald L.Rivest提出，具有公开和安全的特点 基本原理： 使用一个Hash函数，可以将任意长度的数据流转换为一个固定长度的整数（通常4个整数，128位），这个数字成为“数据流的签名”，或者“指纹”。 数据流中任意以一个微小的变化都会导致签名值的变化。 2的128次方可以表达的空间非常大，而32位处理器可分配的内存空间最大4GB 实际的Hash函数为MD5（URL）％n，n为Hash表的大小，即槽的个数 互联网的网页数>100亿，Hash表需要多大？内存是否放得下？——>采用bitmap数据结构压缩内存的使用(int hash[8])，以bit为最小单位，位运算） >10GB

页面选择问题 种子站点：爬虫开始抓取的起点，通常为各大门户网站和官方网站的首页。 尽可能首先抓取重要的网页 问题：重要性的判定 链接欢迎度：取决于反向链接的数目和质量 反向链接数目越多表示其他网页对该网页的认可，被访问的可能性就越高，重要性就越高； 被更多的重要性高的网页指向，重要性越高 避免作弊网页，人为地在网页中设置指向自身的链接 链接重要度：关于URL字符串的函数，通过一些模式确定 如包含.com和home的URL重要度高，具有“/”少的URL重要度高等 平均链接深度：由距离种子站点的距离决定 认为种子站点是重要性高的站点； 离种子站点越近，重要性越高；反之，越低

爬虫的礼貌 为什么？ 爬虫要像绅士一样遵守Robots协议 有些网站不希望爬虫白天抓取网页； 有些网站不希望爬虫抓取敏感信息； DNS服务提供商不希望大量的域名解析工作被爬虫的域名解析请求所占用; …… 爬虫要像绅士一样遵守Robots协议 在网站的根目录下的一个文本文件，是web站点和爬虫交互所遵守的协议。

网页抓取速度的提高 互联网上的网页数量大，更新速度快 问题：如何分解任务，避免多个爬虫抓取相同的网页 提高抓取单个网页的速度：受带宽限制，不可行 尽可能减少不必要的抓取任务：不能快速同步网页的变化 增加同时工作的爬虫数量：有效可行的方式 问题：如何分解任务，避免多个爬虫抓取相同的网页 通过IP地址分解：某个爬虫抓取某个地址段的网页 通过域名解析分解：某个爬虫抓取某个域名段的网页 方案的选择：照顾大型网站，采用域名解析的策略，有“调度员”程序通过域名解析将不同的网页分配给不同的爬虫抓取。

分配过程 对于任意的URL，利用domain函数提取URL的域名； 用MD5签名函数签名域名，MD5(domain(URL)) 将MD5签名值对n取运算 int spider_no= MD5(domain(URL)%n 该URL分配给编号为spider_no的爬虫进行抓取

爬虫 example：Heritrix 采用Java开发的、开源网络爬虫 下载页面：http://crawler.archive.org/downloads.html链接到SourceForge的下载页面 可以在Eclipse配置Heritrix的开发环境，对Heritrix的源代码进行修改和编译，二次开发。 尝试使用Heritrix抓取一些网页，如会展、手机、笔记本、房产、股票、课件等

Crawler in Practice

Homework Option1：尝试应用某爬虫抓取一些网页，并解析存储（可两人一组） Seed：http://mil.news.sina.com.cn/或http://military.china.com/ 5月30日提交实验报告（+10分） Option2：查阅资料，总结撰写一篇关于网络爬虫的小论文 5月23日提交（小论文电子版 ） 考虑所要抓取的数据的特点以及解决方法 论文样本