网络爬虫的设计与实现

1、 毕业设计（论文）说明书学 院 软件学院 专 业 软件工程 年 级 2007 姓 名 张凤龙 指导教师 陈锦言 2011年 3月 6 日毕业设计（论文）任务书题目：网络爬虫设计与实现学生姓名 张凤龙 学院名称 软件学院 专 业 软件工程 学 号 3007218139 指导教师 陈锦言 职 称 讲师 1、 原始依据（包括设计或论文的工作基础、研究条件、应用环境、工作目的等。）互联网是一个庞大的非结构化的数据库，将数据有效的检索并组织呈现出来有着巨大的应用前景。搜索引擎作为一个辅助人们检索信息的工具成为用户访问万维网的入口和指南。但是，这些通用性搜索引擎也存在着一定的局限性。不同领域、不同背景的用

2、户往往具有不同的检索目的和需求，通用搜索引擎所返回的结果包含大量用户不关心的网页。所以需要一个能基于主题搜索的满足特定需求的网络爬虫。为了解决上述问题，参照成功的网络爬虫模式，对网络爬虫进行研究，从而能够为网络爬虫实现更深入的主题相关性，提供满足特定搜索需求的网络爬虫。2、 参考文献1winter中文搜索引擎技术解密：网络蜘蛛 m北京：人民邮电出版社，2004年2sergey等the anatomy of a large-scale hypertextual web search engine m北京：清华大学出版社，1998年3wisenutwisenut search engine whi

3、te paper m北京：中国电力出版社，2001年4gary r.wright w.richard stevenstcp-ip协议详解卷3：tcp事务协议，http，nntp和unix域协议 m北京：机械工业出版社，2002 年1月.5罗刚 王振东自己动手写网络爬虫m北京：清华大学出版社，2010年10月.6李晓明，闫宏飞，王继民搜索引擎：原理、技术与系统华夏英才基金学术文库m北京：科学出版社，2005年04月.3、 设计（研究）内容和要求（包括设计或研究内容、主要指标与技术参数，并根据课题性质对学生提出具体要求。）本课题的主要目的是设计面向主题的网络爬虫程序，同时需要满足的是具有一定的性能

4、，要考虑到网络爬虫的各种需求。网络爬虫应用宽度搜索技术。对url进行分析，去重。网络爬虫使用多线程技术，让爬虫具备更强大的抓取能力。网络爬虫要实现对特定主题的爬取。网络爬虫还要完成信息提取任务，对于抓取回来的网页提取出来:新闻、电子图书、行业信息等。对网络爬虫的连接网络设置连接及读取时间，避免无限制的等待。研究网络爬虫的原理并实现爬虫的相关功能。最终实现的网络爬虫应该能根据设定的主题，从设定的url进行一定深度的搜索，并最终得到需要的数据。 指导教师（签字）年 月 日审题小组组长（签字）年 月 日天津大学本科生毕业设计（论文）开题报告课题名称网络爬虫设计与实现学院名称软件学院专业名称软件工程学

5、生姓名张凤龙指导教师陈锦言（内容包括：课题的来源及意义，国内外发展状况，本课题的研究目标、研究内容、研究方法、研究手段和进度安排，实验方案的可行性分析和已具备的实验条件以及主要参考文献等。）1 课题的来源及意义互联网是一个庞大的非结构化的数据库，将数据有效的检索并组织呈现出来有着巨大的应用前景。搜索引擎作为一个辅助人们检索信息的工具成为用户访问万维网的入口和指南。但是，这些通用性搜索引擎也存在着一定的局限性。不同领域、不同背景的用户往往具有不同的检索目的和需求，通用搜索引擎所返回的结果包含大量用户不关心的网页。为了解决这个问题，一个灵活的爬虫有着无可替代的重要意义。2 国内外发展状况对于网络爬

