海量Web 信息搜集系统优化设计

1海量Web信息搜集系统优化设计2论文摘要本文首先由的起源和发展导出搜索引擎技术的出现和发展。北大天网是这类技术在中国的最早的成功产品之一，本文将大体介绍其体系结构和技术特点。搜集端（crawler）是天网的主要模块之一，它的搜索速度、获取网页质量是评价搜索引擎好坏的主要指标，是检索端的工作的基石。如何更快，更好的抓取网页是本人毕业设计的工作目标。在介绍完搜集端现有的体系结构之后，本文从搜索导向、相似网页、相关度权值给定三个方面阐述它的优化策略，作为本文的重点。最后，本文试图指出现有系统的处理能力极限和瓶颈，并在此基础上作新的体系结构的探讨。关键词：搜索导向，replicas-finding,crawler,URLordering3第一章背景介绍§1.1（WorldWideWeb）起源于1989年欧洲粒子物理研究室(CERN)。月提出的，第一个原型（基于文本）于18个月后运行。的核心技术是超文本和超媒体。通过将文本、图形、图象、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。在十多年的时间里，的信息容量巨增，根据NEC研究院在《自然》上发布的数据[3]，截止到1999年2月，Internet上共有网站16.0M个，其中公开提供万个；共有亿页，这些网页包含了15T字节的数据。按照2000年4月在波士顿举行的第5届搜索引擎年会的会议报告[4]，我们可以知道现今的网页数目已经超过了10亿页。年登陆中国，在到现在仅仅6年的时间里发展速度惊人。根据CNNIC(中国互联网络信息中心)在2000年1月的统计信息表明[5]，中国已有上网计算机350万台，其中个；上网人数890万。关于网页的数目没有具体的统计数据，但根据《科学》杂志上提供的集合估计法[2]，通过中国几个主要搜索引擎获得的搜索数据（天网、新浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过1000万页。§1.2搜索引擎的出现和发展面对浩瀚的信息资源，用户在感到进入信息社会的兴奋之后，立刻觉得不知所措，太多的信息使我们很难迅速定位我们真正需要的信息，而跟随超链在上漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在上进行导航。在1994年，第一代搜索引擎出现了，例如Lycos,Infoseek,AltaVista和Exite。这时，它们还处在研究阶段，数据量少，检索速度慢是它们的突出缺点。最近这几年里，搜索引擎技术有突飞猛进的发展，出现了AltaVista，Inktomi，Google，Inktomi的DirectoryEngine，Inktomi,FAST,NorthernLight等成熟的搜索引擎产品，它们日趋变的好用，成为用户必不可少的工具之一。“北大天网(Webgather)”是CERNET在“九五”攻关项目“计算机信息网络及其应用关键技术研究”中设立了“中文编码和分布式中英文信息发现”子专题，北京大学网络研究室承担了该子专题的部分研究开发工作，设计开发了“天网”中英文搜索引擎（WebGather）[3]。1997年10月29日，天网搜索引擎正式在CERNET上提供查询服务。《软件世界》（1998年7月）将天网评为国内最值得关注的搜索引擎，1998年12月，天网通过了CERNET的鉴定。之后，天网又进行了大量的技术创新和系统的完善。到目前为止，天网总访问量已经突破5,000,000，并且仍以每天大于30,000的访问量递增。4第二章系统概述§2.1“天网”体系结构简介“天网搜索引擎”由两个主要部分组成,分别是搜索端和检索端[refer]。搜索端从上抓取网页，经过分析提取出必要的信息存放到数据库中去（天网目前使用的是informix数据库），当数据库完成一次更新后检索端便可依据数据库internet搜集端搜集数据库分析器检索端检索数据库图2.1搜索引擎总框架图2.2搜集端结构5中存放的信息对用户的检索请求做出答复了，也就是把用户想要的网页例出。从检索的效率上考虑（数据库往往把功能作得很完善，我们宁可扔掉一部分于我们无用的功能，来换取高速的读取），搜集端不是直接从informix数据库中读取信息，而是从由数据库生成的中间文件中读取信息的。结构如图2.1。本文讨论的搜集端的各部分组件及其功能如图2.2。搜集端按如下方式工作，先由主控启动多个gather进程,并给它们逐一分配一个网上的URL,由它们负责去网上抓取网页。Gather对取得的网页进行分析，把结果送给主控，由主控对数据库进行操作，主控可以从gather送来的结果中获得新的URL，再分配给gather。由于网络有时可能不能正常工作，gather把自己在某一时刻的工作状态纪录在共享内存里面，restart进程负责巡视共享内存，处理gather遇到的各种问题，改进程为什么被称作”restart”，是因为当它发现有gather进程由于一些网络上的原因不能正常工作时（如分配的URL不存在，我们称之为“死链”），由他结束该gather的本次任务，分配新的任务后重新开始。为了协调网络速度和CPU处理能力的差异,在一台主机上启动多个gather,并且gather数目可以调节。§2.2技术特点搜索引擎最早只针对于对西文，西文（如英文，法文）又一个特点是，有天然的分割语义的最小单位—词的分割符‘’（空格），而中文词与词之间没有空格。在现代汉语中，大部分的词都是双字节、多字节词，其中单个字的意思与整个词的意思相差甚远，尤其对大量涌入的音译外来词，如因特尔，迪士高，麦当劳等，单个字与整个词的意思基本一点关系都没有。既然词是表达意思的最小单位，“天网”通过一些切词程序，把词从网页中提取出来，网页信息以词的形式被储存。在处理用户查询时，也从词的角度对用户输入作某种理解，再去数据库中查找。这些词被称为关键词，要求能反映文章的内容。现代汉语词类有名词、时间词、方位词、数词、量词，代词、动词、形容词、副词、介词、连词、助词、拟声词，成语等等[ref]。这些词中，助词、连词、介词等词类是不具有这种功能的，一大堆的“但是”、“虽然”、“的”、“呢”、“最”是不能让我们猜出文章的任何内容的。这些词不能代表文章的内容，却在文章中以极高的词频出现。我们把它们叫做“stopword”，在提取关键词时把这些词滤掉。这一点是“天网”的基本特点，也是本文将要提到的基于关键词的“相似网页发现算法”的基础。6第三章搜索导向策略探索（5页）§3.1起源与目标搜索引擎从一个（也可以是一组）起始URL开始，当完成这个网页P0的获取与分析后，它能从P0中提取所有出现的超链（hyperlink）,这些新的URL被插入到一个备搜索的URL队列里面去。搜索引擎以某种顺序从队列里面取出URL,重复前面的过程。决定这种顺序，我们称之为“搜索导向”。显而易见的提议是，先搜索最“重要”的。当我们的搜索引擎受到时间和存储空间的制约，而不能覆盖整个网落时，快速的获得“重要”的网页是非常有用的。这一项工作几年前JunghooCho等人作过，他们在斯坦福大学的校园网上作了实验，对比采取导向与不采取导向搜索引擎的效果。他们最终的结果是，采用了导向机制的搜索引擎比不采用的获得“重要”网页的速度要快得多。首先，我们需要一定的尺度去描述“重要”。由于某一篇网页是否“重要”就是由用户“主观”评价的，各种各样的用户有各种各样的需求，你不可能完全懂得用户想要什么东西，因此这个尺度不是绝对的。因此，我们后面的广义的评价网页“重要”程度的方法有某种尝试、探讨的性质。强调用户的各种需求，把搜索引擎做成针对各个专业的，或提供分类检索，成为搜索引擎的发展方向之一。§3.2如何搜索导向如图3.1，上的网页通过超链指向其他网页，也被其他网页的超链所指向，于是构成了一张巨大的有向图。搜索引擎在网上搜索就是一个遍历有向图的过程。对于有向图的遍历，有深度优先和广度优先两种常用方法。当使用深度优先策略时，搜索引擎总是先搜集离初始网页距离较近的网页，这样网页搜集的质量严重依赖于初始网页的选取。当使用深度优先的导向算法时，我们发现在上网页之间的链接有这样的特点，如图3.2。，三个站点A，B，C（大圆圈表示），它们都包含了大量的网页（小圆圈表示）。存在一些超链，从一个站点中的网页指向另一个站点中的网页。但A,B,C之间的超链远远少于指向本站点网页的网页。从北大的主站点上就可以明显的看到这种情况。在域名下，北大主页存在68个超链，全部指向站内网页。站点内的其他网页网页也很少有指向站外的超链，唯一例外的是一篇《网络导航》的网页（URL），其中含有大量的指向其他站点主页的超链。面对这种情况，如果使用深度优先策略，当搜索程序进入站点A时，通常是要把A中的网页全部搜完才有可能从A中撤出。这样对目前国内的15153个站点图3.1:网页的链状结构ACDB7（CNNIC2000年1月统计信息），天网只能搜索其中十分之一，只是非常不好的。于是我们必须采取另外的策略进行搜索导向。我们选取一些关于网页的参数，通过这些参数的大小来对网页排序决定访问的先后。参数选取的好坏直接关系到我们能不能在“天网”有限的容量里囊括所有被用户所关心的，“重要”的网页。我们以后的工作基于这样一个假定：通过天网检索系统访问的越多的URL，用户对它的倾向性就越强，我们就认为它越重要。每一片网页被访问的次数是通过统计”天网检索端”运行一段时间的对用户查询纪录的日志得到的。由于网页在不断更新，我们在第二次搜索时，并不知道那些网页将被访问多少次，也就是说对新出现的网页，利用网页被访问次数来进行搜索导向是不可能的。于是，我们就想通过一些在搜索前或搜索中能得到的，与被访问次数有良好的正比（或反比）关系的参数来进行搜索导向。这些参数的选取、评价在以后两节有详细的讨论。§3.3导向参数选取通过对信息组织结构的分析，我们对下面几个参数作了考虑：1．网页入度。网页中出现的超链（hyperlink）看成是由一个网页指向另一个网页的一条有向边，网页本身就是一个节点，这样整个就构成了一张巨大无比的有向图。可以用入度函数I(P)来表示整个网络指向网页P的超链的数目。我们假设，一个网页如果被大量的其他网页链接，它就比另一个很少被链接的网页要重要。看上去是这样，例如：1、是一个介绍C++编程技术的目录网页，还有其他一些书籍的目录网页经常被其他网页链接，这种网页对用户获取更多的信息是非常有用的，因此它们是很重要。2、一些娱乐网站，提供视频点播，声讯服务等功能，也被大量的网页链接着。3、政府部门的一些网页，象（关于西部大开发的宣传网页），被大量链接。4、商业网站主页之间存在着大量的链接，主页被链接图3.2网站间网页的链接8得多少，反映了商业网站的影响力。总之，只有当其他网页的编辑者认为此网页重要时，才会在他们所编辑的网页中加入指向此网页的超链。与国外的一些文章一样，我们认为网页入度最有可能被选作导向参数。2．网页的镜像数目。对于一则新闻，我们常常用“被多家报刊杂志转载”来形容它的被关注程度。对于网上的各种信息，如新闻、文学作品、技术文档等，如果它真的被大量网民所关注的话，就会有很多网站把这篇网页拷贝过来，也许会略加改动。这种拷贝网页我们称之为“镜像”。3．域名深度与目录深度。域名和目录都是人们用层次结构组织信息的一种方式。网页处在这种层次结构中的深浅是否与人们对它的关心程度有某种联系？联系是什么？于是我们把上面三个数据作为我们研究的目标，试图