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

课程设计报告(2010--2011年度第一学期)名称：《软件设计与实践》课程设计题目：网络爬虫研究与应用院系：计算机系班级：学号：学生姓名：指导教师：软件设计与实践教学组设计周数：两周成绩：日期：2011年1月14日《软件设计与实践》课程设计任务书一、目的与要求1．了解网络爬虫的架构和工作原理，实现网络爬虫的基本框架；2．开发平台采用JDK1.60eclipse集成开发环境。二、主要内容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掌握crawler的工作原理及实现方法；1.2了解爬虫架构；1.3熟悉网页抓取的整个流程及操作步骤；1.4掌握宽度优先，深度优先算法，并实现宽度crawler应用程序的编写、调试和运行；1.5掌握主题爬行及内容分析技术；1.6实现一个最基础的主题爬虫的过程；1.7理解pageRank算法，并编程验证；二、设计正文网络爬虫研究与应用[摘要]:本文通过对网络爬虫研究的逐步展开，讨论了爬虫的相关概念与技术，并通过实验设计了简单的基于宽度优先的爬虫和主题式爬虫。最后，讨论了PageRank算法。[关键词]:网络爬虫爬虫应用PageRank算法1.引言随着网络技术的迅速发展，万维网已经成为人们获取信息的重要渠道，如何高效地提取并利用这些信息成为一个巨大的挑战。现阶段的搜索引擎，作为一个辅助人们检索信息的工具成为用户访问万维网的入口和指南。但是，这些通用性搜索引擎也存在着一定的局限性，如：(1)(2)搜索引擎提高覆盖面的目标与膨胀的网络信息之间的矛盾日益加深。(3)搜索引擎大多提供基于关键字的检索，难以支持根据语义信息提出的查询。为了解决上述问题，定向抓取相关网页资源的主题爬虫应运而生。主题爬虫是一个自动下载网页的程序，它根据既定的抓取目标，有选择的访问万维网上的网页与相关的链接，获取所需要的信息。与通用爬虫不同，主题爬虫并不追求大的覆盖，而将目标定为抓取与某一特定主题内容相关的网页，为面向主题的用户查询准备数据资源。2.网络爬虫2.1Internet上的网页关系建模如下图所示，如果将网页看成是图中的某一个节点，而将网页中指向其他网页的链接看成是这个节点指向其他节点的边，那么我们很容易将整个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的处理流程图63.4抓取算法3.4.1在介绍算法的开始需要先做两个定义定义1．父网页：网页A中有url链接到网页B，那么网页A就是网页B的父网页。定义2．子网页：网页A中有url链接到网页B，那么网页B就是网页A的子网页。爬虫抓取过程中使用了五个队列，分别是等待队列，处理队列，错误队列，完成队列，抛弃队列。等待队列：爬虫解析到的url先保存到等待队列中，在等待队列中的urI按照特定的排序法则进行排序，等候爬虫的抓取。处理队列：url正在被抓取时放进抓取队列，目的是防止url被同时多次抓取。错误队列：在抓取过程中出错的urI保存到错误队列。完成队列：一个url被爬虫完全抓取之后就将url放进完成队列。3.4.2相关度计算在基于HTML协议的网页中，每一个url的链接文本最能概括表达url所指向的网页内容，在网页中有一个链接模型为ahref=“urltext”text／a，基于网页结构的明确性，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=key1,key2,…,keyn，通过搜索引擎中的索引器，得到一个匹配的网页集合PageSet=pi,pk,pm,pn,…，然后对pi,pk,pm,pn,…中的网页按PageRank值高低进行排序，把排序高的前面K个网页返回给用户。3.1PageRank(p)计算公式PageRank是基于这样一个假设：从许多优质的网页上链接过来的网页，必定也是优质网页。它的特点跟用户的查询过程是不相关的，而跟网页之间的链接结构相关，这个值一般是预先计算好的。它赋予每一个网页p一个特定的Rank值，记为PageRank(p)，计算公式为：由此可见，某个网页文件的PageRank值为所有链入该网页的其他网页的PageRank值除以它们各自的链出网页个数(网页出度）的和。A表示所有指向网页p的网页集合，|P|表示网页p的链出网页个数。PageRank(p)的值跟网页p链入网页个数、网页p链入网页的链出网页个数以及网页p链入网页的质量（重要性）这三个因素有关。基于这样一个假设：一个用户随机地访问网络，该用户到达一个随机网页文件的概率为c，或者随机地沿着一个链接返回到已访问网页文件的概率为1-c，同时假设该用户不会沿着刚才的访问网页链接返回到已访问过的网页文件。3.2PageRank的计算方法——幂法转化公式为xAnlim的值，其中矩阵A为meeCCPAt/)1('以下做算法举例：1)对网页链接关系进行简化，建立一个网页间的链接关系的模型。用矩阵P表示这个链接关系，如果页面i向页面j有链接情况，则pij=1，否则pij=0。如果网页文件总数为N，那么这个网页链接矩阵就是一个一行N列的矩阵。设有三个网页A、B、C，A链接B、C，B链接C，C