6、虫的研究从上世纪九十年代就开始了，目前爬虫技术已经趋见成熟，网络爬虫是搜索引擎的重要组成部分。网络上比较著名的开源爬虫包括nutch，larbin，heritrix。网络爬虫最重要的是网页搜索策略（广度优先和最佳度优先）和网页分析策略（基于网络拓扑的分析算法和基于网页内容的网页分析算法）。3 研究目标本论文主要研究搜索引擎的搜索器（网络爬虫程序）的设计与实现,实现简单的可在后台自动运行的爬虫程序。1. 可以多线程进行抓取。2. 可以进行面向主题的抓取。四研究内容本课题研究的内容是如何使网络爬虫灵活高效。1. 如何具备更强的抓取能力。2. 如何分辨重复的网页内容。3. 如何确定主题相关性。4.

7、对于网络时延等的处理。五研究方法网络爬虫应用宽度搜索技术。对url进行分析，去重。网络爬虫使用多线程技术，让爬虫具备更强大的抓取能力。网络爬虫还要完成信息提取任务，对于抓取回来的网页提取出来新闻等信息。对网络爬虫的连接网络设置连接及读取时间，避免无限制的等待。研究网络爬虫的原理并实现爬虫的相关功能。6 研究手段参考网上开源的网络爬虫和各种网络爬虫相关的书籍，在windows系统环境下开发。5 本课题进度安排： 2010.12.202011.03.10 查阅资料完成任务书 ，完成开题报告 2011.03.112011.03.12 开题报告会 2011.03.132011.04.24 查阅资料，进

8、行论文基本章节的写作，完成初稿， 并完成进行代码编写 2011.04.252011.04.30 毕业设计中期报告会 2011.05.012011.05.22 系统设计结束并再次检查系统的可靠性。2011.05.232011.06.22 完成论文及答辩6 本课题可行性分析网络爬虫目前已经比较普遍，国内外有众多对网络爬虫的研究成果，大部分的技术难题已经有解决方案。所以本课题的可行性较高。8 实验条件windows 操作系统 ；互联网9 主要参考文献1winter中文搜索引擎技术解密：网络蜘蛛 m北京：人民邮电出版社，2004年2sergey等the anatomy of a large-scale

9、 hypertextual web search engine m北京：清华大学出版社，1998年3wisenutwisenut search engine white paper m北京：中国电力出版社，2001年4gary r.wright w.richard stevenstcp-ip协议详解卷3：tcp事务协议，http，nntp和unix域协议 m北京：机械工业出版社，2002 年1月.5罗刚 王振东自己动手写网络爬虫m北京：清华大学出版社，2010年10月.6李晓明，闫宏飞，王继民搜索引擎：原理、技术与系统华夏英才基金学术文库m北京：科学出版社，2005年04月.选题是否合适： 是

10、 否课题能否实现： 能 不能指导教师（签字）年 月 日选题是否合适： 是 否课题能否实现： 能 不能审题小组组长（签字）年 月 日摘 要本课题的主要目的是设计面向主题的网络爬虫程序，同时需要满足的是具有一定的性能，考虑到网络爬虫的各种需求。网络爬虫应用宽度搜索技术。对url进行分析，去重。网络爬虫使用多线程技术，让爬虫具备更强大的抓取能力。对网络爬虫的连接网络设置连接及读取时间，避免无限制的等待。为了适应不同需求，使网络爬虫可以根据预先设定的主题实现对特定主题的爬取。研究网络爬虫的原理并实现爬虫的相关功能。关键词：网络爬虫；面向主题；多线程abstractthe main purpose of

11、 this project is to design subject-oriented web crawler process which is also required to meet certain performance, taking into account the diverse needs of web crawlers.web crawler uses the technology. of breadth-first search.web crawler uses multi-threaded technology, so that spiders crawl can hav

12、e more powerful capabilities.set connection time and read time of the web connection of the web crawler , to avoid unlimited waiting.in order to meet different needs, so that crawlers can achieve pre-set theme crawling a specific topic.research the principle web crawler and and realize the related f

13、unctions.key words：web crawler; subject-oriented; multi-threading 天津大学2007届本科生毕业设计（论文）目录第一章概述11.1课题背景11.2网络爬虫的历史和分类21.2.1网络爬虫的历史21.2.2网络爬虫的分类31.3网络爬虫的发展趋势4第二章 相关技术背景62.1网络爬虫的定义62.2网页搜索策略介绍62.2.1广度优先搜索策略62.2.2最佳优先搜索策略72.3判断相关度算法7第三章 网络爬虫模型的分析和概要设计93.1网络爬虫的模型分析93.2网络爬虫的搜索策略93.3网络爬虫的主题相关度判断103.4网络爬虫的概要

