网络爬虫关键技术分析与实现

　　搜索引擎发展的历史过程与发展现状

　　1搜索引擎的发展的历史

　　1990年以前，没有任何人能搜索互联网。所有搜索引擎的祖先，是1990年由Montreal的McGill University学生Alan Emtage,Peter Deutsch.BillWheelan发明的Archie(Archie FAQ)。一个可以用文件名查找文件的系统，于是便有了Archie.Archie是第一个自动索引互联网上匿名FTP网站文件的程序，但它还不是真正的搜索引擎。1995年12月，Altavista永远改变了搜索引擎的定义。AltaVista是第一个支持自然语言搜索的搜索引擎，AltaVista是第一个实现高级搜索语法的搜索引擎(如AND,OR,NOT等)。用户可以用Altavista搜索Newsgroups新闻组)的内容并从互联网上获得文章，还可以搜索图片名称中的文字、搜索Titles、搜索Javaapplets、搜索ActiveX objects.许多关于网络爬虫的论文都在第一届和第二届World Wide Web conferences被发表。1998年，Google在Pagerank、动态摘要、网页快照、DailyRefresh、多文档格式支持、地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，象Altavista一样，再一次永远改变了搜索引擎的定义。至2005年4月21为止，Google中所收集的Web页面数量已经达到8,058,044,651张。现阶段，出现了Ask Jeeves,Baidu.com,Goto.com,MySimon,Dito等内容类别不同的搜索引擎。

　　2搜索引擎的发展现状与趋势

　　目前，大多数的搜索引擎都是基于关键词的搜索引擎。基于关键字匹配的搜索技术有较大的局限性：首先，它不能区分同形异义。其次，不能联想到关键字的同义词[9]。

　　Web商业化至今，搜索引擎始终保持着网络上被使用最多的服务项目的地位，然而，随着网上内容的爆炸式增长和内容形式花样的不断翻新，搜索引擎越来越不能满足挑剔的网民们的各种信息需求。这表现在以下几个方面：

　　(1)搜索引擎对自然语言提问没有理解能力。

　　(2)搜索引擎收集的网页数量和其数据库的更新速度存在着不可调和的矛盾。

　　(3)搜索引擎无法与电子商务紧密结合。

　　(4)搜索引擎对多媒体内容的处理尚不成熟。

　　搜索引擎的发展面临着两大难题：一是如何跟上Internet的发展速度，二是如何为用户提供更精确的查询结果。所以，传统的引擎不能适应信息技术的高速发展，新一代智能搜索引擎作为一种高效搜索引擎技术的在当今的网络信息时代日益引起业界人士的关注。搜索引擎己成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。

　　1.自然语言理解技术

　　自然语言理解是计算机科学中的一个引人入胜的、富有挑战性的课题。从计算机科学特别是从人工智能的观点看，自然语言理解的任务是建立一种计算机模型，这种计算机模型能够给出像人那样理解、分析并回答自然语言。以自然语言理解技术为基础的新一代搜索引擎，我们称之为智能搜索引擎。由于它将信息检索从目前基于关键词层面提高到基于知识(或概念)层面，对知识有一定的理解与处理能力，能够实现分词技术、同义词技术、概念搜索、短语识别以及机器翻译技术等。因而这种搜索引擎具有信息服务的智能化、人性化特征，允许网民采用自然语言进行信息的检索，为它们提供更方便、更确切的搜索服务。

　　2.十分注意提高信息查询结果的精度，提高检索的有效性

　　用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在结果中筛选。解决查询结果过多的现象目前出现了几种方法：

　　(1)是通过各种方法获得用户没有在查询语句中表达出来的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型;使用相关度反馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关(及其相关的程度)，哪些不相关，通过多次交互逐步求精。-3-哈尔滨工业大学工学硕士学位论文

　　(2)是用正文分类(Text Categorization)技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。

　　(3)是进行站点类聚或内容类聚，减少信息的总量。

　　3.基于智能代理的信息过滤和个性化服务

　　信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模型(如Web知识、信息处理、与用户兴趣相关的信息资源、领域组织结构)、用户模型(如用户背景、兴趣、行为、风格)知识进行信息搜集、索引、滤(包括兴趣过滤和不良信息过滤)，并自动地将用户感兴趣的、对用户有用的信息提交给用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而提供个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。

　　4.采用分布式体系结构提高系统规模和性能

