（计算机软件与理论专业论文）基于web的主题信息采集系统研究与设计.pdf

摘要 在i n t e r n e t 上信息呈指数级增长的背景下，w e b 资源显示出强大的动态不 稳定性，主题用户要找到特定的w e b 主题信息越来越困难。针对该问题，本文以 主题搜索引擎和元搜索引擎技术为背景，研究了基于w e b 的主题信息采集系统 ( 聚焦爬行系统) 的几个问题：首先，研究了w e b 主题词典的建立问题，提出一 种自动动态建立w e b 主题词典的方法，该方法的特点在于，它能自动地从w e b 网站的链接结构中抽取出内容结构，然后基于该内容结构建立相应的w e b 主题词 典：其次，针对主题信息采集策略问题，提出了一种基于元搜索引擎的改进的 s h ( s i m p l eh e u r i s t i c s 简单启发) 算法，该改进的算法比原算法更适应于中文 环境，它是一种基于内容的搜索策略，比基于结构的搜索策略如h i t s ( h y p e r l i n k i n d u c e dt o p i cs e a r c h 超链接引导的主题搜索) 等在搜索主题资源方面有着更 高的效率。同时，由于它是基于元搜索引擎的，根集合的形成不需要耗费太多的 资源，并且可以实现用户实时动态的查询请求；第三，在采集系统结构方面，采 用了非递归的爬行器结构，且各个功能分别通过松耦合关系的不同类组来实现， 使得该系统的可扩展性良好；最后，以敦煌学主题为样本设计和实现了一个基 于w e b 的主题信息采集系统，并对该系统的采集效果进行了比较分析，证明该系 统采用的主题搜索策略良好，可以较好地解决主题用户“资源迷向”的问题。 关键词；w e b 主题信息、信息采集、元搜索引擎、超链接、敦煌学 项目资助：科技部社会公益研究专项资金项目敦煌文物保护数字化研究( 项目编号：2 0 0 1 d i b l 0 0 6 0 ) 1 a b s t r a c t w e br e s o u r c e sp r e s e n ts t r o n gd y n a m i ci n s t a b i l i t yw i t ht h ef a s ti m p r o v e m e n to f i n t e r a c ti n f o r m a t i o n ，t o p i cs p e c i f i cu s e r sb e c o m em o r ea n dm o r ed i f f i c u l ti nf i n d i n g t h ew e bi n f o r m a t i o nt h a tt h e yn e e d a i m i n ga tt h i sp r o b l e m ，w et a k ea r e s e a r c ho nt h e f o c u s e dc r a w l i n g ( o rt o p i c - d r i v e nc r a w l i n g ) s y s t e mt h a tb a s e do nt h et e c h n o l o g yo f t o p i cs p e c i f i c s e a r c he n g i n ea n dm e t as e a r c he n g i n ei n t h i sp a p e r t h er e s e a r c h i n c l u d e ss e v e r a la s p e c t s f i r s t l y , w ep r e s e n tam e t h o dt h a tc a na u t o m a t i c a l l ya n d d y n a m i c e x t r a c tc o n t e n ts t r u c t u r ef r o mt h el i n ks t r u c t u r eo f t h ew e b s i t e s b a s e do nt h e c o n t e n ts t r u c t u r e ，w ec a na u t o m a t i c a l l yc o n s t r u c tt h ed o m a i n s p e c i f i cd i c t i o n a r y s e c o n d l y , w ea d o p ta ni m p r o v e ds h ( s i m p l eh e u r i s t i c s ) a r i t h m e t i cb a s e do nm e t a s e a r c he n g i n e t h ei m p r o v e da r i t h m e t i ci sm o r es u i t a b l ef o rt h ec h i n e s ee n v i r o n m e n t a n di ti sac o n t e n t b a s e da r i t h m e t i c s oi ti sm o r ee f f i e i e n tt h a nt h es t r u c t u r e b a s e d a r i t h m e t i ci nf i n d i n gt h et o p i c - s p e c i f i cr e s o u r c e s f u r t h e r m o r e ，b e c a u s ei ti sas y s t e m b a s e do nm e t as e a r c he n g i n e ，t h eg a t h e r i n go ft h er o o ts e tr e q u i r e sf a rl e s sh u m a n e f f o r ta n di tc a ns a t i s f yt h er e a l - t i m ed y n a m i cq u e r i e s t h i r d l y , w ei n t r o d u c ea n o n - r e e u r s i v em e t h o dt oc o n s t r u c t0 1 1 1 c r a w l i n gs y s t e mi nw h i c he a c hf u n c t i o ni s c o r r e s p o n d i n g t oak i n do fc l a s s g r o u p t h e f o c u s e d c r a w l i n gs y s t e m h a sa n e x p a n s i b l ec h a r a c t e r i s t i cb e c a u s e t h e s ec l a s sg r o u p sa r el o o s e - c o u p l i n gt oe a c ho t h e r f i n a l l y , w ed e s i g na n d o b t a i naf o c u s e dc r a w l i n gs y s t e mt h a tt a k e sa ne x a m p l eo f d u n h u a n gs u b j e c t t h er e s u l t ss h o w t h a to u rf o c u s e d c r a w l i n gs y s t e m h a sa ne x c e l l e n t s e a r c h i n gs t r a t e g y , a n di tc a ns o l v et h e i n f o r m a t i o nl o s t p r o b l e mo ft o p i cs p e c i f i c u s e t k e yw o r d s ：t o p i cs p e c i f i cw e bi n f o r m a t i o n ，f o c u s e dc r a w l i n gs y s t e m ，m e t a s e a r c h e n g i n e ，h y p e r l i n k ，d u n h u a n gs u b j e c t l i 原创性声明 本人郑重声明：本人所呈交的学位沦文，是在导师的指导f 独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文c j 已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：泌聪羹 日期：翌韭：垒：皇3 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产：权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：遁立群奠导师签名：生兰垒日 期：吐! ：兰：y 1 1 研究背景 第一章绪论 1 1 1w e b 的发展现状 w e b ( w o r l d w i d ew e b 或w w w ) 是一个大型的分布式超媒体信息系统。 在最近几年里，w e b 得到了长足的发展，不仅成为企业必不可少的组成部分并且开 始走进千家万户。根据o c l c 的一个研究w e b 特性的项目n - n 1 ，截止到1 9 9 9 年2 月，i n t e m e t 上共有网站1 6 0 0 万个，其中公开提供w e b 服务的网站2 8 0 万个；共有w e b 网页大约8 亿 页，这些网页包含了1 s t 字节的数据。而在2 0 0 2 年它们的采集数据显示全球有9 , 0 4 0 0 0 0 个 网站。由这五年的数据对比可见，w e b 发展迅速。可惜的是该项目没有再进行下去，在2 0 0 3 年就停止统计了。然而，在2 0 0 5 年4 月2 6 日通过访问g o o g l e 可知，它索引的网页数量已 经达到8 ，0 5 8 ，0 4 4 ，6 5 1 张了，可见，这几年w e b 仍然保持高速增长。 同时，w e b 在中国的发展速度也十分惊人口j ，2 0 0 5 年4 月1 4 日，中国互联网络信息中 心( c n n i c ) 发布了第四次中国互联网络信息资源调查报告。截至到2 0 0 5 年1 月，全国网页 总数为8 6 7 ，5 7 6 ，4 0 0 个，平均每个网站的网页数为1 ，2 9 7 个，全国网页总字节数为 2 0 ，5 3 7 ，2 1 4 ，7 1 8k b 。 总体来说，w e b 具有以下特点： 分布性w e b 中没有中心或权威领域，w e b 自发增长。 异质性w e b 内容、w e b 服务成果及w e b 网站结构等等都不相同。 动态性整个w e b 网页的增长率在每一段时期各不相同，有些网页动态形成或有 生命周期。虽然发展规则保持不变，但w e b 的统计数据只在很短时间内有效。 1 1 2 搜索引擎的发展 面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入i = 1 ，它是除了屯子 邮件以外最多人使用的网上服务。 搜索引擎大约经历了三代更新发展： 第一代搜索引擎出现于1 9 9 4 年。这类搜索引擎一般都索引少于1 , 0 0 0 ，0 0 0 个网页，极少 重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待1 0 秒甚至更长的时间。 在实现技术上也基本沿用较为成熟的i r ( i n f o r m a t i o nr e t r i e v a l ) 、网络、数据库等技术相 当于利用一些已有技术实现的一个w e b 上的应用。在1 9 9 4 年3 月到4 月，网络爬虫w o r l d w i d ew e b w o r m ( w w w w ) 平均每天承受大约1 5 0 0 次查询。 大约在1 9 9 6 年出现的第二代搜索引擎系统大多采用分布式方案( 多个微型计算机协同 1 二作) 来提高数据规模、响应速度和用户数量，它们一般都保持一个大约5 0 ，0 0 0 ，0 0 0 网页的 索引数据库，每天能够响应1 0 ，0 0 0 ，0 0 0 次用户检索请求。1 9 9 7 年1 1 月，当时最先进的几个 搜索引擎号称能建立从2 , 0 0 0 ，0 0 0 到1 0 0 ，0 0 0 ，0 0 0 的网页索引。a l t a v i s t a 搜索引擎声称他们每 天大概要承受2 0 ，0 0 0 ，0 0 0 次查询。 白1 9 9 8 年到现在，出现了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引 擎为第三代搜索引擎。第三代搜索引擎的发展有如r 几个特点： 1 索引数据库的规模继续增人，一般的商业搜索引擎都保持在儿千万甚至l ：亿个网页a 2 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点 开始使用该技术。 3由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研究又可以分 为两类：一类是对超文本链的分析，在这方面s t a n f o r d 大学的g o o g l e 系统”1 和i b m 的 c i e v e r 系统做出了很大的贡献：另一类是片j 户信息的反馈，d i r e c t h i t 系统采用的就是 这种方法。 4 开始使用自动分类技术。n o r t h e r nl i g h t 和l n k t o m i 的d i r e c t o r ye n g i n e 都在一定程度上 使用了该技术。 1 1 3 主题搜索引擎第四代搜索引擎的研究进展 搜索引擎要跟上w e b 发展的速度，将面临规模的问题。在1 9 9 8 年，a l t a v i s t a 的c r a w l e r ( 被称为s c o o t e r ) 1 5 1 ，运行在1 5 g b 内存，3 0 g br a i d 硬盘，i g bi o 带宽的4 5 3 3 m h z a l p h a s e r v e r4 1 0 0 5 3 0 0 上。s c o o t e r 与i n d e x i n g 引擎v i s t a 连接，v i s t a 为2 g b 内存，1 8 0 g b r a i d 硬盘，2 5 3 3 m h za l p h a s e r v e r4 1 0 0 - - 5 ，3 0 0 。尽管应用了高端的多处理器和精心醴计 的爬行软件，最大的搜索引擎也只能覆盖3 0 - - 4 0 的w e b 文档，并每两周更新一次p j 。这 样的困境是由于普通搜索引擎适应一切覆盖一切的原则造成的。这种情况下，主题搜索引擎 被提出。 主题搜索引擎有的文献也称之为“专业搜索引擎”或“专题搜索引擎”。本论文统一 称为主题搜索引擎。主题搜索引擎是与普通搜索引擎相对应的一个概念，是指为用户提供某 个主题或某个域( d o m a i n ) 的w e b 网页资源的检索服务，它与通用搜索引擎的区别主要体 现在资源和服务上，主题搜索引擎提供的资源都是与某个主题相关的，服务上更具有专业特 色，有一定程度的个性化。由于主题搜索引擎运用了人工分类、专业领域知识等智能化策略， 因此它比前三代搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为第四代搜 索引擎。这类搜索引擎有主题资源覆盖度高、智能化程度高、检索对象多样化、服务个性化 和专业化等特点。 主题搜索引擎在国内外已经有研究且已经取得了一定的进展。 1 ) 国外主题搜索引擎的研究现状及其存在的问题 国外最早使用查询来指导w e b 爬行器的系统是1 9 9 4 年出现的f i s h 搜索系统( f i s hs e a r c h s y s t e m ) 1 6 j 。后来相继出现了1 9 9 8 年的s h a r ks e a r c h j 、1 9 9 9 年的主题爬行器( f o c u s e d c r a w l i n g ) p , s l 。印度理工学院学者s c h a r k r a b a r t i 发表的一系列文章1 9 , 1 q ”，1 2 ，1 3 ，“】，在计算机 学术界掀起了研究主题搜索的热潮。最主要的研究成果由以下几个国外的项目中产生： ( 1 ) c o l l e c t i o n b u i l d i n g 项目，简称c b p ，是美国国家科学数字图书馆( n a t i o n a ls c i e n c e d i g i t a ll i b r a r y ，n s d l ) 支持下的一个子项目 1 5 , 1 6 , 1 7 i 旨在为科学、技术、工程和教育创建 太规模的在线数字图书馆，研究主题资源自动建设的可能性。因为该项目是面向教育、教学 服务的，强调的是准确度和中心度，所| 三i 每个类别的资源数量相对较少，主题覆盖度太窄。 ( 2 ) f o c u s p r o i e c t 项目，在该项目中，印度籍学者s c h a r k r a b a r t i 提出了一种新的w e b 资源的自动爬行系统，即主题爬行器( f o c u s e dc r a w l e r ) ，它对主题的定义既不是采用关键 词也不是加权词矢量，而是一组具有相同主题的网页，尽管称为面向主题的爬行器，但它实 际上是一整套关于特定资源的自动建设方法，实现在w e b 上查找、获取、索引和维护与特 定主题相关的网页，以建设w e b 主题资源。该系统的最早版本i o l 采用了两个程序：一个是 2 分类器，用来计算f 载文档与主题的相天度，间时也j f 来知道爬行器优先爬于亍相关资源；另 一个程序是抽取器( d i s t i l l e r ) ，用米确定那些指向很多相芙资源的阚页( 在h i t s 算法中， 称为中心网页) ，用相同的分类器同时来控制待爬行队列的优先级和评价f 载网页的相关度， 这样做会影响爬行性能的客观评价，错误地扩人了性能。后来，该系统有了改进版本”“， 设计了两个分类器，一个用来指导爬行，另一个用来计算下载网页与主题的相关度。此外， 该项目为用户预先提供分类体系和相关资源的功能可以有效地减少_ l ；i 户的学习时间，提供系 统的可用性，但是f o c u sp r o j e c t 没有提供基于主题词的搜索，只是根据用户提供的w e b 网 页来找出与之相似的网页，另外，它所搜集资源的数量也很有限。 ( 3 ) c i t e s e e r 是n e c 研究所的一个为了计算机研究提供文献保障的研究项目”。 c i t e s e e r 专门收集在w e b 上的各种样式的论文，包括学者个人主页、研究机构、计算机专业 的大型商业数据库等，对其内容做深入分析，同时抽取它的参考文献，利用s c i ( s c i e n c e c i t a t i o ni n d e x ) 技术，建立一个r e s e a r c hi n d e x 数据库，为科研人员提供文献服务。该系统 设计了一个自治引文索引系统( a u t o n o m o u s c i t a t i o n i n d e x i n g ，a c i ) 【l 埘。该系统可以自动 查找、抽取引文、判断不同格式的引文是否属于相同文献、识别论文主题的上f 文、提供引 文分析方面的统计数据。该项目符合w e b 在线资源自动搜集的宗旨。它的数据来源相对比 较稳定，主要来自学者的个人主页、研究机构主页、商业数据库等，并且只分析格式标准的 研究论文，不搜集w e b 网页的内容。尽管它也实现了主题爬行功能，但没有在预测u r l 与 主题的相关度方面作深入的研究，不适合面向因特网的主题搜索引擎的建立要求。 2 ) 国内主题搜索引擎的研究现状 国内的研究与国外相比还处于一个初步发展阶段，主要侧重于整个系统功能的实现，在 自动主题搜索上研究的层次还很浅。 ( 1 ) 网络智能知识服务系统i _ k n o w 2 0 i 是一个完整地网络智能知识服务系统，i k n o w 系统是一整套针对专业用户的智能知识服务系统，后来进一步发展为万方数据竞争情报计算 机系统( w i f s ) ，该系统旨在综合采集各种可以获取( 网络资源、电子文档、印本文档等) 的信息资源并进行统一的组织、整理、加工，最终服务用户。该系统服务于专业人员的情报 加工工作，可以为最终用户提供情报相关产品。 i - k n o w 系统最早采用通用爬行器模式来实现自动主题搜索的，后来采用了f i s h 算法 来提高主题搜索的性能口“。简单地说该系统在自动主题搜索上只采用了f i s h 算法。 ( 2 ) 南京大学软件新技术国家重点实验室1 2 “，设计了一个互联网数据采集系统。该系 统旨在对w e b 上中英文技术资料进行自动搜集。i d g s 根据用户提交的挖掘目标样本，在 w e b 上自动查找用户所需的信息，它采用空间向量模型和基于词频统计的权重评价技术。 该系统的关键技术在于它的一个模式匹配模块，其任务是计算实际采集到的网页与用户兴趣 之间的相交度。其基本思想是：如果某网页满足用户兴趣，则继续往下找，否则就终止该方 向的查找。该模型类似于f i s h 算法，“哪儿有草，鱼儿就往哪儿游”。但它只是简单地用父 结点的主题相关度来判断是否下载孩子结点，并且只在用户给出的有限种子站点基础之上爬 行，搜索的深度很有限，更多地强调准确度，在一定程度上忽视了覆盖度。 ( 3 ) 北大天网“”，北京大学计算机科学技术系网络与分布系统实验室一直从事搜索引 擎的研究，他们于1 9 9 7 年l o 月2 9 日正式在c e r n e t 上向广大i n t e m e t 用户提供w e b 信息 导航服务，致力于探索和研究中英文搜索引擎系统的关键技术，以便向广大用户提供更为快 速、准确、全面、时新的海量w e b 信息导航服务。天网从最早提供简单的网页信息查询服 务以来，不断推出文件搜索服务、天网目录服务、天网主题服务，同时还在研究个性化服务。 其中的“天网主题”就是致力于特定领域、地域、特定主题的资源搜索搜集。他们解决的关 键技术是网页分类技术。 1 2 研究目标 基于w e b 的主题信息采集系统是主题搜索引擎的前提和核心部分，本论文的研究e l 的 就是希望通过研究基于w e b 的主题信息采集系统，探索出一种能够自动快捷地搜索出w e b 上的主题资源的方法，以便更好地解决主题用户“资源迷向”的问题。 主题搜索引擎一般包含三个基本的部什：爬行器( c r a w l e r ) 、索引器( i n d e x e r ) 雨i 查询 服务器。爬行器( c r a w l e r ) 的功能是在互联网中漫游，发现和搜集主题相关信息，它常常 是一个计算机程序，日夜不停地运行。索引器( i n d e x e r ) 的功能是理解搜索器所搜索的信 息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。查询服务器功能是根据用 户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行 排序，并实现某种用户相关性反馈机制。一般的，主题搜索引擎还包括离线分析的主题领域 词典库。所以，主题搜索引擎的简单结构如图1 1 所示： 图1 1 主题搜索引擎结构图 主题信息采集是主题搜索引擎的前提和核心部分，它实现图l _ l 中的爬行器的功能。主 题信息采集系统面临的问题很多，本文主要讨论了信息采集系统实现时的三个主要问题，也 是图中虚线框部分涉及到的问题。即： 1 ) 主题信息采集的前提一主题词典的建立 通常一个主题是模糊的和不确定的，如何在一个合适的层次范围上精确地定义给定 目标主题。另外，新兴学科的词典如何建立，以及传统学科的主题词典建立以后， 主题词典以什么规则进行扩充，这一问题需要仔细研究，因为它关系到主题搜索引 擎能否更好地符合和满足用户需求。 2 ) 主题驱动的采集算法 与主题相关的网页是占i n t e m e t 中很少的一部分，主题驱动的信息采集应该更加有 效，爬行器应该直接采集与主题相关的网页而同时过滤掉那些与主题不相关的网页 这一点是至关重要的。这也是本论文研究的重点。 3 ) 主题信息采集系统的框架结构 良好地系统框架结构是主题信息采集系统实现的关键。 4 本文主要设计雨i 实现了一个基于元搜索引擎的主题信息采集系统，该信息采集系统中的 主题爬行算法，是改进的适合于中文特色的s h ( s i m p l e h e u r i s t i c s 简单启发) 算法，它利用 元搜索引擎的布询结果作为初始根集合，可根据州户提交的有限的关键词，根据u r l 利锚 文本链接中是否包含主题词进行相关性判定，只f 载那些与给定主题有关的网页。试验结果 显示，该主题搜索引擎的主题爬行算法良好，可以监督爬行器一直爬行下去，直到爬行出所 有的主题网页。 1 3 研究成果 本论文对主题信息采集系统涉及到的几个问题进行了研究和探讨，并设计和实现了一个 基于元搜索引擎的w e b 主题信息采集系统。本论文的研究有以下成果和意义： 提出一种自动地动态建立w e b 主题词典的方法，该方法不同之处在于，它提供了 一种有效的自动地从w e b 网站的链接结构中抽取出内容结构的方法，然后，基于 该内容结构建立相应的主题w e b 词典。建立的w e b 词典可以解决新兴学科词典的 建立问题以及传统学科的词典扩充问题。 改进了一个简单而且容易实现的主题爬行器算法s h ( 简单启发) 算法，该改进算 法充分利用了锚文本数据的主题特性，能够很好地适应中文特点。其思想也可以应 用于其它中文信息检索研究。 该主题信息采集系统在个人p c 机上就可以实现，不需要太多的资源可以完成基 于个人的主题信息采集，实现用户实时动态查询网上资源，同时，它也适合于当一 个用户预先不知道某网站结构，而想从该网站查找一些数据的情况。 总之，本系统提供了基于内容的智能化搜索，可以完成用户输入的任何主题的信息采集 工作，系统易于更新和维护，具有一定的现实意义。 1 4 论文的组织结构 第一章绪论，讨论了本文的研究背景、研究目标及研究成果。 第二章简单介绍了搜索引擎及主题搜索引擎的基础知识。 第三章讨论了主题信息采集系统面临的三个主要问题，并重点研究了基于元搜索引擎 的主题驱动的信息采集算法。 第四章给出了基于w e b 的主题信息采集系统原型系统的设计要点及其实现时的关键 技术。 第五章给出了本文提出的主题信息采集系统的结果及其分析评价。 第六章总结和未来工作展望。 5 第二章相关问题和技术 2 1 搜索引擎 2 1 1 搜索引擎的工作原理 搜索引擎是目前最常用的w e b 信息检索工具，很多用户依靠搜索引擎在w e b 上检索他 们需要的信息，大多数门户站点或商业站点都提供了搜索引擎；另外，w e b 上的专门搜索 引擎站点也非常多，著名的和常用的搜索引擎有：g o o g l e 、y a h o o ! 、a l t a v i s t a 、e x c i t e 、百 度等等。 搜索引擎的工作过程包括两部分： 1 ) 后端过程这个过程是收集w e b 上的一个个网页到数据库中，并为数据库中的网页 建立索引，根据索引就可以迅速找到含有指定词语的网页。这部分在搜索引擎中主要由爬行 器( c r a w l e r ) 、w e b 页面数据库和索引模块来完成( 图2 1 ) 。 2 ) 前端过程这个过程是实时进行的，在用户向系统提交查询时启动，它接受用户的 查询，将之解析成一个个词语，然后通过索引找到含有这些词语的网页，接着把这些网页按 照与查询的相关度排序，最后返回这些网页的列表。这部分工作主要由搜索引擎接口、排序 模块来完成。 l 前端垃程 i ； 查诲 图2 1 搜索引擎的工作原理 2 1 2 搜索引擎的分类 前面的1 1 2 节中已经论述了搜索引擎大致经历了三代1 2 4 1 的更新发展。 另外，根据信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三人类 1 ) 目录式搜索引擎( d i r e c t o r y ，也叫做c a t a l o g ) 6 以人i ：方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘婴，并将 信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏览服务和直接检索服务。 该类搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人r 介入、维 护量大、信息量少、信息更新不及时。这类搜索引擎的代表是：y a h o o 、o p e nd i r e c t o r y 等。 2 ) 机器人搜索引擎 由一个称为蜘蛛( s p i d e r 、w e bc r a w l e r 或w e bw a n d e r e r ) 的机器人群序( r o b o t ) 某种 策略自动地在访问w e b 站点提取站点上的网页，并根据网页中的链接迸一步提取其它网 页，或转移到其它站点上。r o b o t 搜集的网页被加入到搜索引擎的数据库中，供用户查询使 用。i n t e m e t 上最早出现的搜索引擎就是利用r o b o t 米建立数据库，“搜索引擎”这个词的原 义也只是指这种侠义上的基于r o b o t 的搜索引擎。 该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有 很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是：a l t a v i s t a 、n o r t h e r n l i g h t 、e x c i t e 、l n f o s e e k 、g o o g l e ；国内代表为：天网、悠游、百度等。 3 ) 元搜索引擎 也叫做m u l t i p l es e a r c he n g i n e ，这类搜索引擎的特点是没有存放网页的数据库，而是将 用户的查询请求同时向多个搜索引擎递交，将返回的结果经过处理后返回给用户。服务方式 为面向网页的全文检索。严格意义上来讲，元搜索引擎只能算是一种用户代理，而不是真正 的搜索引擎。 这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用所使用搜 索引擎的功能，用户需要傲更多的筛选。这类搜索引擎的代表是w e b c r a w l e r 、l n f o m a r k e t 等。 2 1 4 搜索引擎中的典型排序算法 1 h i t s 算法 首先给出权威( a u t h o r i t a t i v e ) w e b 页面的解释。假设要搜索某一给定主题的w e b 页 面，例如敦煌学方面的页面。这时我们希望得到与之相关的w e b 页面外，还希望所检索的 页面是高质量的，或针对该主题是权威的。 “但是搜索引擎如何能够自动找出权威的w e b 主题页面? ”有意思的是权威性 ( a u t h o r i t y ) 隐藏在w e b 页面链接中。w e b 不仅由页面组成，而且还包含了从一个页面指向 另一个页面的超链接。超链接包含了大量人类潜在的注释它有助于自动发现权威性的网页。 当一个w e b 的作者建立指向另一个页面的指针时，这可以看作是对另一个页面的认可。把 一个页面的来自不同作者的注释收集起来，就可以用来反映该页面的重要性，并可以很自然 地用于权威w e b 页面的发现。因此，大量的w e b 链接信息提供了丰富的关于w e b 内容相关 性、质量和结构方面的信息，这对主题w e b 的挖掘是可以利用的一个重要资源。 2 0 世纪7 0 年代，信息检索的研究者提出了使用杂志论文引用的情况研究论文质撬的方 法。然而与杂志引用率不同，w e b 链接结构具有特殊的特征。首先，不是每一个超链接 都代表对我们寻找的认可。有些链接是为了其他目的而创建的，如为了导航或为了付费广告。 总体上，若大部分超链接具有认可性质，就可以用于权威判断。其次，基于商业或竞争的考 7 虑，很少有w e b 页面会指向竞争领域的权威页面。例如，可f 1 可乐不会链接到其竞争对手 百事可乐的w e b 页面。第三，权威页面很少具有特别的描述。例如y a h o o 主页不会明确的 给出“w e b 搜索引擎”之类的自描述信息。 由于w e b 链接结构存在这些局限性，人们提出了另外一种重要的w e b 页面，称为h u b 。 一个h u b 是指一个或多个w e b 页面，它提供了指向权威页面的链接的集合。h u b 页面本身 可能并不突山，或者说可能没有几个链接指向它们。但是，h u b 页面却提供了指向就某个主 题而言最突出的站点链接。此类页面可以是主页上的推荐链接列表，例如一门课程主页上推 荐的参考文献站点。h u b 页面起到了隐含说明某权威主题页面的作用。通常，好的h u b 指向 许多好的权威页面；好的权威页面则指有许多好的h u b 所集体指向的页面。这种h u b 与权威 页面之间的相互作用，可用于权威页面的挖掘和高质量w e b 结构和资源的自动发现。 如何利用h u b 网页去找出权威网页昵? 算法h i t s ( h y p e f l i n ki n d u c e dt o p i cs e a r c h ) ，是 利用h u b 的搜索算法。h i t s 提供了一个基于网页间结构链接关系的权重机制，标记了两类 不同类型的网页：权威网页( a u t h o r i t i e s ) 和中心网页( h u b s ) ，其内容如下： 首先，h i t s m l 由检索词( 比如可以是敦煌学主题词) 得到初始结果集合，比如基于索 引的搜索引擎得到2 0 0 个页面。这些页面构成了根集合( r o o ts e t ) 。由于这些页面中的许多 页面是假定与搜索内容无关的，因此它们中包含指向权威网页的指针。所以，根集合进一步 扩展为基本集合( b a s es e t ) ，包含所有由根集合中页面所指向的页面，以及所有指向根集合 页的页面。同时可为基本集设定一个元素上限( 如1 0 0 0 ) 。 其次，权重传递阶段( w e i g h t - p r o p a g a t i o n ) ，这是一递归过程，用于决定权威网页的权 重和中心网页的权重值。值得一提的是，由于具有相同w e b 域( 即在u r l 中有相同的一级 域名) 的两个页面之间的链接，经常是起到导航的功能，因此对权威没有什么贡献，此类链 接可以从权重传播分析中去除。 我们向为基本集中的每一个页面赋予一个非负的权威权重和非负的中心权重h ，并 将所有的a 和h 值初始为同一常数。权重被规范处理，保证不变形，如所有权熏的平方和 为l 。a 。与h 。的计算公式如下： a ，= ( 口满足9 呻m h ，= a 。 ( q t 蔫足q - - p ) ( a ) ( b ) 等式( a ) 反映了如果一个页面由许多中心( h u b ) 网页所指，则其权威权重会相应增加( 即 权重增加为所有指向它的页面的现有中心网页权重之和) ，等式( 2 ) 反映了若一个页面指向 大最权威网页，则a p 也会相应增加( 即权重增加为该页面链接的所有页面的权威权重之和) 。 最后，h i t s 算法输出一缀既有较大a ，的页面，又具有较大h 。的页面。 虽然基于链接的算法可以带来良好地结果，但这种方法由于忽略文本内容，也遇到一些 困难。例如当h u b 页包含多个主题的内容时，h i t s 有时会发生偏差。这一问题可以按如下 的方法加以克服，即分别将等式( a ) 和( b ) 的值替换为相应权重的和，降低同一站点内多 链接的权熏，使用超链接元数据来调整( 例如a n c h o r 文本) 参与权威计算链接的权重。 虽然发掘权威网页的难度较大，但根据权威网页和中心网页互相促进的关系，可用递推 8 的方法循环计算出权威网页和中心网炙。它们的关系妇斟2 2 所示。对丁与敦煌学主题相关 的网页集合中的每一个网页，我们都给它们定义两个参数：a ( a u t h o r i t a t i v e ) 和h ( h u b ) 。 a 值越高表示网页的权威度越高，h 值越高袭示网页的中心度越高。 图2 2 权威网页和中心网页关系图 算法具体描述如下： 1 p 是一个网页的集合，e = 如，p ：】网页p 。有超链接指向p ：，p 。，p 2e _ p 2 对每一个p p ，h 0 ) j 口爿0 渤的h u b 值和权威值 3 对于所有的p p ，初始化h 0 ) 和0 ) 为1 4 w h i l e 向量h 和a 没有被聚合时： 5 一f o r 所有的p p ，爿( p ) = ( 一，却n ( p ) 6 一f o r 所有的p e p ，日0 ) = 咖虹一( p ) 7 一规则化h 和a 向量 8 权威网页：输出一组较高a ( p ) 值的网页 中心网页：输出一组较高h ( p ) 值的网页 缺点：h 1 t s 算法最主要的不足就是不考虑文本的语义l 崎容，单纯的考虑w e b 的结构，这点 对于寻找相关主题的权威页面和中心页面都是有很大限制的。 2 p a g e r a n k 算法 p a g e r a n k 是著名搜索引擎g o o g l e 引入的网页排序算法，它是不依赖于查询 ( q u e r y - i n d e p e n d e n t ) 的排序算法。以下简单介绍一下该算法： 1 ) p a g e r a n k 算法1 假设有页面t 1 ，t 2 ，t i ，0 c ，t n 指向网页a ，则要计算网页a 的网页级别p r ( a ) ， 其计算公式如下； p r ( a ) 2 ( 1 - d ) + d + ( p r ( t 1 ) c ( t 1 ) + p r ( t 2 ) c ( t 2 ) + p r ( t n ) c ( t n ) 、 其中： p r ( a ) ：页面a 的网页级别， p r ( t i ) ：页面t i 的网页级别，页面t i 链向页面a c ( t i ) ：页面t i 链出的链接数量， 9 d ：阻尼系数，取值在o l 之问。 由此可见，i ) 这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2 ) 页 面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值是不同的。如果 t i 页面中链出的链接越多，它对当前页面a 的贡献就越小。a 的链入页面越多，其网页级 别也越高；3 ) 阻尼系数的使用，减少了其它页面对当前页面a 的排序贡献。 2 ) 随机冲浪模型 l a w r e n c ep a g e 和s e r g e yb r i n 提出了用户行为的随机冲浪模型来解释上述算法。他 们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概 率，完全由页面上链接数量的多少决定，这也是上面p r ( t i ) c ( t i ) 的原因。一个页面通过 随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼系数d 的引 入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d 可以视为用 户无限点击下去的概率，( 1 - - d ) 则就是页面本身所具有的网页级别。 3 ) p a g e r a n k 算法2 ( 对算法1 的修订) p r ( a ) = ( 1 一d ) ，n + d ( p r ( t 1 ) i c ( t i ) + + p r ( t n ) c ( t n ) ) 其中n 是互联网上所有网页的数量 由此，所有页面的网页级别形成的一个概率分布所有页面的网页级别之和是l 。在算 法l 中，随机冲浪访问某个页面的概率由互联网的总页数决定，在算法2 中，网页级别是一 个页面被随机访问的期望值。 4 ) g o o g l e 的迭代计算p a g e r a n k g o o g l e 采用一种近似的迭代的方法计算网页的网页级别的，也就是先给每个网页一个 初始值然后利用上面的公式，循环进行有限次运算得到近似的网页级剐。根据l a w r e n c e p a g e 和s e r g e yb r i n 公开发表的文章，他们实际需要进行1 0 0 次迭代才能得到整个互联网 的满意的网页级别值。在迭代的过程中，每个网页的网页级别的和是收敛于整个网络的页面 数的。所以，每个页面的平均网页级别是1 ，实际上的值在( 1 - - d ) 和( d n 吖1 司) ) 之间。 5 ) g o o g l e 搜索引擎的网页级别的实现 有三个因素决定的网页的等级：网页特定性因素、入链锚文本、网页级别。网页特定性 因素包括网页的内容、标题及u r l 等。为提供检索结果，g o o g l e 根据网页特定性因素和入 链锚文本计算出网页的l r 值，这个值被检索请求中的各个检索项在页面中的位置和重要性 加权，以决定网页和检索请求的相关性。l r 值和网页级别联合标志网页的基本重要程度， 这两个值的联合方式有多种，但一般是不能相加的。 对非特定的单个词的检索请求，网页的级别是决定性因素，而对于由多个检索词构成的 检索请求，内容相关性的分级标准影响更大。 2 2 主题搜索引擎第四代搜索引擎 2 2 1 主题搜索引擎中的主要技术 主题搜索引擎是为用户提供某个主题或某个域( d o m a i n ) 的w e b 网页资源的检索服务， 它提供的资源都是与某个主题相关的，服务上更具有专业特色，有一定程度的个性化。由于 主题搜索引擎运用了人工分类、专业领域知识等智能化策略，因此它比前三代搜索引擎将更 加有效和准