14、设计12第四章 网络爬虫模型的设计和实现154.1网络爬虫总体设计154.2网络爬虫具体设计154.2.1爬取网页154.2.2分析网页164.2.3判断相关度174.2.4保存网页信息184.2.5数据库设计和存储184.2.6多线程的实现184.2.7附加功能194.2.8整体流程19第五章测试21第六章总结和展望24天津大学2007届本科生毕业设计（论文）第一章概述1.1课题背景 网络爬虫，是一种按照一定的规则，自动的抓取万维网信息的程序或者脚本。另外一些不常使用的名字还有蚂蚁，自动索引，模拟程序或者蠕虫。 网络检索功能起于互联网内容爆炸性发展所带来的对内容检索的需求。搜索引擎不断的发展

15、,人们的需求也在不断的提高,网络信息搜索已经成为人们每天都要进行的内容.如何使搜索引擎能时刻满足人们的需求。最初的检索功能通过索引站的方式实现，而有了网络机器人，即网络爬虫这个技术之后，搜索引擎的时代便开始一发不可收拾了。1.2网络爬虫的历史和分类1.2.1网络爬虫的历史在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生了。现代意义上的搜索引擎的祖先，是1990年由蒙特利尔大学学生alan emtage发明的archie。虽然当时world wide web还未出现，但网

16、络中文件传输还是相当频繁的，而且由于大量的文件散布在各个分散的ftp主机中，查询起来非常不便，因此alan archie工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于 archie深受用户欢迎，受其启发，美国内华达system computing services大学于1993年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外，已能检索网页。当时，“机器人”一词在编程者中十分流行。电脑“机器人”（computer robot）是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门

17、用于检索信息的“机器人”程序象蜘蛛一样在网络间爬来爬去，因此， 搜索引擎的“机器人”程序就被称为“蜘蛛”程序。世界上第一个用于监测互联网发展规模的“机器人”程序是matthew gray开发的world wide web wanderer。刚开始它只用来统计互联网上的服务器数量，后来则发展为能够检索网站域名。与wanderer相对应，martin koster于1993年10月创建了aliweb，它是archie的http版本。aliweb不使用“机器人”程序，而是靠网站主动提交信息来建立 自己的链接索引，类似于现在我们熟知的yahoo。随着互联网的迅速发展，使得检索所有新出现的网页变得越来越

18、困难，因此，在matthew gray的wanderer基础上，一些编程者将传统的“蜘蛛”程序工作原理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从跟踪 一个网站的链接开始，就有可能检索整个互联网。到1993年底，一些基于此原理的搜索引擎开始纷纷涌现，其中以jumpstation、the world wide web worm（goto的前身，也就是今天overture），和repository-based software engineering (rbse) spider最负盛名。然而jumpstation和www worm只是以搜索工具在数据库中找到匹配信息的先后次

19、序排列搜索结果，因此毫无信息关联度可言。而rbse是第一个在搜索结果排列中引入关键字串匹配程 度概念的引擎 最早现代意义上的搜索引擎出现于1994年7月。当时michael mauldin将john leavitt的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的lycos。同年4月，斯坦福（stanford）大学的两名博士生，david filo和美籍华人杨致远（gerry yang）共同创办了超级目录索引yahoo，并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已 达数百家，其检索的信息量也与从前不可同日而语。比如最近风头正劲的googl

20、e，其数据库中存放的网页已达30亿之巨。随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应目前的市场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的搜索引 擎技术和搜索数据库服务提供商。象国外的inktomi，它本身并不是直接面向用户的搜索引擎，但向包括overture（原goto）、 looksmart、msn、hotbot等在内的其他搜索引擎提供全文网页搜索服务。国内的百度也属于这一类（注），搜狐和新浪用的就是它的技术。因此 从这个意义上说，它们是搜索引擎的搜索引擎。1.2.2网络爬虫的分类网络爬虫种类繁多，如果按照部署在哪里分，可以分成：1，服务器侧：一般是一个多