　　搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有千秋。但当系统规模到达一定程度(如网页数达到亿级)时，必然要采用某种分布式方法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口之外，都可以进行分布：搜索器可以在多台机器上相互合作、相互分工进行信息发现，以提高信息发现和更新速度:索引器可以将索引分布在不同的机器上，以减小索引对机器的要求;检索器可以在不同的机器上进行文档的并行检索，以提高检索的速度和性能。

　　这项内容的一个明显的技术是P2Po P2P是peer-to-peer的缩写，意为对等网络。其在加强网络上人的交流、文件交换、分布计算等方面大有前途。长久以来，人们习惯的互联网是以服务器为中心，人们向服务器发送请求，然后浏览服务器回应的信息。而P2P所包含的技术就是使联网电脑能够进行数据交换，但数据是存储在每台电脑里，而不是存储在既昂贵又容易受到攻击的服务器里。网络成员可以在网络数据库里自由搜索、更新、回答和传送数据。所有人都共享了它们认为最有价值的东西，这将使互联网上信息的价值得到极大的提升。

　　5.重视交叉语言检索的研究和开发

　　交叉语言信息检索是指用户用母语提交查询，搜索引擎在多种语言的数据库中进行信息检索，返回能够回答用户问题的所有语言的文档[17]。如果再加上机器翻译，返回结果可以用母语显示。该技术目前还处于初步研究阶段，主要的困难在于语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、互联网跨越国界的今天，无疑具有很重要的意义。

　　6.多媒体搜索引擎

　　随着宽带技术的发展，未来的互联网是多媒体数据的时代。开发出可查寻图像、声音、图片和电影的搜索引擎是一个新的方向。目前瑞典一家公司己经研制推出被称作“第五代搜索引擎”的动态的和有声的多媒体搜索引擎。

　　3搜索引擎分类与工作原理

　　3.1搜索引擎的分类

　　按照信息搜集方法和服务提供方式的不同，目前Internet上的搜索引擎大致可以分成三类：

