一、研究背景 1 、Internet与WWW发展现状 [5] (1)Internet 的发展历程     Internet 的前身是美国国防部高级研究计划署的研究试验性网络ARPANET。1983年TCP/IP成为ARPANET上唯一的正式协议。此后，ARPANET上连接的网络、机器和用户快速增长。1988年NSFNET和ARPANET互联，它的规模以指数增长，很多地区网络开始加入，并且开始与加拿大、欧洲和太平洋地区的网络连接。后来形成Internet。90年代初到现在，是Internet增长最迅速的时期。1993年，Internet的增长速度是341%。截止到1996年7月，Internet已连接了134336个网络，入网主机1228万台，以及数以亿计的用户。到1998年7月，Internet已拥有427万个网址，4300万个域名，3673.9万台主机和3.2亿个网页，其规模大概每年翻一番。   (2)World Wide Web(WWW)     World Wide Web(WWW) 是全球性的网络信息系统。一九八九年，位于瑞士的European Laboratory for Particle Physics(CERN)首先开始了WWW的研究工作。随后，许多其他的研究机构、大学和公司也加入WWW研究者的行列，并相继开发出各自的WWW软件。这些WWW软件的运行平台覆盖了目前主流的计算机硬件和操作系统。在此过程中，WWW也不断完善和发展。同时，为了保证不同WWW软件之间的互操作性，一系列WWW协议和标准也正在使用和完善之中。     在最近几年里，WWW得到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据NEC研究院在《自然》上发布的数据，截止到1999年2月，Internet上共有网站1600万个，其中公开提供WWW服务的网站280万个；共有WWW网页大约8亿页，这些网页包含了15T字节的数据。按照2000年4月在波士顿举行的第5届搜索引擎年会的会议报告，我们可以知道现今的网页数目已经超过了10亿。     WWW 在中国的发展速度也十分惊人。根据CNNIC(中国互联网络信息中心)2001年1月17日在京发布的《中国互联网络发展状况统计报告》，截止到2000年12月31日止，我国上网计算机数有约892万台。我国上网用户人数约2250万人，除计算机外同时使用其它设备（移动终端、信息家电等）上网的用户人数为92万。CN下注册的域名总数为122099个，WWW站点数（包括.CN、.COM、.NET、.ORG下的网站）约265405个，我国国际线路的总容量为2799M。关于网页的数目没有具体的统计数据，但根据《科学》杂志上提供的集合估计法，通过中国几个主要搜索引擎获得的搜索数据（天网、Chinaren、新浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过3000万。   (3)Internet 的信息分布     Internet 上的信息资源随着Internet的发展而呈现出以下特点： l    信息量大而且分散 l    自治性强 l    信息资源多种多样 l    不一致和不完整性     这些特点对网络软件的性能提出了很高的要求。网络的快速发展给信息挖掘带来了挑战。WWW上信息呈现爆炸性的指数增长，同时伴随着上网经验不足、不太了解如何查找信息的新用户的加入。用户很可能最大程度的运用超链来在网上冲浪，他们通常从以下两类网站开始：     第一类是目录系统，其典型代表是Yahoo!的分类目录（http://www.yahoo），Yahoo的分类目录通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类通过手工维护得很好的系统的优点是提供的网页准确率高，可以有效的覆盖所有热门的主题，但它们的缺点是过于主观，而且需要高昂的代价来建立和维护，更新改进的慢，同时不能很好的覆盖所有深奥的主题。     第二类是搜索引擎系统，比如天网中英文搜索引擎（http://e.pku.edu），它通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类通过关键词匹配实现查找的自动更新的搜索引擎优点是涵盖的网页数量巨大，但通常返回太多的低质量相关性不大的结果。   二、 国内外研究现状 1 、搜索引擎发展简史     面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。     搜索引擎技术伴随着WWW的发展是引人注目的。搜索引擎大约经历了三代的更新发展：     第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。在实现技术上也基本沿用较为成熟的IR（Information Retrieval）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。在1994年3月到4月，网络爬虫World Wide Web Worm(WWWW)平均每天承受大约1500次查询。     大约在1996年出现的第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50,000,000网页的索引数据库，每天能够响应10,000,000次用户检索请求。1997年11月，当时最先进的几个搜索引擎号称能建立从2,000,000到100,000,000的网页索引。Altavista搜索引擎声称他们每天大概要承受20,000,000次查询。     自1998年到现在，出现了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引擎为第三代搜索引擎。第三代搜索引擎的发展有如下几个特点：      (1) 索引数据库的规模继续增大，一般的商业搜索引擎都保持在几千万甚至    上亿个网页。      (2) 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。      (3) 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研究又可以分为两类：一类是对超文本链的分析，在这方面Stanford大学的Google系统和IBM的Clever系统作出了很大的贡献；另一类是用户信息的反馈，Direct Hit系统采用的就是这种方法。      (4) 开始使用自动分类技术。Northern Light和Inktomi的Directory,Engine都在一定程度上使用了该技术。       2000 年搜索引擎2000年大会上，按照Google公司总裁Larry Page的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4,000,000网页。       现在有许多网站推出号称第四代的搜索引擎，但是因为没有明显的标志，“第四代”的说法还仅仅是一个说法，并没有成为一个明显的趋势。随着时间的推移，相信会有一个比较统一的标准形成。   2 、几个著名的搜索引擎 (1)AltaVista     AltaVista 创建于1995年12月，其网络域名是http:/www.altavista.conm。在不考虑网络传输速度的情况下，AltaVista每秒可以检索200Gb的数据量，作为一种搜索的量化指标，这个速度远远快于你在硬盘上找一个文件。[2]   (2)Yahoo     Yahoo 最开始是比较常用的查询工具，后来发展成综合性的网站，涵盖搜索、新闻、邮件等。其域名是http://www.yahoo。Yahoo的真正实力来自Yahoo的分类层次，Yahoo的定位非常准确，他们的主要服务对象是查询者而不是其它网站的网管。作为一个其它网站网址的收录者，它正确地处理了查询者、网络管理员之间的相互关系。对于提供网络目录服务站点来说，数据库中储存的网址信息越丰富、越准确，越能为查询者提供高质量的服务，而高质量的服务是维持高访问率的关键。使用人工进行站点分类是一项极大的工程。一般站点只有两层到三层目录来归纳与日俱增的上百万个信息点，而Yahoo通常都有十几层，它所提供的详细分类索引能帮助用户迅速找到相关站点。[2]   (3)Google     Google创建于1998年，网络域名是http://www.google。6年来，Google公司已经由一个纯粹的搜索引擎网站发展为一家非凡的门户网站——拥有广告网络、对比购物服务、电子邮件和Web出版产品，是全球影响力最大的搜索引擎之一。Google支持100多种语言，界面简洁友好。它以其复杂而全自动的搜索方法排除了任何人为因素对搜索结果的影响。虽然Google也在搜索结果旁刊登相关广告，但没人能花钱买到更高的网页级别，从而保证了网页排名的客观公正。Google可以方便、诚实、客观地在网上找到有价值的资料。Google目录中收录了10亿多个网址，这在同类搜索引擎中是首屈一指的。这些网站的内容涉猎广泛，无所不有。   (4)CiteSeer     CiteSeer 引文搜索引擎由NEC公司在美国普林斯顿的NEC研究所(NEC Research Institute，Inc)研制开发，网络域名为http://citeseer.ist.psu.edu。1997年起利用自主的研究成果“自动引文标引系统”在网上建立样品数字图书馆，并起名为“CiteSeer-Scientific literature digital library”，公开在互联网上提供服务。 CiteSeer 采用机器自动识别技术搜集互联网上Postscript和PDF文件格式的各种类型的学术论文，然后依照引文索引方法标引和连接每一篇文献。至今CiteSeer标引的网页数超过1000万，存储的文献全文达60万篇；内容主要涉及计算机科学领域，主题包括智能代理、人工智能、硬件、软件工程、数据压缩、人机交互、操作系统、数据库、信息检索、网络技术、机器学习等。 读者访问CiteSeer既可像使用搜索引擎那样检索浏览相关学术文献，也可利用其特有的引文检索功能查看文献的引用与被引用信息，同时还能获得相关学科最新文献与出版物引用排行。系统实现全天24小时实时更新，包括下载PS或PDF格式的全文。       除以上所介绍的搜索引擎外，还有如MSN、sohu、infoseek、northern、light、Lycos、Excite等著名的搜索引擎，这里就不一一介绍。   3 、搜索引擎的分类  (1) 通用搜索引擎     对所有网页和文件进行收录整理并提供搜索服务，又可以分为两类，一类以Google为代表，几乎完全是由程序自动控制整个流程，人为的干预很少，效率比较高，比较公平，但缺点是由于程序的信息处理能力的局限性，对于网页内容的分类不够准确，有可能给用户提供实际并不需要的页面链接；另一种以Yahoo为代表，依靠人工建立庞大细致的分类体系，方便用户找到自己最需要的页面，这样可以最大限度保证分类的准确性，但是互联网上的信息量正以前所未有的速度增长，人工分类的效率相比之下就过于低下了，不能满足“查全”的要求。   (2) 专业搜索引擎     针对某一特定领域或特定文件类型进行收录整理并提供搜索服务。例如CiteSeer，就是典型的专业搜索引擎。其他的如北大天网FTP搜索引擎，专门针对FTP目录下的文件进行搜索；最近随着博客（网络日志）兴起而兴起的博客搜索引擎， 由于 博客的分类机制比较稳定，而且博客的世界里常常关心的是最新的最有意思的一些新闻，因此未来很可能有大的发展；音乐搜索引擎、电影搜索引擎，针对特定的音频、视频文件格式提供搜索；等等。   (3) 元搜索引擎     元搜索引擎是基于通用Web搜索引擎GSE框架建立的一种搜索机制。GSE框架结构主要由用户、Web服务器、Web信息获取与处理接口、任务调度器、连接管理器Web及搜索引擎组成。用户只需递交一次检索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将所有查询结果集中起来以整体统一的格式呈现到用户面前。通用Web搜索引擎框架将因特网上众多的现有的Web搜索引擎看成一个整体，为用户提供一个透明的分布式异构Web搜索引擎环境，该种方式的引擎可以看作元搜索引擎，它为用户提供一个统一的、集成的查询请求，元搜索引擎根据知识库中的信息转换为各个Web搜索引擎所能识别的格式，然后发给各个搜索引擎，由这些搜索引擎完成实际的信息检索。元检索引擎在搜索到各个Web搜索引擎系统返回的结果后，经过比较分析，然后以一定的格式返回用户。   4 、搜索引擎目前主要存在的问题[4]       现在的搜索引擎可谓“百花齐放”，Google、Yahoo、百度、天网等搜索引擎激烈竞争，连之前很少涉及搜索引擎领域的微软也按捺不住，推出了MSN搜索引擎。但是仍然有许多问题：      (1) 网络信息量太大，而且处于不断的更新当中，难以进行全面的收录，而且收录得越多，全面的更新越困难。      (2) 对于搜索引擎使用者的真正需求，程序并不能准确判断。同样的关键词，不同的人可能需要查找的内容不一样。要在返回查找结果的过程中，将所有结果按重要程度从高到低的顺序组织起来呈现给用户，排序算法是十分关键的。 目前许多搜索引擎都使用基于关键字查询的传统的信息检索算法和技术，返回的页面数量仍然是成千上万。然而“据估计近85%的用户只浏览搜索引擎返回的第一页结果”因此，如何将用户最感兴趣、最重要的页面放在搜索结果的前面就成为影响搜索质量的一个重要因素。      (3) 现在越来越多的人为了能够在搜索引擎返回的结果中排位靠前，特别针对搜索引擎的算法进行一定的优化，如在网页中大量添加热门搜索词汇等，影响搜索引擎的正确判断，使得用户得到许多毫无用处的结果。      (4) 分词技术不完善，对中文的检索结果很多不能与用户期望的很好匹配。   5 、天网搜索引擎系统结构及各部分功能 简介     天网系统主要由WWW信息存取和分析子系统(主控程序)、WWW信息收集控制子系统(搜索器)、资源索引数据库、信息检索子系统、管理和监控子系统等几个部分组成。各个部分的功能如图所示： 图1 WebGather系统总体结构示意图 (1)WWW 信息存取和分析子系统（主控程序）     根据WWW信息收集控制子系统提供的URL和相关信息，使用HTTP协议，在Internet上获取相关资源，并能就对方主机返回的不同状态码作出相应处理。对取回的Web页面(主要是HTML格式)进行分析，自动对中文编码进行识别和转化，对中文信息进行分词、提取页面的标题、关键词、摘要以及其中的超链（HyperLink）。将分析的结果通过扩展SOIF接口提交给信息收集控制子系统。 (2)WWW 信息收集控制子系统（搜索器）     根据配置文件运用自然语言理解和知识获取技术、引导信息收集系统优先访问特定知识领域和特定地域范围内的信息，向HTML存取分析进程发送需访问的URL及相关信息，接收其发回的访问和分析结果。将相应的数据存入信息数据库中。并对信息收集的频度和流量加以控制。 (3) 资源索引数据库     存储收集到的WWW信息，以及分析的结果。并对其重新进行基于词的分级优化索引，以加快查询速度． (4) 信息检索子系统     提供基于WWW方式的信息检索服务。用户通过任何标准的WWW浏览器直接访问。检索系统可以支持在一次检索中使用多个检索词(中、英文)，并支持检索词之间的逻辑关系（与、或）。还可以指定查询的范围和方式（精确、模糊）。检索结果以HTML形式返回给用户。各项结果的标题与它所对应的URL用超链连接起来。用户只需在浏览器中点中检索结果项的标题，就能马上取得相应页面的实际内容。命中的URL页面按它与用户检索关键词的关联程度排序，使用户的检索更有效率。系统还支持在上一次返回的结果中进行查询。   (5) 管理和监控子系统     提供系统配置，启动、停止、监控、统计等管理功能。 信息收集控制子系统与WWW存取分析进程之间的信息交互是通过TCP Socket连接来实现的，因此各子系统可以分布运行于网络中不同的主机上。 图2 管理系统结构图   6 、几种排序算法简介 (1)HITS 算法     它 是由康奈尔大学(Cornell University)的Jon Kleinberg博士于1998年首先提出的，HITS的英文全称为Hypertext-Induced Topic Search。目前，它为IBM公司阿尔马登研究中心(IBM Almaden Research Center)的名为“CLEVER”的研究项目中的一部分。Kleinberg认为搜索开始于用户的检索提问，每个页面的重要性也依赖于用户的检索提问，他将用户检索提问分为三种:特指主题检索提问(specific queries，也称窄主题检索提问)、泛指主题检索提问(Broad-topic queries，也称宽主题检索提问)及相似网页检索提问(Similar-page queries)。而HITS算法则专注于改善泛指主题检索的结果。Kleinberg将网页(或网站)分为两类，即hubs和authorities。应该注意的是，每个页面也有两个级别(ranking)，即hubs(中心级别)和authorities(权威级别)，authorities为具有较高价值的网页，依赖于指向它的页面，而hubs为指向较多authorities的网页，依赖于它所指向的页面。HITS算法的目标就是通过一定的计算(迭代计算)方法以得到针对某个检索提问的最具价值的网页，即排名最高的authority。