21、线程程序，同时下载多个目标html，可以用php， java, python等做，一般综合搜索引擎的爬虫这样做。但是，如果对方讨厌爬虫，很可能封掉服务器的ip，服务器ip又不容易改，另外耗用的带宽也是较贵。2，客户端：很适合部署定题爬虫，或者叫聚焦爬虫。做一个与google，百度等竞争的综合搜索引擎成功的机会微乎其微，而垂直搜诉或者比价服务或者推 荐引擎，机会要多得多，这类爬虫不是什么页面都取的，而是只取关心的页面，而且只取页面上关心的内容，例如提取黄页信息，商品价格信息，还有提取竞争对手 广告信息的。这类爬虫可以部署很多，而且可以很有侵略性。可以低成本大量部署，由于客户端ip地址是动态的，所

22、以很难被目标网站封锁。1.3网络爬虫的发展趋势目前，大多数的搜索引擎都是基于关键词的搜索引擎。基于关键字匹配的搜索技术有较大的局限性：首先，它不能区分同形异义。其次，不能联想到关键字的同义词。web商业化至今，搜索引擎始终保持着网络上被使用最多的服务项目的地位，然而，随着网上内容的爆炸式增长和内容形式花样的不断翻新，搜索引擎越来越不能满足挑剔的网民们的各种信息需求。搜索引擎的发展面临着两大难题：一是如何跟上internet的发展速度，二是如何为用户提供更精确的查询结果。所以，传统的引擎不能适应信息 技术的高速发展，新一代智能搜索引擎作为一种高效搜索引擎技术的在当今的网络信息时代日益引起业界人士

23、的关注。搜索引擎己成为一个新的研究、开发领域。因 为它要用到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。又 由于搜索引擎有大量的用户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。目前传统搜索引擎下，百度、谷歌等大厂商垄断了网络索引市场，因为它们的存在，日益庞大的互联网内容才能突破网络黑暗状态，变成可知的一个世界。然而，传统搜索引擎并不能支持定制搜索和信息处理、挖掘，只能以web1.0的形式存在。可以预见将来互联网信息抓取、挖掘

24、和再处理，将成为人们越来越多的需求，而满足这种需求的，就是各种各样的爬虫与相关的信息处理工具。现在网络上流 行的信息采集工具、网站聚合工具，都是未来新一代爬虫的先驱，甚至已经具备其特点。但是互联网本身，不管1.0还是2.0，还没有为爬虫时代的到来做好充分准备。现在游行的seo，就是强势搜索引擎条件下对网站结构产生的影响。爬虫时代到来之后，互联网上会出现专门的信息站点，就是提供给爬虫看的站点。 传统的网络爬虫技术主要应用于抓取静态web 网页，随着ajax/web2.0的流行，如何抓取ajax 等动态页面成了搜索引擎急需解决的问题，因为ajax颠覆了传统的纯http 请求/响应协议机制，如果搜索

25、引擎依旧采用“爬”的机制，是无法抓取到ajax 页面的有效数据的。 ajax 采用了javascript 驱动的异步请求/响应机制，以往的爬虫们缺乏javascript语义上的理解，基本上无法模拟触发javascript的异步调用并解析返回的异步回调逻辑和内容。 另外，在ajax的应用中，javascript 会对dom结构进行大量变动，甚至页面所有内容都通过javascript 直接从服务器端读取并动态绘制出来。这对习惯了dom 结构相对不变的静态页面简直是无法理解的。由此可以看出，以往的爬虫是基于协议驱动的，而对于ajax 这样的技术，所需要的爬虫引擎必须是基于事件驱动的。第二章 相关技术

26、背景2.1网络爬虫的定义定义1：网络爬虫是一个自动提取网页的程序，它为搜索引擎从web上下载网页，是搜索引擎的重要组成部分。通用网络爬虫从一个或若干初始网页的url开始，获得初始网页上的url列表；在抓取网页的过程中，不断从当前页面上抽取新的url放入待爬行队列，直到满足系统的停止条件。定义2：主题网络爬虫就是根据一定的网页分析算法过滤与主题无关的链接，保留主题相关的链接并将其放入待抓取的url队列中；然后根据一定的搜索策略从队列中选择下一步要抓取的网页url，并重复上述过程，直到达到系统的某一条件时停止。所有被网络爬虫抓取的网页将会被系统存储，进行一定的分析、过滤，并建立索引，对于主题网络爬