　　1.一般搜索引擎：利用网络爬虫对Internet资源进行索引，一般无须人工干预。所谓的网络爬虫是一个程序，通过自动读取一篇文档遍历Web的超链接结构，从而递归获得被引用的所有文档。不同的搜索引擎搜索的内容不尽相同：有的着重站点搜索，而有的搜索可能包括Gropher、新闻组、E-MAIL等。一般搜索引擎的性能主要取决于：索引数据库的容量、存放内容、以及更新速度，搜索速度，用户界面的友好程度以及是否易用等。这类的引擎的代表包括国外的AltaVista(htp://www.altavista.digital.com)InfoSeek(htp://www.infoseek.com)等。

　　2.元搜索引擎：接受一个搜索请求，然后将该请求转交给其他若干个搜索引擎同时处理。最后对多个引擎的搜索结果进行整和处理后返回给查询者。整和处理包括诸如消除重复，对来自多个引擎的结果进行排序等。

　　3.专用引擎：譬如人物搜索、旅行路线搜索、产品搜索等。这些搜索都依赖于具体的数据库。

　　引擎的其他分类方法还有：按照自动化程度分为人工与自动引擎;按照是否有智能分智能与非智能引擎;按照搜索内容分文本搜索引擎、语音搜索引擎、图形搜索引擎、视频搜索引擎等。

　　3.2搜索引擎的基本工作原理

　　搜索引擎搜集互联网上成千上万的网页并对网页中的内容按照关键词进行索引，建立索引数据库供用户进行全文搜索。当用户需要查找某一个关键词时，所有在页面内容中包含了该关键词的页面都会被搜索出来。 下图了描述搜索引擎的工作原理。依靠网络爬虫获取互联网上的大量的网页信息，交给索引程序建立索引，最后提交给用户查询程序供用户使用。传统搜索引擎的工作从功能结构上划分主要分三个部分：1、从互联网上获取信息的爬虫模块;2、建立全文索引库的索引模块;3、用户查询模块。其中，本文所讨论的范围仅限于爬虫模块。下面简要介绍一下各个模块的作用。

　　查看原图(大图)

　　1、网络爬虫模块

　　网络爬虫实际上是一个基于 web的程序。 它从一个初始的网页集出发， 遍历

　　自动的采集网络信息。当爬虫打开某个 HTML 页面后，它会分析 HTML 标记结构来获取信息，并获取指向其它页面的超级链接，然后通过既定的搜索策略选择下一个要访问的站点。 从理论上讲， 如果为 Spider 指定个适当的初始文档集和个适当的网络搜索策略，它就可以遍历整个网络。它的性能在很大程度上影响了搜索引擎站点的规模。

　　2、索引模块

　　网络爬虫爬取的网页上的信息以固定的格式获取到本地后，索引建立程序对信息进行分析，针对页面中出现的关键词建立一种利于快速查找的数据结构，即索引，以供搜索引擎使用。搜索引擎在选择索引数据结构时通常考虑两个因素：紧凑的数据结构和高效的检索能力。由于搜索引擎在建立索引的时候是面对海量的信息，因此在考虑记录大小时要具体到字节中的位，这样才能达到一种比较合理科学性的空间膨胀比。合理的数据结构将使对关键词的检索更加迅速。通常有三种索引的建立基本技术：倒排文件、后缀数组和签名文件。倒排文件在当前大多数信息获取系统中得到应用，它对于关键词的搜索非常有效。后缀数组在短语查询中具有较快的速度，但是该结构在维护上相对比较麻烦。签名文档如今已被倒排索引技术替代。　　 处理网页的过程主要包括这几部分:文档特征向量提取、网页筛选、相关度分析、文档分类和入库操作。

　　3、用户查询模块

　　用户查询模块是搜索引擎和用户之间的接口。其首先获取用户查询条件并加以分析，然后访问索引数据库进行匹配后获得检索结果，然后根据设定的相关度进行降序排序处理后返回给用户。

　　3.3网络爬虫在搜索引擎中的地位

　　从上面的搜索引擎基本原理上可以看出网络爬虫是一种能够跟踪网络上超链接结构，并不断进行网络资源发现与采集的程序。作为搜索引擎的资源采集部分， 网络爬虫的性能将直接影响到整个搜索引擎索引网页的数量、质量和更新周期。因此对于网络爬虫的研究具有深远的意义。

　　3.4网络爬虫的种类

　　为了解决Web采集的关键问题，研究者们经过不断地研究与实践，将爬行器由最早期单纯的基于整个Web的爬行器发展到可满足不同需要的多种采集技术的爬行器。归纳起来，大致可以分为以下几种类型：

　　第一种是基于整个Web的爬行器。主要是指目标为从一些种子URL扩充到整个Web的爬行器，这种爬行器通常是作为门户站点搜索引擎和大型的Web服务提供商的数据采集部分。这类信息采集由于目标是采集整个Web，因此对内存和硬盘等硬件的要求比较高，对采集页面的顺序要求相对较低。

　　第二种是增量式的爬行器。传统的爬行器根据自己的需要采集足量的信息后停止采集，当过一段时间这些数据过时后，它会重新采集一遍来代替先前的信息，称为周期性Web采集器。而增量式的爬行器对待就的页面采用增量式更新，即采集器在需要的时候采集新产生的或己经发生了变化的页面，而对没有变化的页面不进行采集。和周期性信息采集相比，增量式信息采集能极大地减小数据采集量，从而极大地减少了采集的时间与空间开销。但是与此同时，增量式信息采集也增加了算法的复杂性和技术难度。

　　第三种是基于主题的爬行器是指选择性地搜寻那些与预先定义好的主题相关的页面的爬行器。和基于整个Web的爬行器相比，它并不采集那些与主题无关的页面，所以大大地节省了硬件和网络资源，保存的页面也由于数量少而更新快。加之它可以很好地满足一些特定人群对特定领域信息的需求，成为时下研究的热门重点。但它的问题也是显而易见的，例如如何定义有实际意义的主题，如何在采集时判定页面与主题的相关性以及如何提高系统的搜索精度和完全度等。

　　第四种是基于用户个性化的爬行器。不同的用户对一个搜索引擎提交同一个检索词，他们期待的结果是不尽相同的。而通用的搜索引擎却只能返回相同的检索结果，这显然不完全符合用户的需要。而基于用户个性化的爬行器是一种轻量级的采集系统，它的目标就是通过用户兴趣制导或与用户交互等手段来采集信息，给用户提供个性化服务。

　　第五种是移动的爬行器。这种爬行器并不像其他爬行器一样在本地客户机向Web站点服务器发送页面请求，而是将自己上载到它所要采集的服务器中，在当地进行采集，并将采集结果压缩后，再回传到本地。这样做大量地节省了Web资源，大量的剪裁工作将在被采集对象的服务器上完成。

　　第六种是基于元搜索的爬行器。它对用户的提交的查询请求通过多个领域或门户搜索引擎搜索，并将结果整合后返回给用户。一般元搜索引擎并不保存Web页面的索引文件，但是有一些元搜索引擎会保存为它服务的每个搜索引擎的信息特征，以后根据用户请求做出选择。作为搜索引擎首要部件的爬行器在元搜索引擎中功能有所退化，但依然是Web采集的一个研究方向，被称作基于元搜索的信息采集。

　　3.5网络爬虫的两种工作方式

　　3.5.1集中式网络爬虫

　　集中式爬虫的工作原理是：给定的一组初始 URL 种子集合，通过爬虫主体程序多个

　　线程分别获取到种子 URL 后，将 URL 对应的 html 页面获取到本地进行分析，页面内容提取模块将页面中有用的可供搜索引擎建索引的信息获取到本地保存起来，种子提取模块将 html 页面中新的指向其他页面的链接提取出来，经过一系列的处理保存起来供以后继续爬行。

　　3.5.2分布式网络爬虫

　　随着 WWW 信息的爆炸性增长，网络爬虫信息采集的速度越来越不能满足实际应

　　用的需要。即使大型的信息采集系统对 Web的覆盖率也只有 30-40%，刷新一遍已经采集的页面常常需要数周到一个月的时间。解决这一问题的直接办法是升级信息采集器的硬件，采用处理能力更强的计算机系统，然而这种方法的扩展性有限，性价比也不高。因而人们找了一个更好的选择，用分布式方式来进行网页信息采集。分布式网络爬虫可以看做由多个集中式网络爬虫组合而成。分布式系统中的每个节点都可以看作一个集中式网络爬虫。多个网络爬虫共同运行，肯定会涉及到各个节点间相互通信。这时候就会涉及到一些系统通信问题。

　　3.6分布式网络爬虫研究现状

　　要在搜索引擎中尽可能地找到用户所需信息，就要求搜索引擎索引尽可能多的网页，索引网页数量是评价一个搜索引擎好坏的关键因素之一。采用分布式技术在尽可能短的时间内搜集尽可能多的网页，是研制高效搜索引擎的关键技术到目前为止，分布式网络爬虫系统已经有了不少应用，例如现在着名的 Google 和

　　Alta Vista搜索引擎所采用的网络爬虫系统。但由于商业机密等因素的影响，较详细的介绍分布式网络爬虫系统的文章并不多，并且基于 Web 信息采集的分布式理论也还不完善，仍然有待研究。目前，较着名的分布式爬虫有 Google Crawler、Mercator、Internet Archive Crawler、UbiCrawler 等，国内的有北大天网的 Web Gather 爬虫系统。

　　Google 的分布式爬虫系统由四台机器组成，其中一台机器是中央主机，其它三台机器只负责爬行网页，并且只与中央主机通信。中央主机从一个文件里读取 URL，并把它们分发给其它机器的 Crawler 进程。爬虫采用异步 I/O 同时从 300 个网站上获取数据。所有的 Crawler 将下载来的页面压缩并存放在磁盘上。然后 Indexer 进程从这些 HTML页面中将 URL 提取出来，并存放在另一个磁盘文件中。URL Resolver 进程读取这个存放链接的文件， 将其中的相对链接转化为绝对链接， 然后存入一个文件供中央主机读取。不足之处在于如果中央主机失效，则整个系统都会停止工作，而且中央主机的 URL 分

　　发模块常常成为整个系统的瓶颈。

　　Mercator是 Alta Vista 搜索引擎的网络爬虫，它完全由 JAVA写成。Mercator的可扩展性非常好，可以通过增减或替换模块来实现不同的功能。Mercator采用的数据结构可以使无论爬行的规模有多大，只占用有限的内存，数据结构的大部分都在硬盘中存放。并且 Mercator 只存放 URL 的 checksum 值，这样可以节省大量的内存和磁盘空间。Mercator 为最近访问 URL 建立了缓存，该缓存的命中率达到 85%。在提高系统性能方面，Mercator 系统做了非常多的工作，比如重写 JAVA 核心库，建立缓存，采用高速硬盘系统。Mercator 证明了使用JAVA语言也可以达到较高的性能。

　　Internet Archive 爬虫系统采用多个机器共同搜集网页。每个 Crawler 进程负责搜集64 个 Web站点的网页。Crawler 从起始 URL集合中读取，采用异步 I/O并行爬取网页。网页下载后，提取出超链接。如果超链接属于本Crawler负责搜集的 Web站点，则加入未访问 URL 集合，否则存储到交叉 URL 文件中。批处理模块定期分配这些交叉 URL文件到相应的搜集模块，在此过程中要过滤掉重复的 URL。