面向主题的网络爬虫——网页信息抽取---毕业论文

本 科 毕 业 论 文面向主题的网络爬虫网页信息抽取Subject-oriented crawlerWeb information extraction姓 名：学 号：学 院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘要随着Internet的迅猛发展，网络资源急剧增加，信息更加多元化，同时给通用搜索引擎带来了极大的挑战。因为通用搜索引擎是面向所有的Web信息检索者的，庞大的网络信息规模和高速响应要求，使其检索结果不尽人意。主题搜索引擎，是为了进一步提高搜索结果相关度的新一代搜索引擎。它提供了分类更准确、数据更全面、更新更及时的因特网搜索服务。主题搜索引擎中的信息采集，以及主题爬虫系统的搜索策略的研究，对主题搜索引擎的应用与发展都具有非常重要的作用。本文在对搜索引擎的演变和发展进行全面的综述以后，对通用搜索引擎和主题搜索引擎进行了性能的比较。引出主题搜索引擎的重要组成部分主题爬虫，并分析了主题爬虫的基本结构和工作原理。随后，对网络爬虫的一些经典页面相似度算法进行了评价。同时，重点讨论了URL搜索策略，介绍了我们的网络爬虫系统对Web页面的信息采集，并加以实现。最后，展示了我们实现的网络爬虫。论文主要研究了以下4个问题：(1) 对主题爬虫的工作原理，功能模块及基本技术进行了研究。(2) 讨论了主题爬虫经典的页面相似度算法：基于链接的页面相似度算法和基于内容的页面相似度算法；讨论了URL搜索策略算法。(3) 研究并实现了基于HTML的网页的信息抽取。(4) 实现了本系统的界面。关键词：网络爬虫；URL搜索策略；Web信息抽取AbstractWith the rapid development of Internet, network resources increase sharply, and information becomes more diversity than before. At the same time, general search engines are facing a severe challenge. Because the goal of general search engines is information of the entire web, large scale of network information and requirement of high-speed response, which makes the search result cant meet our anticipation. The subject-oriented search engine, a new- generation search engine aiming for increasing the correlation degree of searching results, makes improvement of the internet searching service with better division, more data, and higher speed. The research of information collection and searching strategy of the subject-oriented search engine plays a great role in the development of the subject-oriented search engines.In this paper, after a comprehensive overview of the evolution and development of search engines, we compared the performance of traditional and subject-oriented search engines. After that, subject-oriented spider is raised as the most important part of search engines. We analyzed basic structure and working principle about it. After introducing the classic network page similarity algorithms, we evaluate them. In the aspect of URL searching strategy, we found an improvement and discussed about it. At the same time, we analyzed the strategy of page information extraction based on HTML. The paper does research mainly in following four aspects:Firstly, we studied the working principle, functional modules and basic technology of subject-oriented crawler.Secondly, we discussed the classic page similarity algorithms, both link-based and content-based. We also discussed about the algorithm of URL searching.Thirdly, we researched information extraction based on HTML web pages strategy.Fourthly, implement the interface of this system.Key words: Web Crawler; URL search strategy; Web information extraction 目 录第一章 绪论11.1 选题背景和研究意义11.2 搜索引擎的发展历程21.3 国内外研究现状41.4 文本的主要工作和论文结构6第二章背景知识82.1 搜索引擎的分类82.1.1 通用搜索引擎82.1.2 主题搜索引擎92.1.3 搜索引擎按工作方式的分类102.2 网络爬虫122.2.1 网络爬虫的概念122.2.2 网络爬虫工作原理132.2.3 网络爬虫的主要技术问题152.3 搜索引擎的评价标准172.4 面向主题的信息提取172.4.1 面向主题的信息提取分类182.4.2 面向主题的Web信息提取的优点192.5 主题页面在Web上的分布特征202.5.1 Hub特征202.5.2 主题关联特性212.5.3 站点主题特征212.5.4 Tunnel特征212.6 本章小结22第三章 主题爬虫搜索策略研究233.1 主题爬虫URL搜索233.1.1 广度优先搜索243.1.2 深度优先搜索243.1.3 最佳优先搜索243.1.4 改进的搜索策略243.2 主题页面相关度判断263.2.1 基于链接的相关性算法273.2.2 基于内容的相关性算法293.3 本章小结30第四章 网页信息抽取的研究与实现314.1 网页信息抽取的研究314.1.1 网页主题信息抽取概述314.1.2 网页主题信息抽取目标314.2 网页主题信息抽取的实现334.2.1 基于分块的网页主题信息抽取流程334.2.2 网页HTML标签文档清洗334.2.3 基于容器标签的粗粒度划分344.2.4 分块器页面结构分析384.2.5 页面的超链接提取384.3 界面设计394.4 本章小结40第五章 系统展示41第六章 总结44参考文献45致谢46ContentsChapter 1 Introduction11.1 Background of the topics and research significance11.2 History of the development of search engines21.3 Research status at home and abroad41.4 Main work and structure of this paper6Chapter 2 Background knowledge82.1 Categories of search engines82.1.1 General search engines82.1.2 Subject-oriented search engines92.1.3 Distributed according to work102.2 Crawler122.2.1 The concept of crawler122.2.2 Working principle of crawler132.2.3 Main technologies of crawler152.3 Evaluation standard of search engines172.4 Information extraction of subject-oriented web172.4.1 Categories of extraction of subject-oriented web182.4.2 Advantages of extraction of subject-oriented web192.5 Distribution features of subject-oriented page on web202.5.1 Hub feature202.5.2 Themes related feature212.5.3 Site theme feature212.5.4 Tunnel feature212.6 Summary of this chapter22Chapter 3 Research of subject-oriented searching strategy233.1 URL searching of subject-oriented crawler233.1.1 Breadth-first searching243.1.2 Depth-first searching243.1.3 Heuristic-first searching243.1.4 Improved searching strategy243.2 Relevance judgments of subject-oriented page263.2.1 Link-based relevance algorithm273.2.2 Content-based relevance algorithm293.3 Summary of this chapter30Chapter 4 Research and implementation of information extraction314.1 Research of information extraction314.1.1 Summarize of subject information extraction314.1.2 Target of subject information extraction314.2 Implementation of subject information extraction334.2.1 Flow of partition-based subject information extraction334.2.2 Cleaning of HTML document334.2.3 Vessel-based coarse partition344.2.4 Analyze the structure of page384.2.5 Extraction of Hyperlink384.3 Interface design394.4 Summary of this chapter40Chapter 5 System displaying41Chapter 6 Summary44References45Gratitude46VI网页信息抽取第一章 绪论在进入正式的研究和分析之前，我们首先要明确此课题的研究状况和研究背景，这样有助于我们明确研究方向。1.1 选题背景和研究意义随着Internet的迅速发展，网络上各个领域的数据和信息也急剧增加。自上世纪九十年代www和浏览器出现以来，网络的规模就以惊人的速度增长。据美国因特网检测公司“网器”(Netcraft)28日宣布，截止2008年2月底，全球互联网网站数量超过1.6亿，较一个月前增加了450万1。网页数量也是以几何级增长，达到百亿级别。2009年初，中国网民数已跃居世界之首，将近3亿。而在2008年初，中国也只有大概140万的网民。同时，随着手机相关技术的发展，越来越多的手机用户也加入了网民的行列。在2008年6月的CHIP的调查中，有73.3%的网民认为，通用搜索引擎搜索结果重复率高。另外，还有48.3%的网民认为专业/行业搜索功能差，有49.1%的网民认为信息更新速度慢。以上均是通用搜索引擎的劣势之处。通用搜索引擎是面向大众的一种搜索引擎，其目标是尽可能大的网络覆盖率，但是，随着Web上各种信息的爆炸增长，有限的搜索引擎服务器资源与无限的网络数据资源之间的矛盾更加凸显。即使是Google这种大型通用搜索引擎，它的平均资源覆盖率也只有76%(截止2005年1月)。如图1-1所示为各大型搜索引擎的Web资源覆盖率。同时，它们还将面临着对庞大的索引数据库的信息刷新问题。图1-1 通用搜索引擎的资源覆盖率面对通用搜索引擎的种种问题以及对用户的需求的进一步挖掘，另一种形式的搜索引擎应运而生，它可以在较小的范围内取得比通用搜索引擎更令人满意的结果，以满足某些特定用户的需要，这就是主题搜索引擎。1.2 搜索引擎的发展历程搜索引擎从出现到目前已经经历了一个漫长的过程。(1) 起源：1990年，加拿大麦吉尔大学(University of McGill)计算机学院的师生开发出Archie。当时，万维网(World Wide Web)还没有出现，人们通过FTP来共享交流资源。Archie能定期搜集并分析FTP服务器上的文件名信息，并查找在各个FTP主机中的文件。用户必须输入精确的文件名才能进行搜索，Archie将告知用户哪个FTP服务器能下载该文件。虽然Archie搜集的信息资源不是网页(HTML文件)，但和搜索引擎的基本工作方式是一样的：自动搜集信息资源、建立索引、提供检索服务。所以，Archie被公认为现代搜索引擎的鼻祖。(2) 发展：Robot(机器人)专门用于检索信息的Robot程序像蜘蛛(spider)一样在网络间爬来爬去，因此，搜索引擎的Robot程序被称为spider程序。1993年Matthew Gray开发了World Wide Web Wanderer，这是第一个利用HTML网页之间的链接关系来检测万维网规模的“机器人(Robot)”程序。开始，它仅仅用来统计互联网上的服务器数量，后来也能够捕获网址URL。1994年4月，斯坦福大学(Stanford University)的两名博士生，美籍华人Jerry Yang(杨致远)和David Filo共同创办了Yahoo。随着访问量和收录链接数的增长，Yahoo目录开始支持简单的数据库搜索。因为Yahoo的数据是手工输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。1994年初，华盛顿大学(University of Washington)的学生Brian Pinkerton开始了他的小项目WebCrawler。1994年4月20日，WebCrawler正式亮相时仅包含来自6000个服务器的内容。WebCrawler是互联网上第一个支持搜索文件全部文字的全文搜索引擎，在它之前，用户只能通过URL和摘要搜索，摘要一般来自人工评论或程序自动取正文的前100个字。1994年7月，卡内基梅隆大学(Carnegie Mellon University)的Michael Mauldin将John Leavitt的spider程序接入到其索引程序中，创建了Lycos。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos第一个在搜索结果中使用了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数据量。1995年，一种新的搜索引擎形式出现了元搜索引擎(A Meta Search Engine Roundup)。用户只需提交一次搜索请求，由元搜索引擎负责转换处理，提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户。第一个元搜索引擎，是Washington大学硕士生Eric Selberg和Oren Etzioni的Meta crawler。1995年12月，DEC正式发布AltaVista。AltaVista是第一个支持自然语言搜索的搜索引擎，第一个实现高级搜索语法的搜索引擎(如AND,OR,NOT等)。用户可以用AltaVista搜索新闻组(News groups)的内容并从互联网上获得文章，还可以搜索图片名称中的文字、搜索Titles、搜索Java applets、搜索ActiveX objects。AltaVista也声称是第一个支持用户自己向网页索引库提交或删除URL的搜索引擎，并能在24小时内上线。1997年，AltaVista发布了一个图形演示系统Live Topics，帮助用户从成千上万的搜索结果中找到想要的。1997年8月，Northern light搜索引擎正式现身。它曾是拥有最大数据库的搜索引擎之一，它没有Stop Words，它有出色的Current News、7100多出版物组成的Special Collection、良好的高级搜索语法，第一个支持对搜索结果进行简单的自动分类。1998年10月之前，Google只是斯坦福大学(Stanford University)的一个小项目Back Rub。1995年博士生Larry Page开始学习搜索引擎设计，于1997年9月15日注册了的域名，1997年底，在Sergey Brin和Scott Hassan、Alan Steremberg的共同参与下，BachRub开始提供Demo。1999年2月，Google完成了从Alpha版到Beta版的蜕变。Google以网页级别(PageRank)为基础，判断网页的重要性，使得搜索结果的相关性大大增强。2006年4月，Google宣布其中文名称“谷歌”，这是Google第一个在非英语国家起的名字。Fast(All the web)公司创立于1997年，是挪威科技大学(NTNU)学术研究的副产品。1999年5月，发布了自己的搜索引擎All The Web。Fast创立的目标是做世界上最大和最快的搜索引擎，几年来庶几近之。Fast(All the web)的网页搜索可利用ODP自动分类，支持Flash和pdf搜索，支持多语言搜索，还提供新闻搜索、图像搜索、视频、MP3、和FTP搜索，拥有极其强大的高级搜索功能。(2003年2月25日，Fast的互联网搜索部门被Overture收购)。1996年8月，sohu公司成立，制作中文网站分类目录，曾有“出门找地图，上网找搜狐”的美誉。随着互联网网站的急剧增加，这种人工编辑的分类目录已经不试用。sohu于2004年8月独立域名的搜索网站“搜狗”，自称“第三代搜索引擎”。Openfind创立于1998年1月，其技术源自台湾中正大学吴升教授所领导的GAIS实验室。Openfind起先只做中文搜索引擎，鼎盛时期同时为三大著名门户新浪、奇摩、雅虎提供中文搜索引擎，但2000年后市场逐渐被Baidu和Google瓜分。2002年6月，Openfind重新发布基于GAIS30Project的Openfind搜索引擎Beta版，推出多元排序(PolyRankTM)，宣布累计抓取网页35亿，开始进入英文搜索领域。2000年1月，两位北大校友，超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇(加州伯克利分校博士后)在北京中关村创立了百度(Baidu)公司。2001年8月发布B搜索引擎Beta版(此前Baidu只为其它门户网站搜狐新浪Tom等提供搜索引擎)，2001年10月22日正式发布Baidu搜索引擎，专注于中文搜索。Baidu搜索引擎的其它特色包括：百度快照、网页预览/预览全部网页、相关搜索词、错别字纠正提示、mp3搜索、Flash搜索。2002年3月闪电计划(BlitzenProject)开始后，技术升级明显加快。后推出贴吧、知道、地图、国学、百科等一系列产品，深受网民欢迎。2003年12月23日，原慧聪搜索正式独立运做，成立了中国搜索。2004年2月，中国搜索发布桌面搜索引擎网络猪1.0，2006年3月中搜将网络猪更名为IG(Internet Gateway)。2005年6月，新浪正式推出自主研发的搜索引擎“爱问”。可以说搜索引擎已经有了很大的发展：从最初的只能从FTP上下载文件的Archie到如今功能强大的Google等搜索引擎，从早期的通用搜索引擎到如今各领域的主题搜索引擎。随着计算机网络的不断发展，搜索引擎还会有大的突破，它仍将是未来研究的热点之一。1.3 国内外研究现状我国搜索引擎起步比较晚，但技术发展并不比国外差，我国最具有代表的也可以说是比较成功的搜索引擎就是众所周知的百度，国外的搜索引擎最具代表的就是Google了，这两个搜索引擎很成功的占据了搜索引擎领域的老大的位置，用户覆盖率达到了90%以上。图1-2是国内外知名搜索引擎的排行和一些简短的描述。图1-2 国内外搜索引擎排行如图1-3是对国内外各知名搜索引擎目前的大概介绍。国外的搜索引擎排名依次为：Google，Overture，Yahoo，alltheweb；国内的搜索引擎排名依次是：Baidu，Sina，网易，搜狐。图1-3 国内外各知名搜索引擎大体介绍1.4 文本的主要工作和论文结构本文的主要内容是在介绍主题爬虫基本原理和相关技术的基础上，对经典的页面相关度算法和URL搜索策略进行介绍和分析，并实现了基于HTML的网页信息抽取，同时实现本系统的界面并对系统性能进行实验评价。论文主要研究以下4部分内容：(1) 爬虫的工作原理，功能模块及基本技术；(2) 页面相似度算法，URL搜索策略算法；(3) 基于HTML的网页的信息抽取；(4) 本系统的界面。本文后继章节安排如下：第二章，对搜索引擎及网络爬虫的相关知识和技术进行完整的综述和分析，为后继章节及网络爬虫系统的程序实现打下基础。第三章，分析经典的主题相关度算法：PageRank，HITS和VSM算法，分析了主题爬虫的改进URL搜索策略。第四章，分析了基于HTML的网页信息抽取策略与算法，并对其进行实现。第五章，系统的界面展示。最后总结本文的研究工作和结果，并对本文的后续研究以及研究主题的未来发展提出自己的思考、见解和展望。第二章 背景知识本章主要介绍通用搜索引擎和主题搜索引擎的区别，说明我们为什么要开发主题爬虫，并介绍了网络爬虫的工作原理和方式、主题爬虫所涉及到的相关知识，为后续的章节打好知识基础。搜索引擎的重要组成部分是网络爬虫，通用搜索引擎和主题搜索引擎的分类就是通过网络爬虫来区别的。那么，网络爬虫的工作原理到底是怎样的呢？它将用到什么技术呢？这一系列问题都将在这章中得到答案。2.1 搜索引擎的分类搜索引擎技术在计算机网络技术中发展地非常迅速，在其不断发展过程中出现了具有各种特征、符合各种要求的搜索引擎。因此搜索引擎的分类方式也不少，例如：按工作语种、搜索范围等进行分类。通用搜索引擎和面向主题的搜索引擎是搜索引擎发展过程中的有概括性的两大类，我们将首先说明这两大类搜索引擎。随后将介绍搜索引擎按工作方式的分类。2.1.1 通用搜索引擎通用搜索引擎力图覆盖Web上的所有网页，例如Google, Baidu等通用搜索引擎是通过关键字查询的方式实现的，是语义上的搜索，返回的结果倾向于知识成果，比如文章，论文，新闻等。此类搜索引擎的爬虫，根据初始URL所代表页面上的超链接，不断的拓展链接。搜集到各类资源，然后为下载的所有信息分类，建立索引，存入数据库。网络上的链接就像数据结构中的有向图。图2-1即模拟了Web网页在网络上的相互关系。图中直线代表链接，爬虫只需要网页1的URL就可以爬行剩下的所有网页。此图未对链接方向进行说明，具体的链接问题将在PageRank算法中具体说明。图2-1 通用搜索引擎爬虫爬行图通用搜索引擎是一种可供用户查找各种信息的应用程序，它可供查询的信息比较广，因此，服务器所要保存的信息量很大。用户查询时返回结果不够准确，爬虫爬行的深度也是不够的。不适合运用于专业领域的查询。2.1.2 主题搜索引擎主题搜索引擎是一种面向特定领域查询的应用程序，它会选择性的下载网页，只下载与给定主题有关的网页。通过它，我们可以得到更专业，更精确的信息。如图2.2将模拟主题爬虫的爬行。爬虫会爬行每个页面，但是，它只会将与主题相关度很大的页面下载下来(网页1、3、4、5、6、8)，其他的页面(2、7、9、10、11)将被丢弃。即主题搜索引擎是有选择性的存储特定的页面信息的。图2-2 主题搜索引擎爬虫爬行图2.1.3 搜索引擎按工作方式的分类搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎(Full Text Search Engine)、目录索引类搜索引擎(Search Index/Directory)和元搜索引擎(Meta Search Engine)。(1) 全文搜索引擎：全文搜索引擎是名副其实的搜索引擎，国外具代表性的有Google(如图2-3)、Fast/AllTheWeb、AltaVista、Inktomi、Teoma、WiseNut等，国内著名的有百度(Baidu)。它们都是通过从互联网上提取的各个网站的信息(以网页文字为主)而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是真正的搜索引擎。从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己的检索程序(Indexer)，俗称“蜘蛛”(即爬虫)程序或“机器人”(Robot)程序，并自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的7家引擎；另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如Lycos引擎。图2-3 Google首页(2) 目录索引：目录索引虽然有搜索功能，但是在严格意义上算不上是真正的搜索引擎，它仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词(Keywords)查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的Yahoo(如图2-4)。其他著名的还有Open Directory Project(DMOZ)、LookSmart、About等。国内的搜狐、新浪、网易搜索也都属于这一类。图2-4 雅虎首页(3) 元搜索引擎 (META Search Engine)：元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎有InfoSpace(如图2-5)、Dogpile、Vivisimo等，中文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。图2-5 infoSpace 首页2.2 网络爬虫网络爬虫是搜索引擎的重要组成部分。搜索引擎通常分为四个功能模块：搜索模块，用于在数据库中查询与用户输入的关键字相关的页面；索引模块：为爬下来的内容建立索引并存入数据库；爬虫模块：将Web上的网页下载下来。2.2.1 网络爬虫的概念网络爬虫(又称网页蜘蛛)，是一种按照一定的规则，自动抓取万维网信息的程序或者脚本。它是搜索引擎的关键技术和组成部分2。当然，它还可以应用于站点结构分析、内容安全检测、页面有效性分析、用户兴趣挖掘以及个性信息化获取等多种服务。Internet上的很多站点，尤其是搜索引擎，都使用爬虫下载网络信息，提供最新的数据，爬虫主要用于提供这些站点其访问过页面的副本，搜索引擎就可以对得到的页面进行索引，并将有用的页面存入数据库，用户就可以通过搜索引擎提供的界面查询到自己所需的信息了。简单地说，网络爬虫在搜索引擎中的任务是：日夜不停地在互联网的各个节点中自动爬行，从一个或一组URL开始访问，按照一定的搜索策略，尽可能多、尽可能快地从中发现和抓取信息，直到URL队列为空时停止抓取。图2-6简要的说明了网络爬虫的功能。当网络爬虫收到任务(包括关键字和URL种子)时，就可以开始爬行，将所爬的网页下载下来，经过分析后方可存到数据库，再从URL队列中取出剩下的URL，直到URL队列为空(如果是通用网络爬虫，URL是不可能为空的)或者其他停止条件。Web网络爬虫初始URL下载页面数据库下载的页面用户关键字 图2-6 网络爬虫功能简介图2.2.2 网络爬虫工作原理网络爬虫是如何在Internet上提取Web信息的呢？Web信息提取主要是指依赖Web页面之间的链接关系，从Web上获得页面信息，接着根据已下载页面上的链接不断向所需要的Web页面进行扩展的过程。这一过程，主要是由网络爬虫完成的。如图2-7所示,网络爬虫基本上可以划分为6个部分：URL处理器、Web信息提取器、网页去重检测器、URL提取器、标签信息获取器、数据库,它们协同合作从Web上获取信息.网络爬虫从一个用户给定或者程序事先给定的初始URL集合(也叫URL种子集合)出发,将这些URL全部放到一个有序的待提取URL队列里(检查重复页面是还将用到已下载URL队列).而Web信息提取器从这个队列按一定的规则取出URL，通过Web上的一些通信协议(如http, https,ftp等),获取URL所指向的页面的HTML,将其存入服务器缓存,然后再从这些已获取的HTML中提取信息，如URL,并将这些提取的URL继续放到待提取URL队列里,然后重复上述过程,直到Web信息提取器根据自己的搜索策略停止采集为止。图2-7 网络爬虫基本结构图 URL处理器此部件主要是处理URL队列，它根据一定的策略管理URL队列，通用爬虫只需要从种子URL集合出发，提取URL所下载的页面信息，得到新的链接，并将这些链接加入此队列，如此循环即可。而主题爬虫则需要考虑提取的URL的优先级，它会将优先级最高的URL排在队首，当 URL处理器将URL分配给Web信息提取器时将选择队首的URL。按照网络爬虫系统规模的不同，URL可以是多个采集队列(多线程爬虫，需要注意同步问题)，也可以是一个URL服务器。例如，Google搜索引擎中的网络爬虫构建中就使用了URL服务器来缓存URL，以达到更快的处理速度。从图2-7中不难看出，URL处理器主要有三个数据来源：(1) 初始的种子URL集合；(2) 从URL提取器传递过来的新发现的URL集合(它们从已提取页面中分析得来)；(3) 页面的Meta信息、主题以及摘要等信息，来自标签信息获取器，它们并不是URL，而是为其显示从URL提取器中传递过来的URL的重要级别，为在队列中进行排序提供依据。另外，为了加快页面提取速度，URL处理器通常自带了DNS解析功能1。 Web信息提取器此部件处于系统的底层，是通过各种Web协议来完成网络数据采集的1。一般来说，协议包括HTTP、Gopher、BBS以及FTP等，也有些web信息提取系统会根据实际需要获取WebChat、CIQ等特殊网络信息。主要是根据URL处理器给定的URL锁定Web上的页面，并通过以上提到的各种协议下载此页面的HTML信息。网页去重检测器Web上存在着大量的镜像页面和重复的页面内容，如不进行网页重复内容的检测过滤，将极大地浪费网络带宽和系统的运行效率。因此，重复内容检测是网络爬虫中的重要组成部分，特别是在大型的搜索引擎中。在进行重复内容检测时，一般可以采用简单的段落匹配方法或者相对复杂的相似度匹配方法。对于中文网页的去重算法，经过大量的网页分析后，得出了一种快捷可靠的大规模网页去重算法，即通过寻找到页面中出现的第一个中文句号，然后在句号前后取5个中文字符作为网页内容的唯一识别码。经过实验测试结果表明，该去重算法在中文网页的去重计算中有着良好的应用效果。 URL提取器对于采集到的页面，通过网页去重检测后，需要分析其中的链接，并对链接进行必要的转换以获取真实的URL，这些任务就是由URL提取器来完成的。首先需要判别页面类型，仅需要对类型为“text，html，shtml和htm”等的页面进行分析即可。页面的类型可在对HTTP应答头的分析中得出，有时也可以通过分析URL中的文件扩展名来判别页面类型。随后，需要分析的HTML标记包括，等。页面链接中给出的URL的格式可能是不一样的，既可能是完整的绝对路径URL，也可能是一个相对路径。为方便处理，需要先将其规格化为统一的绝对路径URL格式。同时，针对如今网页上HTML不规范的问题，本系统采取了纠错和再规范方法，具体内容将在第四章进行详述。 标签信息获取器这里所要获取的信息包括已提取页面的Meta信息、页面的标题、页面的摘要等。主要目的是在没有对页面内容进行语义信息理解的前提下，尽可能多的挖掘出HTML标签、结构等的信息，进行基于HTML页面的信息抽取，对从页面中提取出来的URL质量的好坏给出一个度量，然后再传输到URL处理器，对待提取URL队列进行排序。此内容也将在第四章详述。 数据库用来保存从Web上下载下来的有用信息。通过网页去重检测后的页面数据、提取出来的Meta信息、主题和摘要等均需存入数据库中，为了使搜索引擎查询速度更快，搜索引擎会为数据库进行分析建立索引等。由于Web页面规模的庞大，提取的相关数据在存入数据库之前，一般要进行压缩处理。当今很多大型通用搜索引擎为了使其网页覆盖率增大，采用扩大数据库容量的办法，然而，显而易见的是数据库容量的增长是远不及Web上信息规模的增长的。2.2.3 网络爬虫的主要技术问题和传统的信息媒介相比，Web主要有以下几个特点：(l) 信息容量的超大规模：以集合数量级增长；(2) Web的动态性：信息的刷新很快；(3) Web的异构性：Web中包含的文件类型各种各样，包括文本、声音、图像、图片以及活动脚本等；(4) 页面内容的重复性：不少网页的映像相同；(5) 链接特性：每个页面拥有超过8个指向别的页面的链接；(6) 多语种性：现在web上的页面语种超过了100个。这些特征为Web信息的有效提取，提出了巨大的难题。从技术角度来看，挑战主要有以下三点:(1) Web信息容量的巨大使得网络爬虫不可能提取所有的Web页面，即使能够全部提取，也没有足够大的空间来存放。如何提高页面提取的效率，即在单位时间内采集到尽可能多的高质量页面，是网络爬虫面临的难题之一。目前，有四种计算页面质量的方法：Simliarity，计算提取的页面和指导采集的问题之间的相度；BackLink，根据指向这个页面的链接数目判断；ForwardLink，根据页面指出的链接数目判断；PageRank，基于随机漫游模型的链接重要性分析方法(我们将在第三章对其进行介绍与分析)。Cho等对比了宽度优先方法、BackLink方法和PageRank方法，根据实验结果得出PageRank方法最好。这是因为PageRank方法反映的是全局的页面质量分布情况，能够较快的发现全局的高质量页面。(2) 并行页面提取的问题。页面的提取速度是网络爬虫的重要性能指标。Web中的页面数量规模非常庞大，而网络的连接速度相对比较缓慢，为了提高提取速度，必然考虑采用并行的做法，即多线程算法。这就引入新的问题：重复性：多个不同的提取器在同时页面提取的时候增加了重复提取页面的可能性；质量问题：单个系统能够根据算法提取到全局最优的页面，而采取并行的话，每个提取器只能看到局部页面，从而导致提取到的页面质量有所下降；通信带宽代价，为了并行，各个提取器之间不可避免的要有一些通信，这就带来通信的带宽问题，当各个页面提取器通过Internet进行通讯，通信带宽的代价就显得至关重要。(3) 页面更新问题3。为了保持系统中的页面是最新的，网络爬虫系统不得不对已经采集过的页面进行周期性的更新。但是，随着Web规模上的爆炸性增长，这个问题似乎变得不可逾越。最近的一项报告显示，即使是流行的Web搜索引擎，其页面刷新一次有时甚至会持续数月的时间。有人尝试使用泊松过程(poissonproeess)来描述页面变化率，并研究和对Web三种页面刷新策略：固定顺序的刷新，随机刷新和纯随机刷新策略。直觉上，更多的刷新应该分配给那些更新更快的页面。但是研究表明，用较高的频率刷新更新快的页面并不一定是明智之举，有时对各种页面采用相同的刷新周期效果反而更好。这是因为，以过高频率刷新更新快的页面，将使得其它页面的刷新机会减少，反而造成总体刷新质量的下降。2.3 搜索引擎的评价标准在搜索引擎的发展初期，人们对它的要求较低，只要它能把互连网上相关的网站搜出来，搜到的网站尽量多一点，无关的网站能少一点就能满足。那时，人们评测搜索引擎的方法是用几个关键词，测试对比它们的搜索速度、搜索数量和无关网站的多少。简单说就是全、快、准。此后，独特的搜索引擎技术此起彼伏，层出不穷，但是，人们的评测方法却没多大变化，现在常见的评测还是简单的用几个关键词比较搜索速度、搜索结果数量和各自介绍的搜索准确性。搜索引擎的评价标准与目前搜索引擎的发展状况并非完全吻合。下面，我们就目前常用的评价指标进行分别介绍。(1) 搜索引擎的查全率。搜索引擎首要的关注点就是查询范围，检索出的相关文档数和文档集中所有的相关文档数的比率。此评判标准有很大不足。网页索引容量有大小， robot和spider程序不同，索引范围和索引标准也不尽相同，在大型的搜索引擎上搜不到的内容可能在小型的搜索引擎上搜到。 此外，搜索引擎是可以针对特定的关键词进行结果优化的，优化了的搜索引擎在对特点的关键词查询时返回结果必然是更加完美，所以，只考察其查全率是不能说明问题的。(2) 搜索的速度。即使搜索引擎搜集的信息再多，它的平均下载速度比较低的话，我们还是不能说它的性能高。搜索引擎搜索的速度还和访问量，网页索引数量有关。索引数量越大，所要比较的数据就越多，那么搜索的速度也就越慢了。当然，此衡量标准与爬虫关系并不大。(3) 查准率。查准率是检索出的相关文挡数与检索出的文档总数的比率。这一点对用户来说相当重要，也是评价搜索引擎最主要的一点依据。一个查准率低下的搜索引擎是不会用任何市场的。当然，查准率还受用户对关键词的表达所影响。(4) 死链接和网页的更新速度。通常的搜索引擎返回用户的结果总有些页面是不可达的，少到百分之一二，多到百分之八九。但是象Google使用了网页快照功能，几乎不存在死链接问题，就算搜索结果中的那个网站已关闭，你还是可以看到Google自己储存的网页。(5) 重复信息返回的过滤。返回结果应该尽可能不出现重复、类似的结果。2.4 面向主题的信息提取面向主题的信息提取与通用搜索引擎的信息提取有很大区别，前者在提取的时候就已经有了主题信息，它将只提取与主题相关的信息，无关的就将舍弃。而后者在提取信息时时没有主题可言的，它不会丢弃任何信息。2.4.1 面向主题的信息提取分类主题搜索引擎主要有两种分类依据：一种是根据提取主题的范围和规模，另一种是根据提取是能否由用户指定主题。 广泛主题和具体主题的Web信息提取根据提取主题的范围和规模，面向主题的Web信息提取可划分为广泛主题的Web信息提取和具体主题的Web信息提取3。(1) 广泛主题是指那些涵盖面较宽，并且和其它主题相比具有较强独立性的一类主题。广泛主题的Web信息提取也称作领域Web信息提取。用户在提取这类主题时，往往没有太具体的明确要求，这类信息提取所需要提取的Web页面数量较多，为了达到较高的召回率，在进行URL主题相关性剪枝过滤时所设的阀值较低，限制条件较宽。同时它提取的页面内容种类相对较杂，提取页面与主题的平均相关度也相对较低。(2) 与之相对应，具体主题的Web信息提取涵盖面较窄，意义也比较明确，提取页面的数量也较少。这类提取一般直接服务于用户。它在进行URL主题相关性剪枝过滤时候所设定的闽值较高，限制条件比较严格。这类信息提取对用户来说具有更强的针对性，提供的是主题相关度很高的页面。 固定主题和可变主题的Web信息提取