27、虫来说，这一过程所得到的分析结果还可能对后续的抓取过程进行反馈和指导。定义3：如果网页p中包含超链接l，则p称为链接l的父网页。定义4：如果超链接l指向网页t，则网页t称为子网页，又称为目标网页。主题网络爬虫的基本思路就是按照事先给出的主题，分超链接和已经下载的网页内容，预测下一个待抓取的url及当前网页的主题相关度，保证尽可能多地爬行、下载与主相关的网页，尽可能少地下载无关网页。2.2网页搜索策略介绍 网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题，目前常见的是广度优先和最佳优先方法。 2.2.1广度优先搜索策略 广度优先搜

28、索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页，一般使用广度优先搜索方法。也有很多研究将广度优先搜索策略应用于聚焦爬虫中。其基本思想是认为与初始url在一定链接距离内的网页具有主题相关性的概率很大。另外一种方法是将广度优先搜索与网页过滤技术结合使用，先用广度优先策略抓取网页，再将其中无关的网页过滤掉。这些方法的缺点在于，随着抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。 2.2.2最佳优先搜索策略最佳优先搜索策略按照一定的网页分析算法，预测候选url与目标网页的相似度，或与主题的相关性，并选取评价最

29、好的一个或几个url进行抓取。它只访问经过网页分析算法预测为“有用”的网页。存在的一个问题是，在爬虫抓取路径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。因此需要将最佳优先结合具体的应用进行改进，以跳出局部最优点。将在第4节中结合网页分析算法作具体的讨论。研究表明，这样的闭环调整可以将无关网页数量降低30%90%。2.3判断相关度算法主题爬虫的系统组成最初考虑是对页面的过滤，不像普通爬虫对所有页面的链接进行处理，先对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含的链接和领域相关的几率也较大，这

30、样提高了爬行精度，虽然会遗漏少数页面，但综合效果是令人满意的。因此，主题相关度的分析是主题爬虫设计的关键。 （一）主题相关度计算模型垂直搜索引擎与通用搜索引擎最大的区别在于垂直搜索引擎是面向某个领域的，因而垂直搜索引擎的网络蜘蛛只采集与主题相关的网页，与主题无关的网页将被丢弃，将此类网络蜘蛛称为主题蜘蛛6-8。主题蜘蛛将网页下载到本地后，需要使用基于内容的主题判别方法计算该网页的主题相关度值，主题相关度低于某一阈值的网页被丢弃。主题相关度的计算方法有布尔模型和向量空间模型两种模型算法10。1.布尔模型。在主题判别时，布尔模型是很容易实现的。在布尔模型9中，一个文档通过一个关键词集合来表示。同时

31、，某个主题也以关键词集合的形式来表示。在判断文档与某主题的相关度的过程中，相当于是计算两个关键词集合的交集。对基于布尔模型的主题判别模型来说，交集中含有的元素越多，则认为与主题的相关度就越高。2.空间向量模型。向量空间模型11（vector space model）由salton等人于20世纪60年代末提出，是一种简便、高效的文本表示模型，其理论基础是代数学。与布尔模型不同，向量空间模型把用户的查询要求和数据库文档信息表示成由检索项构成的向量空间中的点（向量），而通过计算向量之间的距离来判定文档和查询之间的相似程度（例如，用它们之间夹角的余弦作为相似性度量）。然后，根据相似程度排列查询结果。在

32、向量空间模型中，文档被形式化为n维空间中的向量，把关键词的个数n作为空间向量的维数，每个关键词的权值 作为每一维分量的大小，则主题用向量表示为：a=(a1,a2,an),i=1,2,n,ai=wi对于页面进行分析，统计关键词出现的频率，并求出频率之比，以出现的频率最高的关键词作为基准，其频率用xi=1表示，通过频率比，求出其他关键词的频率 ，则该页面对应向量的每一维分量为xiwi。指定一个阈值r，当cos=r时就可以认为该页面和主题是比较相关的，r的取值需要根据经验和实际要求确定，如果想获得较多的页面，可以把r设小一点，要获得较少的页面可以把r设的大一点。（二）布尔模型与空间向量模型分析布尔模

