基于Nutch的搜索引擎实现及中文扩展论文.doc

资源描述

毕业设计(论文) 第36页基于Nutch的搜索引擎实现及中文扩展摘要搜索引擎是为满足人们网络信息搜索应运而生的网络工具,它是互联网信息查询的导航针,是沟通用户与网络信息的桥梁。然而,随着网上内容的爆炸式增长和内容形式花样的不断翻新,搜索引擎越来越不能满足挑剔的网民们的各种搜索需求,尽管Web搜索是漫游Internet的基本要求, 并且现有web搜索引擎的数目却在下降。这很有可能进一步演变成为一个公司垄断了几乎所有的web搜索为其谋取商业利益。于是强有力的搜索工具成为这些网民们的渴盼。作为Apache开源子项目，Nutch 提供完整的搜索引擎框架，在对全文进行索引的时候，索引部分采用了开源工具包Lucene进行全文索引。通过对Nutch的二次开发，我们可以利用它强大的网络资源采集功能对网络资源进行采集，并加工进入本地库，最后让用户直接面对有效的信息。本文重点讨论搜索引擎原理，基于Nutch的搜索引擎的实现架构，同时网页抓取过程做了深入的研究和分析；最后，对在早期Nutch的版本的基础上如何更好的支持中文，实现中文分词搜索给出问题的解决方案，并对基于Nutch的搜索引擎的应用进行了讨论。关键词：搜索引擎，抓取器，Nutch，中文分词 Nutch –Based Search Engine Implementation and Chinese extension Abstract Search engine is the internet tool meeting demands of people while surfing on the internet and searching the information. It is a Internet Information navigation and bridge between internet user and information. However, with the sharply increase of the net content and the surprisingly change of the Synchronized forms of content, search engine can not satisfy increasingly critical user’s all kinds of search demands, although Web search is the foundation of the internet Roaming ,the existing number of search engine is down.This phenomenon can easily became one company almost monopolized all web search for its commercial gain. Therefore ,a strong and useful and effective search tool rise to the hope focus of internet user.Nutch is such search engine, when Nutch aims to text indexing, it uses the revenue Lucene toolkit for full-text indexing. Through the second Nutch development we can make use of its powerful internet resource Collection Function to collect the resource we need, then put the processed information into local database, finally, user can directly face effective information. In this paper, we emphasize on the implementation architecture of the Nutch, Search engine principle，webpage crawling process. Excepting the in-depth research and analysis about above, we also give the solution of how to support Chinese and Chinese segmentation on the basis of earlier versions. Finally, a discussion about the application based on Nutch is given. Key words：Search engine, crawler, Nutch, Chinese segmentation 目录 1绪论 1 1.1 课题背景 1 1.2 搜索引擎的现状 2 1.2.1搜索引擎的发展历史 2 1.2.2搜索引擎的分类 3 1.2.3当前主流搜索引擎简介 4 1.3 论文组织结构 5 2搜索引擎基本组成及数据结构 6 2.1搜索引擎基本组成及工作流程 6 2.1.1基本组成 6 2.1.2工作流程 6 2.2 存储结构 8 2.2.1页面存储库 8 2.2.2词典库 8 2.2.3 Hits列表 9 2.3 索引结构 10 2.3.1文档索引库 10 2.3.2前向索引表 10 2.3.3后向索引表 11 3基于Nutch的搜索引擎实现的关键技术 11 3.1网页抓取技术研究与设计 11 3.1.1抓取技术的协议分析 11 3.1.2通信协议 12 3.1.3 HTML解析 13 3.2 网页抓取方法 13 4 基于Nutch实现架构 16 4.1 基于Nutch的搜索引擎开发环境和体系结构 16 4.1.1 基于Nutch的搜索引擎的开发环境 16 4.1.2基于 Nutch的搜索引擎的体系结构 16 4.2 基于Nutch的搜索引擎的抓取过程运行 20 4.3 搜索结果展示 22 5 Nutch中文扩展设计与实现 23 5.1中文分词和搜索引擎 23 5.2 中文分词算法 23 5.2.1 基于字符串匹配的分词算法 24 5.2.2基于理解的分词方法 25 5.2.3基于统计的分词方法 25 5.3 中文分词难点 26 5.4 Nutch分析 27 5.5 Nutch中文搜索 28 5.5.1 Nutch中文分词 28 5.5.2 JavaCC分析 29 5.5.3利用JavaCC构造中文分析模块 31 5.6小结 33 结论 33 总结 33 展望 33 致谢 34 参考文献 34 1绪论 1.1 课题背景互联网发展的今天，一方面离不开其开放、共享的特性带给人们的全新体验，另一方面也离不开数以亿计的为其提供各类丰富内容的网络节点[2],联网被普及前，人们查阅资料第一想到的便是拥有大量书籍资料的图书馆，到了今天你怎么想？或许今天的很多人都会选择一种更方便、快捷、全面、准确的方式——互联网。你可以坐在家里轻点几下鼠标就查到想要的各类信息，这在互联网没有被普及之前，还都仅是一个梦而已，但如今这一切已成为了可能。而帮助你通过整个互联网快速查找到目标信息的就是越来越被重视的搜索引擎。络上已经有很多关于搜索引擎方面的报道。目前，搜索引擎成为最受人们关注的焦点之一，也成为亿万富翁的制造摇篮。越来越多的公司都希望在搜索引擎这座金矿中挖到金子，其中许多人会选择拥有自己的搜索引擎。国内著名搜索引擎公司百度总裁李彦宏说：搜索引擎不是人人都能做的领域，进入的门槛比较高。现有web搜索引擎的数目在下降. 这很有可能进一步演变成为一个公司垄断了几乎所有的web搜索为其谋取商业利益。 Nutch 正是在这种环境中诞生，它是一个刚刚诞生开放源代码(open-source)的web搜索引擎完整框架，作为apache旗下的一个开源项目已经有两年的历史。基于nutch开发者可以建立自己内部网的搜索引擎，也可以针对整个网络建立搜索引擎。相对于那些商用的搜索引擎, Nutch作为开放源代码搜索引擎将会更加透明,更值得大家信赖.。现在所有主要的搜索引擎都采用私有的排序算法, 而不会解释为什么一个网页会排在一个特定的位置，除此之外, 有的搜索引擎依照网站所付的费用, 而不是根据它们本身的价值进行排序。与它们不同, Nucth没有什么需要隐瞒, 也没有动机去扭曲搜索的结果。 Nutch将尽自己最大的努力为用户提供最好的搜索结果。Nutch 致力于让每个人能很容易, 同时花费很少就可以配置世界一流的Web搜索引擎.与现有的搜索引擎相比，nutch在索引为了完成这一宏伟的目标, 必须能够做到:每个月取几十亿网页，为这些网页维护一个索引，对索引文件进行每秒上千次的搜索，提供高质量的搜索结果，以最小的成本运作。 1.2 搜索引擎的现状 1.2.1搜索引擎的发展历史随着信息技术的不断发展，特别是互联网应用的迅速普及，电子信息爆炸式地丰富起来，目前，仅Google收录的网页就超过了80亿，并且每天全球互联网页面数目以千万级别的数量增加，要在浩如烟海的网络信息海洋中自如冲浪，搜索引擎已经成为必不可少的利器。自1994年至今，伴随着英特网的日益发展壮大以及Web信息量地迅速膨胀，Web搜索引擎技术为了不断满足人们对Web信息检索的需求，已经经历了三代发展阶段[8]：第一代搜索引擎出现于1994年，以集中式见所为主要特征，这类搜索引擎一般都索引少于1百万个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10秒甚至更长的时间，在实现技术上也基本沿用较为成熟地IR（Information Retrieval），网络，数据库等技术，相当利用于利用一些已有的技术实现的一个WWW杀害上的应用。第二代搜索引擎系统大约出现在1996年，大多采用分布式检索方案，即多个微型计算机协同工作来提高数据规模，响应速度和用户数量。他们一般都保持一个大约5千万网页的索引数据库，每天能够响应1千万次用户检索请求。第三代搜索引擎系统出现在1998年到2000年期间，这一时期式搜索引擎空前繁荣地时期。第三代搜索引擎的发展有如下几个特点：（1）索引数据库的规模继续增大，一般的商业搜索因情窦保持在几千万甚至上亿个网页。（2）除了一般意义上地搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。（3）由于搜索返回数据量过大，检索结果相关度评价成为研究地焦点。相关地研究又可以分两类：一类是对超文本链的分析，在这方面始于Stanford大学的Google系统作出了很大的贡献；另一类是用户信息的反馈，DirectHit系统采用的就是这种方法。（4）开始使用自动分类技术。Norghern Light和Inktomi的DirectoryEngine都在一定程度上使用了该技术。进入了21世纪后，随着信息多元化的增长，千篇一律的给又用户同一个入口显然已经不能满足特定用户更深入的查询需求同时，这样的通用搜索引擎在目前的硬条件下，要及时更新以得到互联网上较全面信息是不太可能的。针对这种情况，分类细致，精确，数据全面深入，更新及时的面向主题的搜索引擎出现了。由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比上面提到的前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为的时代搜索引擎。 1.2.2搜索引擎的分类按照信息搜集方法和服务提供方式的不同搜索引擎系统可以分为三大类: 目录式搜索引擎：以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏览服务和直接检索服务。该类搜索引擎因为加入了人的智能，所以信息准确，导航质量高，缺点是需要人工介入，维护量大，信息量少，信息更新不及时。目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是安目录分类的网站链接列表而已。用户完全可以不用关键词查询，仅靠分类目录也可以找到需要的信息。国外比较著名的目录索引搜索引擎有yahoo(),Open Directory Project（DMOZ）(), LookSmart ()等。国内的搜狐（）,新浪（），网易（）,网址之家（）等也都具有这一类功能。 (2)机器人搜索引擎[9]：由一个称为网络蜘蛛（Web Spider）的机器人程序以某种策略自动在互联网中搜集和发现信息，由索引器（Indexer）为搜集到的信息建立索引，由检索器（Searcher）根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式时面向网页的全文检索服务。该类搜索引擎的优点是信息量大，更新及时，毋需人工干预，缺电视返回信息过多，有很多无关的信息，用户必须进行筛选。机器人搜索引擎也称全文搜索引擎，它是名副其实的搜索引擎，国外具有代表性的有Google (), yahoo () , AllTheWeb ()等。国内著名的有百度（）,中搜（），搜狗()等。他们都是通过从互联网上提取的各个网站的信息（以网页文字为主）而建立的索引数据库，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，也是目前常规意义上的搜索引擎。（3）元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除，重新排序等处理后，作为自己的结果返回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大，更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛选。元搜索引擎再接受用户查询请求时，同时再其他多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎有Dogpile()，综合了Google,Yahoo Search,MsnSearch的搜索结果，Vivisimo（）等。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，入Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。 1.2.3当前主流搜索引擎简介现在在网上的搜索引擎已经有很多，比较著名的有Google，AltaVista，Yahoo，InfoSeek，Metacrawler，SavvySearch等等。国内也建立了很多搜索引擎，比如百度，中搜，搜狗，一搜等等。其中在信息搜索的取全率和取准率上做的最好的还数Google。 AltaVista：自1995年，AltaVista开始全文搜索服务以来，已被公认为搜索技术的先驱，领航者，不断改进，帮助用户搜索网上的相关信息。公司基于58项技术专利而建，在避免双重搜索，地域垃圾等技术上不断革新，发展了类聚方法，改进了搜索结果的相关性。AltaV站点可以提供综合搜索结果，使用户立刻找到相关网页，多媒体文件以及最新新闻。同时可以把得到的搜索结果翻译成其他语言。 Google是当前搜索准确度和用户查询相关度最好的搜索引擎。它的主要优势在于：1，大容量的页面存储空间。据称Google目前收录的Web网页数量已经达到80亿。2，及时响应速度。据统计，Google的普通搜索花费的平均时间在0.3秒以内，这得益于其数百台的高性能硬件服务器系统和分布式并行查询软件系统。3，查询返回的结果不仅仅集中于大型热门网站，而更多的是针对待定的Web页面。 Baidu百度是全球最大的中文搜索引擎，在中文分词方面相比其他搜索引擎具有较大的优势。但在收集的网页量，搜索速度，页面相关度排序方面比Google等搜索引擎还有一定的差距。 1.3 论文组织结构本文先对搜索引擎的原理，组成，数据结构，工作流程等方面做了深入而细致的研究与分析。在理论研究的基础上，本文用基于Nutch的java技术对搜索引擎的三个核心部分即网络蜘蛛，网页索引，搜索进行了实现。网络蜘蛛部分采用了非递归爬取方式和java的多线程机制，利用一个基于内存的作业队列管理器负责网页抓去过程总URL链接的加入，分配，处理等作业，同时使用线程池管理多个抓取线程，并发抓取网页。索引和搜索部分基于Nutch的搜索引擎则借助Luence全文搜索引擎中的java类进行实现。Luence是Apache软件基金会的一个开源项目，完全由java实现，适用于需要全文搜索能力的应用程序，并具有良好的跨平台能力。最后对采用中文分词技术和javaCC技术实现Nutch的中文扩展进行了细致的讨论。 2搜索引擎基本组成及数据结构 2.1搜索引擎基本组成及工作流程 2.1.1基本组成搜索引擎主要由网络蜘蛛（Web Spider/Crawler），索引器（Indexer）和检索器（Searcher）三部分组成[1] （1）网络蜘蛛（Crawler）的主要功能是从指定的IP地址或网页出发遍历互联网搜集网页，并沿着任何网页中的所有URL爬到其他网页，重复这个过程，并把爬过的所有网页搜集到页面存储库中。（2）索引器（Indexer）对收集回来的网页进行分析，提取相关网页信息（包括对网页所在url，编码类型，页面内容包含的关键词，关键词位置，生成时间，大小，与其它网页的链接关系等），根据一定的相关度算法进行大量复杂计算，得到每一个网页（针对页面内容）以及超链接中每一个关键词的相关度(或重要性)，然后利用这些相关信息建立网页索引输据库。（3）当用户输入关键词搜索后，搜索请求经过分解，由搜索器（Searcher）从网页索引数据库中找到符合该关键词的所有相关网页。所有相关网页针对关键词和相关信息在索引库中都有记录，只要综合相关信息和网页级别形成相关度数值，然后进行排序，相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。搜索引擎的工作流程可以简化为以下四个步骤：（1）网上抓去网页（2）建立索引数据库（3）在索引数据库中搜索（4）对搜索结果进行整理和排序 2.1.2工作流程图2.1为一个搜索引擎典型的基本组成以及工作流程图图2.1搜索引擎典型的基本组成以及工作流程图网络蜘蛛从互联网上抓去网页，并把网页送入“页面存储库”，从网页中“抓取URL”，把URL送入“URL数据库”，“网络蜘蛛控制”得到网页URL，控制“网络蜘蛛”抓取其它页面，反复循环直到把所有的网页抓完。系统从“页面存储库”中得到文本信息，送入“索引器”模块建立索引，形成“索引库”，同时进行“链接信息提取”，把链接信息(包括锚文本，链接本身等信息)送入“链接输据库”，为“网页评级”提供依据。 “用户”通过提交查询请求给“索引器”，检索器在“索引库”中进行相关网页的查找，同时“网页评级”把查询请求和链接信息结合起来对搜索结果进行相关度评价，通过“检索器”按照相关度进行排序，并提取关键词的内容摘要，组织最后的页面反会给“用户” 2.2 存储结构 2.2.1页面存储库页面存储库存储网络蜘蛛爬取到的每个Web页面完整的HTML代码和相应的URL信息，并采取了如图2-2-1所示的压缩存储方式。页面存储库不需要其他额外的数据结构来管理和维护，简化了数据一致性维护的复杂度和工作量，并且，从页面存储库能够重建其他相关的数据结构，图2.1为页面存储库结构。 Sync Length Compressed Packet Sync Length Compressed Packet 图2.1 页面存储库结构 Sync：同步标志。用于标识压缩包之间的分隔； Length：压缩包的长度。用于表明压缩包的长度和定位； Compressed Packet：压缩包数据；页面存储库采取紧锁存储方式，利用同步标志和压缩包长度来进行定位和查找。图2.2压缩存储结构包主要记录了文档标识号（DocID）和URL页面信息等。 DocID Encode URLLen PageLen URL Page 图2.2 压缩包（Compressed Packet）存储结构 DocID:文档标识号用于标识页面存储库中唯一的Web页面。 Encode：表示存放文当时采用的编码方式； URLLen：标识该文档来源URL的长度； PageLen：标识文档的长度； URL:表示文档来源的URL； Page：文档内容； 2.2.2词典库词典库（Lexicon）最主要的作用是为检索器（Seacher）提供单词查找帮助，即将待监察队文本单词转化为单词标识号(WordID)，以便在后向索引中查找与之对应的文档。为了保证及时响应速度，词典库应该能够整个放入内存中。因此词典库采取紧缩存储方式显得有其重要。由于每个单词长度变化很大，单词总数达到数百万个，因此词典库，如图2.3所示，采取不定长记录紧缩存储的方式，附加一个哈息表（HashTable）辅助查询，如图2.4所示，。 Word1 Null Word2 Null … 图2.3 词典库（Lexicon）存储结构所有单词（Word）的字符紧接着一次存储，Null为word间分隔标识。 Hash值 Hash值冲突链表头指针 001 Pointer to collision link 002 Pointer to collision link … … 图2.4 哈息辅助查询表图2.4中的Hash值是根据各个单词的所有字符运用一定的算法得出的。哈息表以哈希值排序。对于相同哈希值的单词，则顺次加入其后的冲突链表中。冲突链表项结构如下图2.5： WordID Pointer to lexicon Pointer to next item 图2.5 冲突链表项结构 WordID为单词标识符，用于标识单词字符文本。检索器（Searcher）依据用户待检索单词，在词典哈希表中查出对应的单词标识符。然后到后项索引中查找与该单词标识符对应的各个相关文档； Pointer to Lexicon 为单词在词典库中的位置指针，用于核对哈希值冲突的单词，在词典中按单词的字符逐一核对； Pointer to Next Item为指向链表下一项的指针，用于链表的遍历查找 2.2.3 Hits列表 Hits列表是指特定单词Word在某个页面文档（Document）中每次出现时的状态的列表，包括单词出现位置，出现频率，字体大小和单词大小写等信息。Hits存储的信息对于搜索引擎页面优化算法非常有用，往往决定着单词在页面文档中的重要程度，因此对用户查询的相关度影响重大。 2.3 索引结构 2.3.1文档索引库文档索引库（Document Index）用于查找，定位每个Web页面文档，它是一种固定长度的ISAM(Indexed Sequential Access Method索引顺序存储模式)索引，按照文档标识号DocID关键字排序。该索引条目记录了当前文档的状态，页面存储器中的位置，文档校验和其他一些统计数据。结构如图2.6所示： DocID Status Point to Repository Checksum Other statistics 图2.6文档索引库结构 DocID：文档标识号，用作排序关键字； Status：文档状态，包括文档是否已被抓取等信息 Point to Repository：指向文当在页面存储库中的位置指针 Other statistics：文档的其他统计信息如果文档已经被抓取，则文档索引条目中的Other statistics包含一个指向名为docinfo的可变长度文件的位置指针，该文件包含了文档的URL和标题信息。否则，如果文档未被抓取，则该指针指向URL列表，其中仅包含了URL信息。这种数据结构设计的目的是获得合理紧缩的数据结构，以及仅通过单次磁盘搜索就可以取得所需记录的能力。 2.3.2前向索引表前向索引表事实上已经完成了部分的排序，存储在一系列的“存储桶”中。存储桶的数量设计为64个，每个存储桶保存了一定范围内的单词标识号WordID。当一个页面文档包含由某个存储桶内的单词时，该页面文档标识号DocID就被存储到该存储桶中，同时将相关的但此列表及其Hits列表一个存入其中。 DocID 文档标识号 Word单词标示号 Nbits：Hits列表长度 Hits条目 Word单词标示号 Nbits：Hits列表长度 Hits条目 … … … Null空标示图2.7 前向索引表每个DocID后面紧跟多个《WordID，Nbits，hitlist》序列，以空标示Null作为分隔符。 2.3.3后向索引表后项索引表实际上是利用已存在的前向索引表，经过排序器处理后形成的。后向索引表与前向索引表的主要区别在于：前向索引表的主关键字为DocID，后向索引表的主关键字为WordID。这是因为前向索引表时以每个页面文档为基础，对其包含的单词进行分析后形成的，自然以页面标示号DocID为主关键字；而后向索引表的功能是为了搜索引擎能够通过某个关键词但此查找到与之相关的页面文档，需要以单词标示号WordID为主关键字。图2.8为后向索引表 WordID 单词标识号 DocID文档标示号 Nbits：Hits列表长度 Hits条目 DocID文档标示号 Nbits：Hits列表长度 Hits条目 … … … Null空标示图2.8 后向索引表项结构 3基于Nutch的搜索引擎实现的关键技术 3.1网页抓取技术研究与设计 3.1.1抓取技术的协议分析搜索引擎的第一步工作是在Web上收集网页并将其存入页面存储库，即网页抓取。目前搜索引擎都采用一个叫网络蜘蛛（Web Spider）的机器人程序来完成网页的抓取工作。网络蜘蛛实际上是一个很形象的名字，吧互联网比喻成一个蜘蛛网，那么Web Spider就是在网上爬来爬起去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页开始），读取王爷的内容，找到在网页中的其他链接地址，然后通过这些连接地址寻找下一个网页，这样一直循环下去，直到把整个网站的所有网页都抓去完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。 3.1.2通信协议 HTTP是面向分布式和协同式超媒体信息系统的应用层协议，是www分布信息的主要通信协议。HTTP是建立在TCP之上的协议。要从Web上抓取网页，也就是通过HTTP协议与Web服务器之间进行数据通信，所以在研究网页抓取技术前要对用到的通信协议进行简要介绍。 HTTP是一个请求/响应方式工作协议 1． HTTP请求行一个HTTP请求由请求行，可选的个数的请求首标和一个空行组成使用POST方法时还允许由一些附加数据。请求行格式如下：请求方法 URL HTTP/版本号 2． HTTP响应状态行在收到一个合法的请求（请求行，任选的首标，空行）之后，服务器返回一个装太行，一个或更多的响应首标，一个空行，以及关联的文档，状态行格式为： HTTP1.0 / 版本状态码消息 3．与HTTP服务程序通信 HTTP是一个相当简单的协议，依据HTTP传输机制，客户端可以与HTTP服务器程序进行通信，它的简单工作流程如下：（1）客户首先打开一个与HTTP服务程序的套接字连接，默认值为端口80；（2）然后发一行请求，一些可选的请求首标与一个空行来发布命令（通常是对一个文件的请求）。在某些情况下，服务器程序的数据包含在空行之后；（3）接着HTTP服务器发送一个响应行，某些响应首标，一个空行与一个文件；（4）关闭连接； 3.1.3 HTML解析当采用的网络蜘蛛进行网页抓取时，网络蜘蛛为了从一个网页到令一个网页必须存储它所访问的每个页面中的链接，因此它就要分析网页的HTML代码定为所有能指向其他网页的标签（tag）。多数能连到其他王爷的标签具有HREF（hypertext reference）属性。所有HTML链接被包含在HREF HTML属性中。HREF属性通常和anchor tag和image map结合在一起。对Web Spider来说，就是要找到HREF中的链接，例如下列中的nextpage.html。（1）<a herf=”nextpage.html” alt=”Go Here”>Click Here</a> (2) <map name=”sample”> <area shape=”rect” cords=”20,27,82,111” Herf=”nextpage,html”> <area shape=”default” nohref> </map> 依据包含在HREF中的数据的不同，网络蜘蛛找到的链接有三种类型：同属于相同Web服务器的内部链接，不同站点的外部连接和指向非网页的其他链接（如Email地址）。网络蜘蛛依据找到的内部链接和外部连接再连到其它的页面。 3.2 网页抓取方法对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的数据看，容量最大的搜索引擎也不过时抓取了整个页面数量的40%左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有网页，有许多网页无法从其他网页的链接中找到；另一个原因是存储技术和处理技术的问题，如果按照每个页面的平均大小为20K计算（包含图片），100亿个网页的容量是100×2000G字节，即使能够存储，下载也存在问题。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因此，搜索引擎的网络蜘蛛只是抓取那些重要的页面，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。在抓去网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先。广度优先是指网络蜘蛛会先抓取起始网页中连接的所有网页。这是最常用的方式，因为整个方法可以让网络蜘蛛并行处理，提高其抓取得速度。深度优先是指网络蜘蛛会从一个起始页开始，一个链接一个链接的跟踪下去，处理完这条线路之后再转入下一个起始页面，继续跟踪链接，整个方法有个优点是网络蜘蛛在设计的时候比较容易。两种抓去顺序的比较如下图2.9：图2.9 两种以页面抓取方法的比较由于步可能抓取所有的网页，有些网络蜘蛛对一些不太重要的网站，设置了访问的层数。例如，再上图中，A为起始网页，属于0层，B，C，D，E，F属于第一层，G，H属于第二层，I属于第三层。如果网络资助设置的访问层数为2的话，网页I是不会被访问到的。这页让有些网站上一部分网页能够在搜索引擎上搜索到，另外一部分则搜索不到。对于网站设计者来说，扁平化的网站结构设计有助于搜索引擎抓去其更多的页面。相应于页面抓取的两种策略就有两种方式来构建网络蜘蛛程序：递归方式和非递归方式。对于网页爬取来说使用递归看似非常合理，因为Web Spider执行的是重复的操作。例如考虑以下伪代码：尽管看起来递归是构建spider的合理选择，但是这种情况仅在访问的网页数量相对较少时适用，因为递归的每一次执行都会将程序的相关信息压入堆栈中，网页越多递归程序自行的次数也越多，堆栈将会变得愈来愈大最终系统内存会被耗尽致使程序停止运行。在运用多线程时递归程序也不适用，因为每一个线程有它自己独立的堆栈，这样就造成了与递归程序的不兼容。构建网络蜘蛛的第二种方式是非递归方式，这种方式使用队列存储URLs和广度优先的抓取方式。信发现的页面放在对列中等待网络蜘蛛处理。网络蜘蛛程序使用四个队列，URL在被处理的不同阶段将被放在不同的队列中：（1）等待队列：在这个队列中，URLs等待Web Spider来处理。初始的URLs和新发现的URLs被加入此队列中。（2）运行队列：Web Spider从等待队列中取出URLs，就将其放入此队列。放在此队列中的URLs所指向的页面被下载，同时解析被下载页面中的HTML代码以及发现新的URLs并加入等待队列。为了防止一个URL被处理多次，一旦它被处理被移入错误队列或完成队列。（3）错误队列：页面被下载后如果发现错误，这个URL就将移入错误队列，Web Spider将不再处理它。（4）完成队列：页面被下载后如果没有错误就被加入到此队列中，在此队列中的URL将不会移到其他队列中。一个URL在某一时刻仅处于一个队列中，下图是URL被网络蜘蛛处理时的状态变迁图3.10 完成队列 url处理完成错误队列运行队列等待队列图2.10 URL状态变迁图 4 基于Nutch的搜索引擎实现架构 4.1 基于Nutch的搜索引擎开发环境和体系结构基于Nutch的搜索引擎是java技术对搜索引擎的三个主要部件（网络蜘蛛，索引器，搜索器）的实现，能很好的完成搜索引擎的基本功能。 4.1.1 基于Nutch的搜索引擎的开发环境在实现搜索引擎的时候需要以下几个软件：（1） jdk5.0（java程序开发包）（2） tomcat5.5(Servlet / Jsp容器) （3） MyEclipse(开发平台) （4） Luence（Apache开源项目，实现索引和搜索的java类库） 4.1.2基于 Nutch的搜索引擎的体系结构基于Nutch的搜索引擎是构建在Apache开源项目Luence之上的，利用Luence实现索引和搜索，在此基础之上完成网络蜘蛛的实现。其体系结构图如下图4.1所示图4.1 Nutch Architecture （1）在基于Nutch的搜索引擎中，网络蜘蛛Crawler的实现如下： Crawler算法：创建一个新的网页数据库把开抓取的根URL放入网页数据库(inject) 重复以下3步直到达指定的抓取层数 -从网页数据库的新url信息生成抓取列表(generate) -根据抓取列表抓取网页的内容(fetch) -根据抓取回来的网页链接url更新网页数据库(updatedb) 利用计算出的网页url权重更新抓取的网页信息(updatesegs) 倒排links并且生成linkdDB(invertLink) 对抓取的网页建立索引(index)

展开阅读全文