（计算机科学与技术专业论文）web信息搜索技术的研究.pdf

摘要 随着万维网的发展，w 曲上的信息资源正在以前所未有的速度增长。面对海量 的数据，用户常常无法从中找到自己所需要的数据。如何使用户能够在网络中快 速，准确的找到所需要的数据是w 曲信息检索面临的挑战。 搜索引擎技术的出现，为用户提供了一种在w 曲中检索信息的简单的方法，使 用户能够通过关键字进行相关资源的搜索。但是用户所需的资源种类不同，通用 搜索引擎难以提供给用户足够的资源，因此出现了针对特定领域的搜索服务。r s s 新闻搜索就是这类应用，它仅仅搜索r s s 新闻资源。同时，越来越多的网络应用采 用了b s 模式，因此出现了许多集成在浏览器上的搜索服务，并提供其他方便用户 的附加功能。 本文首先介绍了信息检索技术的基本概念和模型，介绍了搜索引擎和元搜索 引擎的基本结构；对基于链接分析的搜索引擎排序算法p a 积r a n l 【和h r r s 进行了分 析和对比，在此基础上提出了基于概念的权重p a g c r a n l 【改进算法以及为页面标记 概念的两种方法；提出了基于用户反馈的结果融合排名算法；详细介绍了r s s 新闻 搜索平台的结构，数据库模式设计，搜索操作的性能优化方法，主客观结合的新 闻排名机制；最后介绍了一种浏览器插件，它主要提供一种为页面进行概念标记 的方法，同时提供元搜索接口等其他服务。 关键词：w e b 信息检索，p a g e r a n k ，r s s 新闻搜索，排名，浏览器插件 a b s t r a c t w i t hm ed e v e l o p m 饥to f w o r l dw i d ew c b ，t l l e 锄。吼to f d a t a w e b 唧锄d s d r 砌t i c a l l y f a c i n g m 觚yd a t a0 i l w c b ，t h eu s e r sa l w a y s l o t l l e i r w a y t o 伽曲峙 印c c m cd a t a ni sa 曲吼l l e r 培ei nw c b i n f o m l a t i o nr e m e v a lt om a | t h el l s 盯f i n dt l l ed a t a 瓤埘1 r a t e l y 孤dq u i c k l y s e a r c h 王抽西n ep r o v i d e sas i m p l em e m o dt of h l dw 卸a g e u s e r sc a n 五l l dt h e w 却a g eb yt e l l i l l gl l l es e a r c hb n g i i l et l l ek c ”，0 r d u s e 墙a l w a y sd 锄锄dd i f r 盯e n t t y p 韶o fr e s o u r c e s ，b u tg e f a ls e a r c he n g i i 圮c a l l i l o tp r o v i d e 娜伍c i e n tf e u r c cf o r u s e 墙s o m es p e c i f i cs e a r c hs e n ，i c e 锄e r g e s f o re x a m p l e ，r s ss e a r c hs 盱“c e sa i mi s t oo n i y a r c ht h er s sn e w sr e s o u r c 铭s p c c i 氏“i y m o r ea n dm o w e ba p p l i c a t i o i l s u b r o w s e r s e r v e ra r c h i t c c t l l r c ，m a tm 锄yt o o l s 即1 b e d d e di nb r o w s e r sh 勰b e c n i n l p l 锄e m c d t h e s et 0 0 1 sa l w a y sp r o v i d e 柚i n t e g r a t e ds e 疵hs e r 、r i c e 强d 础c r f h n c d o nc o n v e n i e n tf b ru s e 鹋 n ep 印e r 百v 髂锄o v e 州e wo fb 邪i cc o n c 印协舳dm o d u l e so f 蛐m m t i o n r 曲曲v 地a i i dm ea r c l l i t c c t u r eo fs e 卸c he n g m ea n dm 啦s e 缸c he i 晒m c o n l p a r c st h e p a g e r a i l l 【锄dh i t sa 1 9 0 r i t l m ，驵dt l l p r o p o s e saw e i 出e dp a g e r a n ka l g 嘣t l l m b 够c d c c e p t s ，锄d t om 毗岣d so f t a g g i n gc o n c q p t sf b rw 曲p a g e p i o p o s e sa 僦l t m c r g er a n 虹n gm 弛o db 勰c do n 嵋c r s f b e d b a c k t 1 l ep 印e rd e s c d b e st l l ea r c l l i t e 咖o f 廿 r s ss e a 础p l a t f o 肋i nd e t a i l ，i n c l u d i n g 地s c h 锄蠲o fn 圮d a t a b a ，t h e o p 血i l i 髓矗o no f 缸c ho p e r a t i o l l ，a n dm e 瑚心n gm e c h a l l i s mo fr s sn e w s a ti a s t ， d e s c r i b 髂at o o l b 盯锄b e d d e di nab r o w s e r ，w i l i c h 删d e sam e t h o do f 嘲n g c o n c e d t sa n dm e l as a hs e r v i c e s k e yw o r d s ：w 曲h l f o n n a t i o nr e 缸c v a l ，p a g e r a l l l 【，r s sn e w ss e a r c l l ，砘“d l l g t b o l se r n b c d d e d 证b r o w s e r n 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文_ _ l = 作的知识产权单位属于西北工业大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位 论文研究课题再撰写的文章一律注明作者单位为西北工业大学。 保密论文待解密后适用本声明。 文， 经注 开发 的成 明。 学位论文作者签名 钟 指导教师签名 嗍年；月二? 日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位论 是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已 明引用的内容和致谢的地方外，本论文不包含任何其他个人或集体已经公 表或撰写过的研究成果，不包含本人或他人已申请学位或其它用途使用过 果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：生盘丛乌 卅年3 月带7 监塑 西北t 业大学硕士学位论文第一章绪论 1 1 研究的背景和意义 第一章绪论 万维网从诞生到现在不过二十余年，但它给人们的生活带来了巨大的影响。 随着网络应用的快速发展，w w w ( w o 订dw i d cw e b ) 已经成为许多行业信息发布、 交流的主要平台。w e b 上可以利用的文本数据总量就有千兆字节，另外还存在着大 量的图像、音频、视频等多媒体资源。一方面w w w 包含了从技术资料，商业信息 到新闻快讯，体育娱乐咨询等多种类别和形式的信息；而另一方面，由于网络的 动态性，资源分布分散，没有统一的数据管理形式，使用户很难在w w w 上找到自 己所需要的信息。这一矛盾从w 西诞生就存在，但是直到现在也没有得到根本的解 决。w c b 信息检索技术能够高效、准确的从w c b 数据中查找用户需要的信息、并以 有效的形式呈现给用户。w c b 信息检索技术不仅有很强的实用性，有很大的现实意 义，而且作为w e b 数据管理的一部分，在学术界也受到广泛关注【6 ”。 1 2 国内外的研究现状 传统的信息检索技术源于图书馆，它对信息项进行表示、存储、组织和存取。 信息检索技术首先要对系统进行建模，常用的模型包括布尔模型，向量模型和概 率模型。在模型基础上进行文档的标引，查询和文档的定义，并给出针对查询的 相似度计算公式，最后通过用户界面返回给用户。 搜索引擎是早期出现的w c b 信息检索方法。它的出现在一定程度上缓解了从巨 大的w w w 的资源中查找信息的难度。搜索引擎已经成为普通用户在网络上获取信 息的主要方法，用户输入关键字，通过搜索引擎获取一组包含该搜索关键字的相 关页面。搜索引擎本身通过网页采集程序收集大量网页并且建立索引，当用户查 询到来时通过查找索引并返回相关页面。搜索引擎一般分为集中式和分布式两种。 当前最成功的搜索引擎代表是g o o g l e 。 网络目录也是常用的一种w e b 信息检索工具。目录是各种知识的等级分类。用 户可以通过逐层的目录浏览，查找自己感兴趣的页面。w e b 目录通常包括政治，经 济，教育等大的类别，一级分类在1 2 到2 6 个之间，每个目录下还有更细的分类。 西北工业大学硕十学位论文第一章绪论 网络目录的代表是y a h o o ! 。大多数搜索引擎现在也提供主题目录，如a q l e x c i l e 等，但是这些都是针对某些特定领域的，如有的站点关注于商业，新闻或政治。 网络目录和搜索引擎是最早出现的两种通用的w c b 信息检索方法。 元搜索引擎是建立在独立搜索引擎之上的搜索引擎。这类搜索引擎自身不维 护数据，而是将用户请求发送到若干独立搜索引擎，取回这些独立搜索引擎的搜 索结果并进行结果融合并显示给用户。这类搜索引擎的代表有m e t a c m w l s a v v y s e a r c h 和h l q u i m s 。 由于网络资源包括的资源过于丰富，出现了针对特定领域的搜索平台。比如 针对学术论文的c i t e s e e r ；针对网络上大量的r s s 新闻，b l o g 页面，越来越多的网 络应用提供了r s s 新闻搜索，比如d i g g 。这些网络应用和通用的搜索引擎、网络目 录的最大区别是只关注一类w e b 资源，而不是广泛的搜取网络上的所有资源，例如 r s s 新闻搜索只关注r s s 新闻种子资源，百度m p 3 搜索只关注文件格式为m p 3 ，w m v 等的音频资源。 1 3 研究工作概述 w c b 信息检索技术包含的研究方向较多，本身面临着许多挑战，目前没有一个 高效统一的模型用于w e b 信息检索。作为成功的第一代w c b 信息检索模型的代表搜 索引擎技术也正融入越来越多新思想与新技术。数据挖掘，人工智能，机器学习， 自然语言分析，社会学等学科的技术都融入到w e b 信息检索领域。 笔者于2 0 0 5 年参加中美合作“下一代智能搜索平台”项目的研发，先后参加 了“d i g g o l 个人信息挖掘助手”和“w i z a g 智能r s s 新闻聚合搜索平台”的研发。 主要完成了搜索平台的总体结构设计，数据库模式设计，搜索排名算法设计与实 现，搜索性能优化以及嵌入浏览器的用户界面开发等工作。结合项目经验，提出 了基于概念的权重p a g c 胁k 改进算法，基于用户反馈的元搜索引擎模型及结果归 并方法。 1 4 本文组织结构 本论文是按照作者承担的主要研究和开发工作来安排的，共分为六章，每一 章的主要内容如下所示： 第一章绪论。本章简要介绍了本文的研究背景和意义、研究工作内容以及论文内 容的安排。 第二章w e b 信息检索技术概述。本章介绍了传统信息检索方法，经典信息检索模 2 西北工业大学硕十学位论文第一章绪论 型，信息检索的评价标准：介绍了w e b 信息检索技术的基本概念，分析了 w e b 数据的特点，对搜索引擎和元搜索引擎进行了简要介绍。 第三章搜索排序算法研究。首先研究了基于链接分析的搜索引擎排序算法 p a g e r a n k 和h i t s ( h y p e r t e x t i n d u c e dt o p i cs e a r c h ) ；然后提出了两种 提取概念的方法，并在此基础上设计了基于概念的权值p a g e r a n k 改进算 法；最后提出基于用户反馈的元搜索模型，在此模型基础上设计了结果归 并算法。 第四章r s s 新闻搜索平台的设计与实现。详细介绍了r s s 新闻搜索平台的构架， 数据库设计，搜索性能优化方法和分布式数据库部署策略。介绍了新闻文 章的主客观因子结合的综合排名算法的设计与实现。 第五章嵌入浏览器的搜索集成工具的设计与实现。介绍了一种嵌入浏览器的用户 界面设计与实现方法。 第六章结束语。本章总结了全文的主要工作，并展望了后续的研究工作，指出了 进一步的研究内容。 西北工业大学硕士学位论文第二章w 曲信息检索技术概述 第二章w e b 信息检索技术概述 2 1 传统信息检索方法 信息检索( i n f o r m a t i o nr e t r i e v a l ) 是对信息项进行表示，存储，组织和存取 “1 。信息检索的主要目标就是检索出所有与用户查询相关的文献。在传统的信息检 索系统中，通常采用标引词来编制索引和检索文献。标引词就是关键词或一组相 关词，其自身有一定的意义。标引词更为一般的形式是一篇文献中出现的任何词， 这样构成全文检索系统。信息检索的核心问题就是预测哪些文献相关，哪些文献 不相关。通常取决与采用的排序算法，处在排列最顶端的文献被认为是最可能相 关。本节首先形式化的定义信息检索模型，然后介绍两种常见的检索方式和三种 经典信息检索模型，最后介绍了信息检索的过程。 2 1 1 信息检索的形式定义 信息检索模型是一个四元组 ，其中 ( 1 ) d 是文献集中的一组文献逻辑视图，称为文献的表示； ( 2 ) q 是一组用户信息需求的逻辑视图，称为查询； ( 3 ) f 是一种机制，由于构建文献表示、查询及他们之间关系的模型； ( 4 ) r ( q 。d j ) 是排序函数，该函数输出一个与查询q 。q 和文献表示d j d 有关 的实数，这样就在文献之间根据查询q i 定义了一个顺序。 2 1 2 特别检索和过滤 特别检索和过滤是传统信息检索中的主要两种应用方式“1 。特别检索类似于图 书馆里的图书检索，图书馆的书库中的藏书一般情况下是固定的( 一般仅在新学 期会购入新书) ，不同学生到图书馆中查找自己所需要的书籍。由此可见，特别检 索的特点在于集合中的文献保持相对静止的状态，而用户的查询则是变化的。搜 索引擎也属于这种类型的检索。 过滤又称为路由选择，其特点和特别检索相反，它的特点在于用户的查询规 4 西北工业大学硕十学付论文第二章w 曲信息检索技术概述 则相对稳定，而文献集合是经常变化的。例如一些股票市场和新闻服务，用户定 制一些查询，在不同时间返回不同的数据。过滤的难处在于构建一个真正反映用 户优先选择的用户需求档。例如在第四章中详细介绍的r s s 新闻搜索平台中，提供 按种子类别进行过滤的功能，而用户需求档就是种子的名字。 2 1 3 经典信息检索模型 信息检索的三个经典模型分别为：布尔模型，向量模型和概率模型。 布尔模型：布尔模型是基于集合理论和布尔代数的一种简单的检索模型。在 布尔模型中，文献和查询用标引词集合来表示，又被称为集合论模型。布尔模型 假定标引词在文献中要么出现、要么不出现，因此标引词权值变量都是二值的， 即w 。 o ，1 。查询被表示成有确切语义的布尔表达式，通常是由若干个标引 词通过联结词n o t ，a n d ，o r 连接起来的。查询本质上是一个常规的布尔表达式， 它可以表示为多个合取向量的析取，即析取范式d n f ( d i s j u n c t i v en 0 r 舱1f o 珊) ， 记为q 州表示的任意合取分量。文献d ，和查询q 的相似度定义为： ，、f 1 如果j g 。c l ( q 。q 抛) ( v 露f ，g f ( d j ) = g f ( q c c ) ) s 2 叭d ，g ) = t 0 其它 如果s i m ( d ，q ) = l ，则布尔模型表示文献d j 与查询q 相关，否则文献与查询不相关。 但是，布尔模型只能判断文献是否相关，而无法判断部分匹配的情况。 向量模型：在向量模型脚中，文献和查询用t 维空间的向量来表示，称该模型 为代数模型。通过给查询和文献中的标引词分配非二值权值，实现部分匹配。这 些权值被用于计算文献和用户查询之间的相似度。向量模型通过对检出文献相似 度降序排列的方式来实现文献与查询的部分匹配。在向量模型中，元组( k 。，d j ) 的 权值w “是一个正的非二值数。此外，查询中的标引词也要加权。用w 。表示二元组 k i ，q 的权值，- t ，。 = o ，查询向量q 表示为q = ( w 耽。，w 。q ) ，其中t 是系 统中标引词的数日。文献d 。的向量可以表示为d j = ( w 。，w 。) 。矢量模型 通过矢量d ，和q 之间的形似性来评价文献d ，和查询q 的相似度。一般使用两个向量的 余弦值来计算相似度，即 s 拥( “g ) - 尚= 5 w w 细 两北t 业大学硕士学何论文第二章w 曲信息检索技术概述 概率模型：概率模型”1 试图通过概率方法处理信息检索问题。给定一个用户查 询q 和文档集中的一个文档d j ，概率模型试图估计用户找到其感兴趣的文档d j 的概 率，模型假设这个相关概率只是依赖于查询和文档的表示。概率模型假设在文档 集中存在一个子集，它是查询q 的结果集。理想结果集记为r ，它使得总体的相关 概率最大。集合r 中的文档被认为是于查询相关的，不在集合r 中的文档则被认为 是不相关的。在概率模型中，标引词的权值是二值的，即w 。 o ，l ，w 。 o ，1 ) 。 查询q 是标引词的一个子集。设r 是已知的相关文档集，设、r 是r 的补集，p ( 刚w ，) 是文档d ，与查询q 相关的概率，p ( 1 r1 w ，) 是文档d ，与查询q 不相关的概率。文档也 与查询q 的相似度可以定义为： 只r l 形1 s 洲d 口、= 二二- 、r 爿础i 形) 、 j 在这些基本信息检索模型基础上，研究人员又提出了许多改进模型，例如在 基于集合论的模型上，提出了模糊集合论模型和扩展布尔模型；在代数模型基础 上，衍生了广义向量模型，潜语义标引模型和神经网络模型；在概率模型基础上， 区分出了推理网络模型和信任度网络模型。 2 1 4 检索的评价 常用的系统性能指标是时间和空间指标。在一个信息检索系统中，人们最关 注的指标是相应时间和所需空间。在这些基本的指标基础上，针对信息检索系统 的特点，还有两个重要的衡量标准就是查全率和查准率。 设信息查询实例为i ，i 对应的相关文献集合为r ，用表示该集合中的文献数 目。假定用给定的检索策略对信息查询i 进行处理，并生成一个文献结果集合a ，用 i a l 表示该集合中的文献数目。用| r a l 表示r 和a 的交集中的文献数量： 查全率是指检出的相关文献与相关文献( 集合r ) 总数的比值，即查全率为： r ：型 i r i 查准率是指检出的相关文献与检出文献( 集合a ) 总数的比值，即查准率为： p ：型 1 4 i 两北工业大学硕十学位论文第二章w 曲信息检索技术概述 2 1 5 检索过程 在检索过程开始之前，必须定义一个文本数据库。这通常由数据库管理器来 完成，它将要使用的文献，将要在该文本上执行的操作转换为文献的逻辑视图。 数据库管理器还要为数据库中的文本进行标引，对文本建立索引。在检索过程中 会用到不同的索引结构，最常见的一种索引就是倒排文档。 用户首先详细说明用户需求，随后对用户需求进行分析和转换，为用户需求 提供一个系统表达式，接着通过查询获得检出文献。在把文献发送给用户之前， 要根据相关度，对检出文献进行排序。随后用户检查经过排序后返回的文献集合， 查找有用的信息。在这过程中，用户可能会将反馈信息发送给系统，系统可以利 用用户所选择的文献改进查询的表达。而在这些过程中，一般都需要一个用户界 面，例如在w 曲浏览器中显示的一个w 曲搜索引擎页面。 2 2w 曲信息检索技术 w 曲应用的迅速发展和它的指数增长已广为人知，仅可利用的文本数据总量就 有千兆字节。w 曲可以看成一个非常大的，非结构化且无处不在的数据库。这就 需要有效的工具来管理，检索和从数据库中筛选信息。w 曲信息检索的基本形式 有三种，第一种是搜索引擎，它标引一部分网络文献作为一个全文数据库，例如 a l t a v i s t a ；第二种是w 曲目录，它按主题来对所选择的w 曲文献进行分类，例如 y 址o o ! ；第三种是利用超链接结构来检索网络i i 】。本节首先介绍w 曲数据的特点， 然后分别对搜索引擎和元搜索引擎技术进行了简单介绍。 2 2 1w 曲数据的特点 网络带来的w 曲数据有非常鲜明的特点，这些特点都加大了w 曲信息检索的 难度。数据的分布性：由于网络的本质特性，w 曲数据经常分布在许多计算机平 台上；不稳定数据的高比例，由于w 曲的动态性，新的计算机和数据容易添加或 删除。当域名或文件名发生改变或不存在时，还要处理悬空链接和重新定位的问 题：网络数据量的指数增长带来了大规模的数据；非结构化和冗余的数据，每个 h 聊l 页面都没有很好的结构，许多网络数据是重复的镜像，或者非常相似，据 统计约有3 0 的网页是重复的。如果考虑语义上的冗余则重复数据更多；数据的 质量不高，网络可以看出是一个新的出版媒体，然而在大多数情况下，许多内容 7 西北丁业大学硕十学位论文第二章w 曲信息检索技术概述 并没有经过编辑处理，甚至任何一个用户都可以在网络上添加内容( 比如现在流 行的个人网络日志b 1 0 9 ，电子布告板b b s ) ，因此网络上的数据可能是错误的，无 效的；异构数据大量出现在网络中，除了有多种媒体和由此产生的多种格式外， 还需要处理不同的语言，不同的字母表，而这其中可能非常庞大，例如中文，日 文等贬洲字母表。 2 2 2 搜索引擎概述 大多数搜索引擎采用了集中式的收集器索引器结构【4 1 ，其体系结构如图2 1 所示。收集器( 又常被称作蜘蛛s p i d e f ，爬虫w b 衄，机器人r o b o 协) 是一个程序， 它按某种策略( 如广度优先或深度优先) 遍历网络，发回新的或更新过的网页， 然后将这些发送回的数据存储在文档库中。实际上收集器并不是实际运行在异地 的机器上，而是在本地系统中运行，向异地的w 曲服务器发送请求并获取网页。 索引器分析收集器收集到的网页，将文档表示成便于检索的形式，并在文档上建 立索引，最后将生成的索引库保存在主服务器上。索引一般采用某种形式的倒排 索引，倒排索引的每一项包含一组指针，这些指针指向和这个索引项相关的网页。 当用户输入某个关键词进行搜索时，需要通过用户接口将查询发送到检索器，检 索器通过索引快速找到相关的文档，然后按某种算法排序计算这些文档的排序值， 最后将排序后的结果返回给用户。 图2 1 搜索引擎体系结构图 大多数搜索引擎使用布尔模型或向量模型及这些模型的扩展进行排序。除了 经典的词频逆文献率方法外，经常使用的还有布尔扩展、向量扩展和最大引用等 方法。新的排序算法使用到了超链接信息，这是w 曲和传统瓜数据库之间的最根 本区别之一。指向一个网页的超链接的数量能够用来测量该网页的流行程度和质 量。此外，被相同页面所引用的网页与网页之间的公共链接表明了这些页面之间 的关系。常见的例子有w 曲q l l 哪h r r s 和p a g e r 丑1 1 1 c 。将在第三章详细讨论h i t s 8 西北t 业大学硕士学位论文第二章w 曲信息检索技术概述 和p a g e r 她k 。当i j 有许多成功运行的搜索引擎，例如舢t a s t a ，e x c i t e ，i n f o s e e l 【， l ，y c o s ，g o o g l e ，百度和天网搜索。 2 2 3 元搜索引擎概述 元搜索引擎是把一个给定的查询发送到几个搜索引擎、w 曲目录及其他数据 库，并收集和统一结果的一种网络服务器【l 】。可以认为元搜索引擎是建立在独立搜 索引擎之上的搜索引擎。它利用下层的若干个独立搜索引擎提供的服务向上提供 统一的检索服务，本身不采集文档、维护索引。元搜索引擎首先按某种策略把用 户的查询发送给特定的几个独立搜索引擎，再将各独立搜索引擎所得结果按照某 种结果归并策略进行融合，排序，最终给出统一的查询结果。元搜索引擎综合多 个搜索引擎的结果，可以增加网络资源的覆盖率，提高搜索的查全率；同时，元 搜索引擎在进行结果归并时，依据某种归并策略，可以对独立搜索引擎的一次查 询结果进行二次集成和排序，提高搜索的查准率。 经典的元搜索引擎主要由三部分组成：请求提交代理、检索接口代理、结果 显示代理【5 】。请求提交代理负责选择调用哪些独立搜索引擎，检索时间限制，检索 返回结果数量限制等；检索接口代理将用户的检索请求按不同的格式发送到各个 独立搜索引擎；结果显示代理负责各个独立搜索引擎检索结果的去重，合并，显 示。当前也有许多成功运行的元搜索引擎，例如：m c t a c 饱w 1 v i 、，i s i m o ，b b m ， s a v v y s e a r c l l s e 砌。 2 2 4 w 曲挖掘技术 w 曲挖掘是从与w w w 相关的资源和行为中抽取感兴趣的、有用的模型和隐 含信息。一般地，w 曲挖掘可分为三类：w 曲内容挖掘，w 曲结构挖掘和w 曲使 用记录挖掘【6 】。w 曲挖掘技术能改善w 曲信息检索的质量，提供更多的应用类型， 而且w 曲挖掘技术也是当前数据管理领域的一个热点研究方向【7 1 。 w 曲内容挖掘：从文档内容或其描述中抽取知识的过程。其主要内容是对w 曲 页面文档内容及搜索引擎的查询结果进行总结，聚类，分类等。w 曲内容挖掘有 两种策略：直接挖掘文档的内容或在其他工具搜索的基础上进行改进。 w e b 结构挖掘：从w w w 的组织结构和链接关系中推导知识。由于文档之间 的互连，w w w 能够提供除文档内容之外的有用信息，利用这些信息，可以对页 面进行排序，发现重要的页面。第三章介绍的p a g e r 锄k 和h i t s 算法就是这一类 型w 曲挖掘的代表。 9 西北工业大学硕千学位论文第二章w 曲信息检索技术概述 w e b 使用记录挖掘：主要目标是从w e b 的访问记录中抽取感兴趣的模式。 w w w 中每个服务器都保留了访问日志，记录了关于用户访问和交互的信息，分 析这些数据可以帮助理解用户行为，从而改进站点的结构；或为用户提供个性化 的服务。在第四章中介绍的r s s 新闻搜索平台中采用的主观排名因子，就是这一 类型的应用。 2 3 小结 本章首先介绍了信息检索的形式化定义，对特别检索和过滤这两种不同的检 索方式进行了对比；介绍了布尔模型、向量模型和概率模型三种经典信息检索模 型；指出信息检索系统的基本评价标准是查全率和查准率；描述了一般的信息检 索系统中的信息检索过程；接着分析了w 曲数据的特点，介绍了搜索引擎和元搜 索引擎的体系结构和基本工作原理，最后介绍了w 曲挖掘技术。 1 0 西北丁业大学硕十学位论文第三章搜索排序算法研究 第三章搜索排序算法研究 3 1 基于链接分析的排序算法分析 一个超文本文档( 即网页) 内可能存在大量的超链接，每个超链接指向互联 网上的其他文档。因此，互联网上的文档问存在一个有规则的网络拓扑结构。对 互联网的组织结构和链接关系进行推导，可以得到互联网上某个文档的重要程度， 进而可以对这些文档进行排序。因此，当前主流的搜索引擎( 如g o 0 9 1 e ，百度) 都 采用了基于链接分析的排序算法。 目前基于链接结构分析的搜索引擎排序算法主要都来源于两种经典算法：一 种是斯坦福大学s e r g e yb r i n 和l a w r e n c ep a g e 提出的p a g e r a n k 算法，为了验 证该算法的性能，他们建立了g o 0 9 1 e 搜索引擎的原型，现在g o o g l e 已经发展成 全世界最知名，最强大的搜索引擎。另一种算法是康奈尔大学j o nk l e i n b e r g 提 出的h i t s 算法嘲。 本章首先简要描述这两种算法的基本思想，对各自的特点进行了分析比较， 然后针对p a g e r a n k 算法采用的平分页面自身p a g e r a n k 值的策略，提出了一种按 概念权重分配p a g e r a n k 值的改进算法。概念可以采用多种方法进行选取，文中给 出两种方法。 3 1 1p a g e 毗m k 算法 p a g e r a n k 算法是最经典的搜索引擎排序算法，它的基础是网络用户的随机访 问模型“。b r i n 和p a g e 在其论文中提出一种用户行为的模型：假设有一个随机的 网络冲浪者，任意给定一个网页，持续点击链接，最终厌倦并开始访问另一个随 机页面，这一模型被称为随机冲浪模型。这样，在随机冲浪模型中，一个随机的 网络冲浪者访问一个页面的可能性就是该网页的p a g e r a n k 值。 p a g e r a n k 算法的基本思想其实来源于传统的学术文献的引文分析方法，而 b r i n 和p a g e 把这一思想应用到了w e b 页面中。传统的文献分析方法为，一篇文献 的重要性可以通过其他文献对其引用的数量来衡量。如果文献a 被同学科的许多 文献所引用，则文献a 在该学科内应该是一篇有影响力的著作。同样，在w e b 环 西北工业大学硕+ 学何论文第三章搜索排序算法研究 境下，如果页面a 通过超级链接指向了页面b ，相当于页面a 引用了页面b ，即页 面a 给页面b 投了一票，页面a 需要把自己的一部分p a g e r a n k 值分给页面b ，图 3 一l 是一种网络拓朴结构下的p a g e r a n k 值分配示意图。最后，根据每个页面的 p a g e r a n k 值来判断页面的重要性，重要的页面会在搜索引擎的搜索结果中位于前 列。如果一个网页有许多网页都指向它，那么它可能获得很高的p a g e r a n k 值；如 果一个网页被一个本身p a g e r a n k 值很高的页面所指向，那么它同样可能具有很高 的p a g e r a n k 值。页面p a g e r a n k 值的计算公式为： p r ( a ) = ( 1 一d ) + d ( p r ( t 1 ) c ( t 1 ) + + p r ( t n ) c ( t n ) ) 假设页面t 1 t n 都有超链接指向页面a 。其中p r ( a ) 表示页面a 的p a g e r a n k 值；参数d 是一个衰减因子，根据不同情况可以设定d 在o 到1 之间，通常设定 为0 8 5 。c ( t ) 表示页面t 指向其他页面的链接个数。 在通常情况下，设定每个网页的初始p a g e r a n k 值为1 ，通过以上公式，递归 计算各网页的p a g e r a n k 值，直到网页的p a g e r a n k 值趋于稳定。由于其用户行为 模型假设用户访问网络是完全随机的，因此一个页面的p a g e r a n k 值被平分给了其 所指向的页面，由上述公式中的项p r ( t 1 ) c ( t 1 ) 可以明显的看出其平分策略。 3 1 2h i t s 算法 图3 1p a g e r a n k 值分配示意图 k 1 e i n b e r g 在其论文中提出了h i t s 算法，用来评定网页内容的重要性。h i t s 的重要性评价是针对用户查询的。该算法将网页分为两个类别，即权威页 西北_ 丁业大学硕十学位论文 第三章搜索排序算法研究 ( a u t h o r i t i e s ) 和中心页( h u b s ) 。权威页是表达某一主题的页面，对这一主题 它的价值很高，依赖于指向它的页面。中心页是指向多个权威页的页面，它把这 些权威页链接在一起，依赖于它所指向的页面。h i t s 算法为每个页面引入两个权 值，即a u t h o r i t y 权值和h u b 权值，通过一定的计算可得到针对某个检索提问的 最具价值的网页，即排名最高的权威页。 h i t s 算法首先通过传统的搜索引擎( 如a l t a v i s t a ) 选取一定数量的页面作 为根集，然后在根集的基础上进行扩展，把引用根集的页面和被根集引用的页面 都加入进来，生成基本集，再针对基本集中的超链接建立所要处理的子图。在这 个子图上，建立页面的a u t h o r i t i e s 和h u b s 的计算公式。设a ( p ) 表示页面p 的 a u t h o r i t i e s 值，h ( p ) 表示页面p 的h u b s 值，指向页面p 的集合为b ( p ) = q l ， q 2 ，q n ，页面p 指向的页面的集合为i ( p ) = q 1 ，q 2 ，q n ) 。则 a ( p ) = h ( q 1 ) + + h ( q n ) ：h ( p ) = a ( q 1 ) + + a ( q n ) ： 通过迭代计算，最终得到页面p 的a u t h o r i t i e s 值。h i t s 算法中的a u t h o r i t i e s 和h u b s 值是互相加强的。图3 2 是一种网络拓朴结构下的h i t s 值分配示意图。 却= l 】q l + 1 1 q 2 + b q 3h p 篁a f l 电1 1 2 + a 1 3 图3 - 2h i t s 值分配示意图 3 1 3p a g e r a n k 算法和 t s 算法的比较分析 虽然p a g e r a n k 算法和h i t s 算法都是基于超链接拓扑结构分析的搜索引擎排 序算法，但是两者还是有区别的： 西北丁业大学硕十学付论文第三章搜索排序算法研究 ( 1 ) p a g e r a n k 完全忽略网页内容，仅根据网络超链接的拓扑结构计算得到网 页的p a g e r a n k 值，是一种独立查询( q u e l y i n d e p e n d 锄t ) 的算法。而t s 的 a u 1 0 r i t i e s 值是相对于某个检索主题的，是一种依赖查询( q u e r y d 印e n d e n t ) 的算 法。 ( 2 ) p a g e r a n k 是基于对w 曲的整体分析，而h i t s 算法则是通过传统搜索引 擎查选结果构建的基本集上进行分析的，是w 曲的局部分析，容易造成“主题漂 移”现象。 ( 3 ) 虽然p a g e r a n k 处理的数据比h i t s 多，但是h i t s 首先需要抽取根集，并 扩充基本集，从客户端等待的时间上看，p a g c r 矗n k 需要的时间比m t s 短。 ( 4 ) 从权重的传播上看，p a g e r a n k 基于随机冲浪模型，可以认为网页的重要 性从一个砌1 0 r i t i e s 传到另一个a u t h o 商e s 。而在h i t s 的模型中，则是从h u b 页传 到a u n l o r i t i e s 页。 从目前的应用来看，p a g e r a n k 算法相对于h i t s 算法有一定的优势，g 0 0 9 l e 成 功的商业运作，就是很好的例证。虽然p a g e r a n k 算法已成功应用到g o o g l e 当中， 但是它并不考虑网页的具体内容，平分p a g e r a n k 值，不考虑各个链接重要性，这 是值得改进的。在下一节中，我们讨论一种权重p a g e r a n k 改进算法。 3 2 基于概念的权重p a g e r a l l l ( 改进算法 由于p a g e r a n k 采用的随机冲浪模型认为每个链接的重要程度是相同的，所以 采用了平分策略。实际上，不同的超链接的价值是不同的。假设a 页面有指向b 页面的超链接，则b 页面可能是和a 页面高度相关的一个页面，比如都是讨论同 一主题的页面：然而也可能b 页面和a 页面根本不相关，b 页面可能只是一个广告 页。这一点和传统的文献引文分析不同，文献引文经过严格的审查，可以保证引 文间的高度相关性，而在w e b 环境下，超链接的质量无法保证。 针对p a g e r a n k 所存在的上述问题，结合h i t s 算法的思想，提出了一种改进 算法，即根据网页问概念的关联比重及用户搜索的概念，按权重分配页面的 p a g e r a n k 值。 3 2 1 基于网页内容的概念选取方法 在该改进算法的实现中，首先要为每个网页确定若干个概念。概念的选取可 以有多种方法，如u d ol ( r u s c h w i t z 在其论文1 中总结了种方法：选择在以下标 签上下文中出现多于一次的关键字作为概念。这些标签包括：e t a 信息，文档的 1 4 两北t 业大学硕十学位论文第三章搜索排序算法研究 题目，文档的标题，超链接的文本，以及重点强调的部分( 如字体为粗体或斜体 的部分) 。这种方法主要的特点是基于页面源码分析，可以认为是一种客观的概念。 这种对b 页面源码分析提取概念的方法可以认为是传统的文本分析的一个 拓展，已经有许多种成熟的算法，特别是针对英文。这种算法的基本过程可以概 括为以下几个关键步骤： ( 1 ) 对文本进行切词。针对英文，空格是自然的分割符，由空格隔开的就是独 立的单词。仅仅依靠空格的分词是最基础的，通常情况下还需要有一个停用词表， 用来过滤那些对检索来说作用不大的单词，或没有实际意义的单词。最后，需要 进行词干提取，因为英文中不但有比较级的变化，例如比较级，最高级；还有时 态、单复数的变化，例如：w o d d n g ，w o r k s ，w o r k e d 对应同一个词干w o r k ，目前最 常用的词干提取算法是p o r t e rs t 锄 1 2 】。针对中文，切词本身就是一项复杂的问题， 因为中文没有天然的分割符，容易出现切词的二义性及歧义，中文切词具体方法 可以参考相关文献。 ( 2 ) 构造一个语义字典。语义字典对于文本切词来说是有指导意义的，它规定 了每个词的不同重要级别。比如，名词，实意动词表达的概念要比虚词，冠词， 语气词表达一个文档的实际内容多。同时，通过语义词典，还可以进行层次概念 抽取，同义近义词的合并与提取。当前已经有较多的成熟语义词典，针对英文有 p r i n c e t o n 大学研发的w 砌n e t ，针对中文有北京大学研发的现代汉语语料库和语义 信息词典。借助这些语义字典，可以更好的完成文本的切词以及概念的提取。 ( 3 ) 超文本文档的分析。超文本文档中不同标记内的文本提供给更多的附加信 息，比如在标题标签内的文本，粗体、黑体标签内的文本，超链接中的文本的权 重要加大。 3 2 2 基于f 0 1 1 【s o n o n l y 的概念选取方法 上一小节中提到的概念选取方法是一种客观的选取算法。w e b 环境下的文本标 记的一个特点就是用户的参与，可以让用户对文档添加概念进行标记，即社会性。 f 0 1 k s o n o m y 分类法就是民间社会分类法。这个概念起源于社会性书签服务中最具 特色的自定义标签功能。f o l k s o n o m y 分类标引可以由三类角色完成，分别为专家， 信息发布者，以及普通用户m 。 专家对一个文档的概念标引常常出现在传统的信息检索领域。比如一个图书 馆管理员按照图书馆的分类体系，对一本书进行标引，分类，标记概念。这要求 图书馆管理员熟悉分类体系，需要经过严格的专业知识学习与训练。如果在w e b 西北工业大学硕士学何论文第三章搜索排序算法研究 环境下应用，则需要类似图书馆管理员的角色对w e b 文档进行分类和概念标记。 早期的y a h o o ! 网络目录采用的目录式检索就是采用这种方法，它通过人力把w e b 页面归为若干大类，每一类低下又有若干子类。但是随着w e b 文档的海量增长， 仅靠专家人力地标记w e b 文档的可行性不大。因此，这种方法在w e b 环境下显然 是不适用的。 信息发布者对一个文档的标引在学术论文中很常见，通常作者会从论文中选 出规范的、用以表示全文主题内容信息的单词或术语作为这篇论文的关键字列在 论文中。比如，文献 8 的关键字为：”w o r l dw i d ew e b ”，”s e a r c h e n g i n e ”， ”i n f o r m a t i o nr e t r i e v a l ”， ”p a g e r a n k ”，”g o 0 9 1 e ”。这些关 键字就可以作为文献 8 的概念。在w e b 环境下，作者同样可以把关键字发表在文 档中，一种可行的方法就是写在m e t a 标签中，例如 c o n c e p t l ，c o n c e p t