33、型的主要缺陷在于每个关键词的权重都是一样的，它不支持设定关键词的相对重要性，但是其优点也较为明显，它易于实现，计算代价较小。向量空间模型最大优点在于它在知识表示方法上的巨大优势。在该模型中，文档的内容被形式化为多维空间中的一个点，以向量的形式给出。也正是因为把文档以向量的形式定义到实数域中，才使得模式识别和其他领域中各种成熟的算法和计算方法得以采用，极大地提高了自然语言文档的可计算性和可操作性。通过对空间向量模型和布尔模型的介绍，我们知道现在垂直搜索引擎大多采用空间向量模型计算主题相关性。这样极大的提高到主题爬虫的效率，也极大的提高了垂直搜索引擎的应用效率，给客户带来了高效的查询效果。与在进行

34、页面的主题相关度分析后，当其主题相关度符合要求时将处理该页面中的所有链接，但其中的链接指向的页面也可能有许多偏离了主题，这一点在网页的标题上就可以看出，现在大多数网页的标题已经很明显的给出了文本的主要描述对象，所以传统的空间模型策略没有注意到网页标题这个重要的角色。针对此提出了一种基于网页标题的空间向量模型主题相关度计算方法。第三章 网络爬虫模型的分析和概要设计3.1网络爬虫的模型分析 首先建立url任务列表，即开始要爬取的url。由url任务列表开始，根据预先设定的深度爬取网页，同时判断url是否重复，按照一定算法和排序方式搜索页面，然后对页面按照一定算法进行分析，并提取相关url，最后将所

35、得url返回任务列表。之后将任务列表中url重新开始爬取，从而使网络爬虫进行循环运行。3.2网络爬虫的搜索策略 本文的搜索策略为广度优先搜索策略。如下图3-1所示。图3-1广度优先搜索策略示意图 1） 定义一个状态结点采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。不同的问题需要用不同的数据结构描述。2）确定结点的扩展规则根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目

36、标状态的结点的过程。广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，.对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。结点的扩展规则也就是如何从现有的结点生成新结点。对不同的问题，结点的扩展规则也不相同，需要按照问题的要求确定。

37、3）搜索策略为了便于进行搜索，要设置一个表存储所有的结点。因为在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般设计成队列的数据结构。搜索的步骤一般是：（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展.。最终可能产生两种结果：找到

38、目标结点，或扩展完所有结点而没有找到目标结点。3.3网络爬虫的主题相关度判断主题爬虫的系统组成最初考虑是对页面的过滤，不像普通爬虫对所有页面的链接进行处理，先对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含的链接和领域相关的几率也较大，这样提高了爬行精度，虽然会遗漏少数页面，但综合效果是令人满意的。因此，主题相关度的分析是主题爬虫设计的关键。主题蜘蛛将网页下载到本地后，需要使用基于内容的主题判别方法计算该网页的主题相关度值，主题相关度低于某一阈值的网页被丢弃。（1） 什么是网页标题通常浏览一个网页时，通过浏览器顶端

39、的蓝色显示条出现的信息就是“网页标题”。在网页html代码中，网页标题位于标签之间。网页标题是对于一个网页的高度概括，一般来说，网站首页的标题就是网站的正式名称，而网站中文章内容页面的标题就是这文章的题目，栏目首页的标题通常是栏目名称。当然这种一般原则并不是固定不变的，在实际工作中可能会有一定的变化，但是无论如何变化，总体上仍然会遵照这种规律12。例如，现在会看到很多网站的首页标题较长，除了网站名称之外，还有网站相关业务之类的关键词，这主要是为了在搜索引擎搜索结果中获得排名优势而考虑的，也属于正常的搜索引擎优化方法。因为一般的公司名称（或者品牌名称）中可能不包含核心业务的关键词，在搜索结果排名

