课程设计(综合实验)报告格式.doc

课程设计报告( 2010 - 2011 年度第 一 学期)名 称： 软件设计与实践课程设计 题 目： 网络爬虫研究与应用 院 系： 计算机系 班 级： 学 号： 学生姓名： 指导教师： 软件设计与实践教学组 设计周数： 两周 成 绩： 日期： 2011 年 1 月 14 日软件设计与实践课程设计任 务 书一、 目的与要求1 了解网络爬虫的架构和工作原理，实现网络爬虫的基本框架；2 开发平台采用JDK 1.60 eclipse集成开发环境。二、 主要内容1. 了解网络爬虫的构架，熟悉网页抓取的整个流程。2. 学习宽度优先和深度优先算法，实现宽度crawler应用程序的编写、调试和运行。3. 学习主题爬行及内容分析技术。4. 实现网络爬虫的基本框架。三、 进度计划序号设计(实验)内容完成时间备注1对网络爬虫程序进行初步认识2011-1-52学习算法2011-1-73设计爬虫的框架，划分功能模块2011-1-104代码实现及调试2011-1-135验收、撰写报告2011-1-14四、 设计成果要求1 要求按时按量完成所规定的实验内容；2 界面设计要求友好、灵活、易操作、通用性强、具有实用性；3 基本掌握所采用的开发平台。五、 考核方式平时成绩验收实验报告。 学生姓名：于兴隆 指导教师：王蓝婧 2011 年 1 月 2 日1、 课程设计的目的与要求1.目的： 1.1 掌握crawler的工作原理及实现方法； 1.2 了解爬虫架构； 1.3 熟悉网页抓取的整个流程及操作步骤； 1.4 掌握宽度优先，深度优先算法，并实现宽度crawler应用程序的编写、调试和运行； 1.5 掌握主题爬行及内容分析技术； 1.6 实现一个最基础的主题爬虫的过程； 1.7 理解pageRank算法，并编程验证；2、 设计正文网络爬虫研究与应用摘要:本文通过对网络爬虫研究的逐步展开，讨论了爬虫的相关概念与技术，并通过实验设计了简单的基于宽度优先的爬虫和主题式爬虫。最后，讨论了PageRank算法。关键词:网络爬虫 爬虫应用 PageRank算法1.引言 随着网络技术的迅速发展，万维网已经成为人们获取信息的重要渠道，如何高效地提取并利用这些信息成为一个巨大的挑战。现阶段的搜索引擎，作为一个辅助人们检索信息的工具成为用户访问万维网的入口和指南。但是，这些通用性搜索引擎也存在着一定的局限性，如： (1)统一的返回不能满足不同用户的检索需求。 (2)搜索引擎提高覆盖面的目标与膨胀的网络信息之间的矛盾日益加深。 (3)搜索引擎大多提供基于关键字的检索，难以支持根据语义信息提出的查询。为了解决上述问题，定向抓取相关网页资源的主题爬虫应运而生。主题爬虫是一个自动下载网页的程序，它根据既定的抓取目标，有选择的访问万维网上的网页与相关的链接，获取所需要的信息。与通用爬虫不同，主题爬虫并不追求大的覆盖，而将目标定为抓取与某一特定主题内容相关的网页，为面向主题的用户查询准备数据资源。2.网络爬虫 2.1 Internet上的网页关系建模 如下图所示，如果将网页看成是图中的某一个节点，而将网页中指向其他网页的链接看成是这个节点指向其他节点的边，那么我们很容易将整个Internet上的网页建模成一个有向图。理论上，通过遍历算法遍历该图，可以访问到Internet上的几乎所有的网页。图 1. 网页关系的建模图2.2搜索引擎的分类和整体结构 2.2.1分类 :搜索引擎虽然所采用的技术和实现的方法各有不同，但是总体来说可以分为两类，一种是基于目录的搜索引擎，另一种是基于全文检索的搜索引擎。 2.2.2整体结构: 目前，在国内外各主要商业搜索引擎在技术上主要使用了全文检索技术，下图为基于使用全文检索技术的搜索引擎的整体结构。基于全文检索技术的搜索引擎主要由三部分组成，如图所示，信息采集器（网络爬虫），索引器、搜索接口。 图2 搜索引擎的整体结构2.3网络爬虫： 2.3.1定义：网络爬虫是一个自动提取网页的程序，它为搜索引擎从Web上下载网页，是搜索引擎的重要组成部分。2.3.2基本原理：爬虫从一个或若干初始网页的URL 开始，通过分析该URL 的源文件，提取出新的网页链接，继而通过这些链接继续寻找新的链接，这样一直循环下去，直到抓取并分析完所有的网页为止。当然这是理想状态下爬虫的执行过程，但是实际上要抓取Internet上所有的网页是不可能完成的。从目前公布的数据来看，最好的搜索引擎也只不过抓取了整个Internet40%的网页。这有两个原因，其一是网络爬虫设计时的抓取技术瓶颈造成的，无法遍历所有的网页，很多网页链接不能从其他网页中得到。其二是存储技术和处理技术造成的，如果按照每个页面的平均的大小是20K，那么100 亿个页面的大小就是200000G，对于现在的存储技术来说是个挑战。 2.3.3爬行策略： （1）广度优先： 广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。该算法的设计和实现相对简单，可以覆盖尽可能多的网页。本课题采用广度优先策略。对图1 中的节点进行访问：1-2-3-4-5-6-7-8 （2）深度优先：深度优先搜索策略是一种在开发Spider 的早期使用得较多的方法，是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。当不再有其他超链可选择时，说明搜索已经结束。对图1 中的节点进行访问:1-2-5-6-3-7-4-82.3.4爬虫物理分布架构 图3 爬虫物理分布架构爬虫部分阶段性地从互联网上抓取内容。存储库存储爬虫下载下来的网页，是分布式的和可扩展的存储系统。2.3.5简易爬虫实现流程图 4. 爬虫流程图图 简易爬虫爬取网页的流程2.3.6 单个网络爬虫的系统结构图图5 单个Spider的系统结构单个Spider的系统结构如上图所示.每个爬虫从一组种子URL开始,首先根据初始URL并按照机器人拒绝协议检测被访问主机是否允许访问该URL,通过检测后由HTTP/HTTPS下载模块下载该网页。URL抽取器从下载的网页中抽取出新的URL，然后由URL过滤器逐个检测URL是否符合过滤器限制。最后，用哈希函数计算各个URL的哈希值，如果属于本Spider的爬行范围，则将该URL加入到本地URL数据库中；否则把该URL插入到URL发送队列中，由URL分发器定时转发给对应的Spider.3.主题爬虫 3.1 定义 主题网络爬虫就是根据一定的网页分析算法过滤与主题无关的链接，保留主题相关的链接并将其放入待抓取的URL队列中；然后根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止。所有被网络爬虫抓取的网页将会被系统存储，进行一定的分析、过滤，并建立索引，对于主题网络爬虫来说，这一过程所得到的分析结果还可能对后续的抓取过程进行反馈和指导。 3.2抓取的网页与主题的相关性决定策略（1） 行业搜索：比如机票搜索，抓取的是各大航空公司网站和代理人网站上面的数据。这种方法适合小型行业搜索引擎。（2） 根据得到的网页的内容，判断网页内容和主题是否相关。如果一个网页是和主题相关的，在网页中的标题、正文、超链接中，通常会有一些和主题相关的关键词。在面向主题的搜索中，这种词叫做导向词，给每个导向词一个权重，就能够优先访问和主题相关的URL。（3）针对网页连接进行评分。（后面着重讨论PageRank算法）3.3主题爬虫URL的处理流程 图6 3.4抓取算法 3.4.1在介绍算法的开始需要先做两个定义定义1父网页：网页A中有url链接到网页B，那么网页A就是网页B的父网页。定义2子网页：网页A中有url链接到网页B，那么网页B就是网页A的子网页。 爬虫抓取过程中使用了五个队列，分别是等待队列，处理队列，错误队列，完成队列，抛弃队列。等待队列：爬虫解析到的url先保存到等待队列中，在等待队列中的u rI按照特定的排序法则进行排序，等候爬虫的抓取。处理队列：url正在被抓取时放进抓取队列，目的是防止url被同时多次抓取。错误队列：在抓取过程中出错的urI保存到错误队列。完成队列：一个url被爬虫完全抓取之后就将url放进完成队列。3.4.2相关度计算 在基于HTML协议的网页中，每一个url的链接文本最能概括表达url所指向的网页内容，在网页中有一个链接模型为text，基于网页结构的明确性，text往往是一个非常精确的概括性描述文字。在这种结构基础上，我们采用向量空间模型来计算链接文本text的相似度，用它标记urltext的相关度。模型公式如公式(1)。 其中Wij表示特征向量在链接文本中的权值，Wir表示特征向量i在主题特征库中的权值，R代表主题特征向量，SIM(Pj，R)表示链接文本Pi的相关度。3.4.3 爬虫的抓取算法如下：(1) 将初始页面url集合放进等待队列，分配每个url一个相关性消息值m，并给每个url同样的相关度值。 这个相对于后面将要计算到的值较大。初始页面会人为根据主题进行筛选，所以与主题的紧密度高。人为的给定一个高的相关度值优点有两个，首先，减少爬虫的计算量，这些种子站点不需要通过相关度的计算。其次，可以在等待队列中置于较靠前的位置，在以后的更新过程中，可以优先更新。(2) 对等待队列中的url，先根据m值大小排序，再根据相关度的大小排序。(3) 根据第二步排好序的等待队列，将排序最前的url拿出放进处理队列，爬虫开始抓取。(4) 下载网页到本地磁盘，并建立索引，然后将url地址放进完成队列。(5)利用解析器解析出网页中的链接与对应的链接文本，利用公式1计算链接地址的相关度值。(6) 将第5步得到的相关度值与相关度阀值f进行比较，其结果分为三种情况：第一种情况是相关度值大于相关度阀值，且父网页的相关性消息m值等于初始值，则直接传递父网页的m 值给子网页。第二种情况是相关度值大于相关度阀值，且父网页的相关性消息m 值小于初始值，则恢复m 值为初始值，传递m 值给子网页。第三种情况是相关度值小于相关度阀值，则将父网页的m 值乘以遗传基因比例b传递子网页的(b值大于0小于1)，子网页的相关性消息值是m*b。(7) 将url，m值，相关度值放进等待队列，重复第二步。(8) 算法结束。3. PageRank算法PageRank算法是由Google公司两个创始人Sergey及LarryPage提出的一种搜索引擎排序算法。先给每个网页赋予一个PageRank值，那么对于用户查询串分词后得到关键字的集合，Q = ，通过搜索引擎中的索引器，得到一个匹配的网页集合PageSet=，然后对中的网页按PageRank值高低进行排序，把排序高的前面K个网页返回给用户。3.1 PageRank(p)计算公式 PageRank是基于这样一个假设：从许多优质的网页上链接过来的网页，必定也是优质网页。它的特点跟用户的查询过程是不相关的，而跟网页之间的链接结构相关，这个值一般是预先计算好的。它赋予每一个网页p一个特定的Rank值，记为PageRank(p)，计算公式为：由此可见，某个网页文件的PageRank值为所有链入该网页的其他网页的PageRank值除以它们各自的链出网页个数 (网页出度）的和。A表示所有指向网页p的网页集合，|P|表示网页p的链出网页个数。PageRank(p)的值跟网页p链入网页个数、网页p链入网页的链出网页个数以及网页p链入网页的质量（重要性）这三个因素有关。基于这样一个假设：一个用户随机地访问网络，该用户到达一个随机网页文件的概率为c，或者随机地沿着一个链接返回到已访问网页文件的概率为1-c，同时假设该用户不会沿着刚才的访问网页链接返回到已访问过的网页文件。3.2 PageRank的计算方法幂法转化公式为 的值，其中矩阵A为以下做算法举例：1)对网页链接关系进行简化，建立一个网页间的链接关系的模型。 用矩阵P表示这个链接关系，如果页面i向页面j有链接情况，则pij = 1，否则pij = 0。如果网页文件总数为N，那么这个网页链接矩阵就是一个一行N列的矩阵。设有三个网页A、B、C，A链接B、C，B链接C，C链接A、B，那么 。2) 将这个一行N列的矩阵P进行倒置操作，并把各个列矢量除以它们各自的链接网页个数，就得到了PageRank矩阵。转换后的矩阵也常常称为推移概率行列，一般记为。3) A矩阵计算过程。易知 设C=0.5,得到.4) 循环迭代计算PageRank。令每个网页的初始PageRank的值均为1， 比较x与b的值，如果差别较大，则将b赋给x,继续计算。反复迭代，直到最后两次的结果近似或相同，则迭代结束。用幂法计算PageRank总是收敛的，即计算的次数为有限次。3.3Rank数值的含义 有许多可以查询PageRank的工具或网页，会给出一个110分的数字，数字越高，Rank就越高，具体含义如表1所示。 表1 Rank数值的含义Rank数值含 义02表示目前没有太多外部链接连到此网站；但不意味此网站在Google上排名就一定很低。假如此网页讨论的主题够专业，范围够狭窄，很有可能网友在Google上面搜寻时，此网页可以排名在很前面3一般经营两年以上的网站大多能达到这个成绩；这是很不错的成绩，但是在热门搜寻领域里的排名不会很理想4能达到这个数字，证明链接到此的网站外部连接“质”、“量”俱佳。不仅链接到此网站的网站数多，而且链接到此网站本身的PageRank也相当高5表示有不少“权威性”的重量级网站链接到此网站；通常Google内部会自定义一些它们认为特别重要的网站，如果某一网站能取得这些网站的链接，Rank分数就会上升得很快，相应的排名得到提升6能突破5到6的网站非常少，如果此网站达到5或6，说明此网站有很不错的知名度的大站，而且此网站的反向链接够多也够重量710能够达到这个级别的网站相对于整个网络来说极少4. 程序及算法实验 4.1宽度crawler应用程序 根据上面的原理，进行爬虫的的设计。 对应上面的流程图，简易爬虫由下面几个类组成，各个类职责如下：Queue.java： 实现了一个简单的队列，在 LinkDB.java 中使用了此类。LinkDB.java：用来保存已经访问的 url 和待爬取的 url 的类，提供url出队入队操作。FileDownloader.java：用来下载 url 所指向的网页。HtmlParserTool.java： 用来解析网页文本。LinkFilte