40、中将处于不利地位。（二）网页标题的重要性以google为例，google会对其标题标签（meta title）中出现的关键字给予较高的权值。所以应当确保在网站的标题标签中包含了最重要的关键词，即应围绕最重要的关键词来决定网页标题的内容。不过网页的标题不可过长，一般最好在35到40个字符之间。在实际操作中，网页标题不宜过短或过长。太短无法完整的表达网页信息，太长不仅不利于用户识别，而且对搜索引擎来说也加大了识别核心关键词的难度；网页标题应概括网页的核心内容。搜索引擎在进行搜索的时候，搜索结果的内容一般是网页标题、网页摘要信息和链接，要引起用户的关注，高度总结了网页内容的标题至关重要。比如戴尔中国

41、的网站首页标题为“戴尔中国（dell china）计算机，笔记本电脑，台式机，打印机，工作站，服务器，存储器，电子产品及附件等”。戴尔的首页标题中不但涵盖了最重要的公司信息，而且还包括公司的主要产品，这就是核心关键词，当用“笔记本电脑”、“台式电脑”这些关键词在谷歌中进行搜索时，戴尔公司的网页都排在第一屏的前几条位置。（2） 但是与此同时需要注意的还有网页正文的重要性，因为网页的标题和关键字很可能与正文无关，虚假关键词是通过在meta中设置与网站内容无关的关键词，如在title中设置热门关键词，以达到误导用户进入网站的目的。同样的情况也包括链接关键词与实际内容不符的情况。 具体判断主题相关度的

42、步骤 1.对标题及正文的特征项的选取是通过分词后与主题集合匹配，并通过词频计算来得到与主题向量维数相等的标题向量和正文向量。2.通过向量空间模型计算出主题和标题的相关度b。3.通过空间向量向量模型计算主题与正文的相关度c。4.主题与整个网页的相关度：a=4b+c。5.通过详细计算，设定相关度阈值为2，网页与主题的相关度a2，则认为该网页与主题相关的。3.4网络爬虫的概要设计本网络爬虫的开发目的，通过网络爬虫技术一个自动提取网页的程序，实现搜索引擎从自己想要访问的网上下载网页，再根据已下载的网页上继续访问其它的网页，并将其下载直到满足用户的需求。根据现实中不同用户的实际上的各种需求，本项目简单实

43、现主题爬虫，本网络爬虫需要达到如下几个目标：1.设计基于多线程的网络爬虫，客户端向服务器发送自己设定好请求。如图3-7所示。url配置文件url配置文件列表临界区互联网线程1搜索元url如线程2搜索元url如线程n图3-2 多线程网络爬虫概要设计图模型2.通过 http将web服务器上协议站点的网页代码提取出来。3.根据一定的正则表达式提取出客户端所需要的信息。4.广度优先搜索可从网页中某个链接出发，访问该链接网页上的所有链接，访问完成后，再通过递归算法实现下一层的访问。 本网络爬虫最终将设计成一个能够自动读写配置文件并且在后台自动执行的网络爬虫程序。网络爬虫工作流程图如图3-3所示。图3-3

44、 网络爬虫工作流程图第四章 网络爬虫模型的设计和实现4.1网络爬虫总体设计根据本网络爬虫的概要设计本网络爬虫是一个自动提取网页的程序，根据设定的主题判断是否与主题相关，再根据已下载的网页上继续访问其它的网页，并将其下载直到满足用户的需求。 1.设计基于多线程的网络爬虫。2.通过 http将待爬取url列表对应的url的网页代码提取出来。3.提取出所需要的信息并且通过算法判断网页是否和设定的主题相关。4.广度优先搜索，从网页中某个链接出发，访问该链接网页上的所有链接，访问完成后，再通过递归算法实现下一层的访问，重复以上步骤。总的来说爬虫程序根据输入获得url任务列表，即初始url种子，把初始种子

45、保存在临界区中，按照广度搜索运算法搜索抓取网页并提取url返回到临届区中，通过判断主题相关度算法判断相关度，取出不相关网页，从而使整个爬虫程序循环运行下去。4.2网络爬虫具体设计4.2.1爬取网页 主要用到的技术如下：继承htmleditorkit类，改写其中的 htmleditorkit.parser getparser()属性protect为public，用下列函数爬取网页：public class xxxxx extends htmleditorkit public htmleditorkit.parser getparser()return super.getparser(); 步骤如

46、下：1首先建立url连接。urlconnection url_c = url_test.openconnection();2设置连接超时时间和读取超时时间。url_c.setconnecttimeout(10000);url_c.setreadtimeout(10000);3. 用输入流，bufferedreader读取，并且将网页内容存储为字符串。4.2.2分析网页继承parsercallback获得网页内容/ 得到标题文本protected string urltitle = new string();/ 得到某一网页上的所有链接protected vector links = new v

47、ector();protected vector linkname = new vector();/ 得到网页上的正文文本protected string paragraphtext = new string();protected string linkandparagraph = new string();protected string encode = new string();public parser(string baseurl) base = baseurl;public string getencode() return encode;/ 获得该网页标题public stri

48、ng geturltitle() return urltitle;/ 获得该网页的所有链接public vector getlinks() return links;/ 获得所有该网页的链接名public vector getlinkname() / 获得网页正文public string getparagraphtext() public void handleendtag(html.tag t, int pos) / 处理简单标签public void handlesimpletag(html.tag t, mutableattributeset a, int pos) / 处理结束标签p

49、ublic void handlestarttag(html.tag t, mutableattributeset a, int pos) / 处理文本 标签public void handletext(char data, int pos)之后通过调用htmleditorkit.parser类，生成对象就可以直接得到分析后的网页文件。4.2.3判断相关度 算法实现步骤和算法描述：1. 对标题及正文的特征项的选取是通过分词后与主题集合匹配，并通过词频计算来得到与主题向量维数相等的标题向量和正文向量。2.通过向量空间模型计算出主题和标题的相关度b。3.通过空间向量向量模型计算主题与正文的相关度c

50、。4.主题与整个网页的相关度：a=4b+c。5.通过详细计算，设定相关度阈值为2，网页与主题的相关度a2，则认为该网页与主题相关的。输入：主题集合文本a.txt，网页url输出：主题相关度（1）get topic（string path）/根据路径获取主题文本集合（2）compulate topicweight（string topic）/求主题结合权重（3）sortanddelrepeat(intcount)/删除重复元素并排序（4）delrepeat(string segment)/删除分词后的重复元素（5）delrepeat(vector url)/删除得到的url中的重复元素（6）ge

51、tparser(string url)/获得parser实例（7）string titlestr =p.geturltitle（）/获取网页标题（8）string bodystr=p.getparagraphtext（）/获取网页文本（9）string titlestrseg=segment.segment（titlestr）/网页标题分词（10）string bodystrseg=segment.segment（bodystr）/网页文本分词（11）compulate title.length，body.length/计算标题向量长度和网页文本向量长度（12）set topicweight1

52、，titleweight1，bodyweight1；/设置权重（13）last compulate relative/计算主题相关性（14）return relative；/返回结果 根据系统设置首先是下载所有网页，而后判定主题相关性，与主题相关则放置在相关url库中，不相关的网页则丢弃。4.2.4保存网页信息1.首先建立url连接。urlconnection url_c = url_test.openconnection();2.新建pagepro类。如下：private string host;private int port;private string contenttype;priv

53、ate int contentlength;private string date;private string url;3.将数据存入新建的pagepro类中。4.将数据保存到预先输入的地址。4.2.5数据库设计和存储使用jdbc访问数据库，储存下载的网页url和下载时间信息。4.2.6多线程的实现 设计为4个线程同时进行工作。1. 从用户输入的起始url开始，递归获得指定深度的url。2. 对每个url进行分析，判断相关度。3. 下载与主题相关的网页，并存储在数据库中。第i个线程对所有url列表中序列为第0+4i url的进行同步操作，其中对储存所有url的列表执行synchronized

54、 (all_url)操作。4.2.7附加功能为了检测网络环境，防止因为不良的网络环境影响网络爬虫的爬取效率和正确略，额外添加了实时的ping功能，调用windows的命令解释器的ping功能，测试用户输入网址与当前主机的连接状况，测试当前网络状况是否良好。4.2.8整体流程爬虫代码文件构成如图4-1：图4-1代码结构构成截图 htmlparser.java这个类是改写htmleditorkit.parser getparser()方法为publichttp.java是根据输入url获取网页文档parser.java是继承parsercallback获得网页内容relative.java是判断主题与网页内容的相关性s