（信号与信息处理专业论文）搜索引擎改进问题的研究.pdf

摘要 互联网的出现带来了网络信息高速发展的时期，同时也造成了信息的海量 增长，互联网搜索引擎成为人们一项必不可少的工具。搜索引擎是网络信息检 索最常见的工具，他涉及卸多方面的内容，包括信息检索数据挖掘，分布式处 理，自然语言处理，因此具有很大的挑战性。随着信息的激增，查找精确信息变 得越来越困难。如何改进现有的搜索引擎和系统，满足用户日益增长的信息需 求，成为当今信息检索课题的一个重要方向。 本文将按照如下方式进行组织：第一章提出选题的意义，背景和本文的工 作，着重研究了互联网的信息特征和目前搜索引擎的不足之处第二章对搜索 引擎做一个简要的综述，介绍互联网的发展和搜索引擎产生的必然联系，阐述 了搜索引擎的发展历史和各个历史条件下具有代表性的搜索引擎的特征，搜索 引擎的分类和模块组成。第三章介绍搜索引擎的改进分析，提出搜索引擎改进 所用到的数据挖掘，个性化，自动聚类等方法并阐述了个性化搜索的基本模型。 第四章，提出了改进搜索引擎的排序算法。第五章，介绍实现的搜索引擎系统 平台。第六章，总结所做的工作，并对搜索引擎的发展做了展望。 本课题深入搜索引擎的原理，发展历史，目前发展现状和存在缺陷，厕时对 现有搜索引擎提出了若干改进： 对数据挖掘和个性化搜索进行了研究，井提出一种基于个性化的搜索模 型。 在继承经典p a g e r a n k 算法框架下，对p a g e r a n k 算法做了修正，提出了一种 改进的p a g e r a n k 排序算法i p r ( i m p m v e dp a g e r a n k ) 。 合理利用社区发现和推荐信息，提出一一种社区推荐技术的排序算 法c r r ( c o m m u n i t ya n dr e c o m m e n d a t i o nr a n k ) 。 实现了一个搜索 j 擎系统i m p r o v e d s e a r c h 关键词：信息捡索，搜索引肇，数据挖掘，个性化搜索，社区发现，信息推荐 网页摊序 a b s t r a c t i n t e m e tb r i n g san e ws p e e d i n gi n f o r m a t i o na g e 。a tt h es a m et i m e i n f o r m a t i o n i l t e r e a s e se v e r 3 , s e c o n di na l lu n e o n t r o t t a b i ew a y w 蛐hm a k e ss e ( s e a r c he n g i n e ) a d a i l y n e e d e dt 0 0 1 s e a r c he n g i n ei so n eo fm o s tc o m m o nt o o l si nw e bi n f o l m a d o n r e t r i e v a l w h i c hi n c l u d e sm a n yf i e l d ss u c h 矗si n f o r m a t i o nr e t r i e v a l 。d a t am i n i n g 。d i s t r i b u t i n gp r o c e s s n a t u r el a n g u a g ep r o c e s s i n ga n ds oo n s oi tg i v e sp e o p l es o m ec h a l l e n g e s h o w e v e r , a st h ei n f o r m a t i o nc o n t i n u e si n c r e a s i n g ，f i n d i n gap i e c eo fn e e d e d i n f o r m a t i o nb e c o m e sn l o r ed i f h c u l h o wt oi m p r o v es e a r c he n g i n es y s t e ma n dm e e t t h en e e d so fu s e r si so n eo ft h em o s tf o c u s e dw a y si nl r ( i n f o r m a f i o nr e t r i e v a l ) t e s e a r c h t h i sa r t i c l ei so f g a n i z e da sf o l l o w s ：t h ef i r s tc h a p t e re l a b o r a t e st h em e a n i n go f o n tr e s e a r c h ，b a c k g r o u n d sa n dm a i nj o b ，t h i sp np a y sal o to fi m p o r t a n c eo nt h e f e a t u r e s o f i n t e r n e ta t t d t h e d e f e c t s o f s e t h es e c o n d p a r t m a k e s ab r i e f s u r v e ya b o u t s e ，i n c l u d i n gs eh i s t o r y , t h ed i f f e r e n tt y p e so fs e ，a n dt h eb a s i cp r i n e i p l e so fs e t o et h i r dc h a p t e ra n a l y s e st h es t r a t e g i e s “i m p r o v e m e n ta b o u ts ei n c l u d i n gd a t a m i n i n g ，p e r s o n a l i z e ，f l u t o c l u s t e r i n g t h ef o u r t hp a r tb r i n g su ps o m ei m p r o v e m e n t si n s er e s e a r c h t h ef i f t hc h a p t e ri n t r o d u c e so u rs es y s t e mp l a t f o r m t h el a s tp a r ti sa c o n c l u s i o n o f o u r i ：e s e a r c ha n d m a b s o n i c f o f e c a s t a b o u t f u t u f er e s e a r c h t h i o u g h c l o s es t u d i e s o f t i r h i s t o r y ，s e p r i n c i p l e s s e p r o b l e m s a n d d e f e c t s ，o u r r e s e a r c hb r i n g sn ps o m ei m p r o v e m e n t sf o rs e ： h a sac l o s er e s e a r c ho nd a t am i n i n ga n dp e r s o n a lr e s e a r c h ，a n db r i n g su pa p e r s o n a l i z e ds e a r c hm o d a l b r i n g su pa ni m p r o v e dp a g e r a n k ( i p r ) a l g o r i t h mu n d e r c l a s s i cp a g e r a n ka l g o r i t h mf r a m e w o r k b r i n g su pac o m m u n i t ya n dr e c o m m e n d a t i o nr a n k ( c r r ) a l g o r i t h mb yp r o p e r l yu s i n gc o m m u n i t yd i s c o v e r ya n dr e c o m m e n d a t i o ni n f o r m a t i o n i m p l e m e n t sas es y s t e mn a m e di n l p r o v e d s e a r c h 一垒璺! ! ! ! 塑 k e y w o r d s ：i n f o r m a t i o nr e t r i e v a l ，s e a r c he n g i n e ，d a t am i n i n g ，p e r s o n a l i z e ds e a r c h ， c o m m u n i t yd i s c o v e r y , i n f o r m a t i o nr e c o m m e n d a t i o n ，p a g er a n k i n g i v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅或借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：l 三2 型 川年月2 留日 第一章绪论 1 1 研究背景和意义 现在，互联网已经成为人们日常生活不可分离的部分，无论是工作，学习， 还是生活。随着互联网的发展，人们愈发需要它提供丰富的资讯信息。同时，随 着知识大爆炸时代和互联网信息的指数式递增，如何精确获得用户需要的数据， 已经成为人们共同关注的问题。如何找到更加符合用户意愿的信息，是搜索引 擎一直致力解决的问题 1 1 1 网络信息的特点 搜索引擎处理的数据对象直接来自于互联网，因此需要了解互联网信息的 特点互联网数据特点可归结为如下，它们给信息检索带来了一些难题川： 1 呈分布式存放，互联网通过不同的主机、站点互通信息，并且这种分布式 的存放呈网状分布。 2 互联网信息无组织性，目前不存在一个有效的方式，将互联网数据建立成 一个模型。 3 互联网信息的高冗余性，据统计3 0 以上的网页是重复的。 4 互联网信息的不稳定性，网上的信息容易更新和删除，统计表明，平均每 个月，都会有4 0 的网页发生改变，因此，出现空链接的几率和数据改变 的几率相当高。 5 数据的异构性，互联网数据形式多样，如多媒体文件：图像文件，音频文 件，视频文件等，另外就是文本文件，包括很常见的半结构化文档h t m l 文 件，x m l 文件。 6 大量垃圾信息充斥着互联网，许多虚假广告，不健康信息，错误信息。因 此，互联上存存1 ：少的虚假信息。 第一带绪沧 互联网信息的这种特点，给人们的信息检索带来一定程度的不便，搜索引擎就 是在这种条件下诞生的。搜索引擎的出现给信息检索带来了飞跃发展。但是由 于互联网不断发展的特点，不可能住一定条件f 解决全部的问题，因此。互联网 的发展造成了搜索引擎的长足发展。下面介绍的是现有搜索引擎的一些弊端。 1 1 2 搜索引擎存在的问题 搜索引擎在处理互联网数据时带来了积极作用，但现有搜索引擎给人们带 来了很多方便的同时，也逐渐暴露了自身的一些问题，用户对信息检索的要求 越来越商，也推动了搜索引擎的向前发展。随着海量信息涌入万维网，检索数据 依然会成为一个很大的问题，虽然许多搜索引擎已经成为用户不可或缺的信息 获驭手段，但精确的检索出想要的结果，也不再是件容易的事。用户常常为“相 关但不精确”的结果所干扰，r e s p e c t 调研资料表明2 0 0 6 年6 2 的用户只点击搜 索结果页第一页的结果，而高达9 0 的用户只点击搜索结果页的前三页里的结 果。而在2 0 0 2 年，这两个数字分别为4 8 及8 1 。这些变化说明了用户对搜索引 擎的要求越来越高，他们愿意花在寻找结果卜的时间越来越少。因此排序查找 到的结果比搜索本身更为重要，尤其是当检索结果过于庞大时。现有搜索引擎 的弊端如下： l i 网络信息量过于庞大，网络结构模型没有特定的规律可以描述。 2 检索工具多样，但没有统一标准可以依赖。 3 检索结果排序满意程度不够，检索结果信息过多，有用信息不全。 4 检索结果不够个性化，没有考虑不同用户的不同请求。 5 跨语言搜索有待发展完善 6 多媒体信息检索很不完善 7 索引数据库更新的速度严重滞后于网页的更新速度。 本课题结合了搜索引擎的原理和现状，在研究现有的搜索引擎的前提f ， 改薛了搜索引警的质量，对搜索引擎的发眨和改进，提出了自己的解决方式。无 论存科研，还是实际的应_ 蚌j 中，部仃很大的价值。 2 中国科学技术大学硕士学位论文 1 2 本文的主要工作 综合上而提出搜索引擎存在的若干问题，本课题深入研究，并做了如下工 作： 1 2 1 对搜索引擎做综述 本文详细介绍了互联网和搜索引擎的发展历史，搜索引擎在不同历史条件 下的舆型代表，并从客观的角度分析了搜索引擎的发展趋势。同时对搜索引擎 的各个组成部分做了细致的综述，从底层的网页抽取，网页预处理，索引入库， 到查询的实现，搜索引擎的语法表达，用户接口，排序显示等，做了充分的叙 述。 1 2 2 分析搜索引擎改进策略 对搜索引擎的改进方法一一数据挖掘做了介绍，在数据挖掘的基础上提出 了个性化搜索的概念，经研究得出结论，个性化的搜索引擎是未来搜索引擎的 一个重要发展方向，同时并提出了一种个性化的搜索引擎模型。对搜索引擎 的其它改进方式，如自动聚类方法，本文也做了简单介绍。 1 2 3 提出改进的p a g e r a n k 算法i p r 搜索引擎的排序问题一直是搜索引擎研究的热点，改进的p a g e r a n k 排序方 法，是基于p a g e r a i l k 算法”的而提出，他给p a g e r a n k 算法带来了很大的改进，同 时由于它的算法框架基于p a g e r a n k ，具有良好的可移植性，方便的在现有系统 中推广这个算法。具有较高价值的理论意义和应用价值。通过验证，发现i p r 算 法对排序的性能提高了将近一倍( 0 ，8 9 倍) 。 1 2 4 提出社区推荐技术的c r r 算法 基于社区推荐的排序( c o m m u n i t ya n dr e c o m m e n d a t i o nr a n k ) 算法，是本文 提出的另外一种排序算法，它恰到好处的应用到了容易被人们忽视的信息：即 网络的社会信息”，各种网页和网站中的分布其实是有某种规律的。这种规律 就是网络的社会化，即网页会破自发的组合，通过这种基于推荐的方法，能获 得排序质量大大的提高，c r r 算法和相同条件i - p a g e r a n k 算法相比，提高了四 倍( 4 0 2 倍) 。 3 第一章绪论 1 2 5 实现搜索引擎系统i m p r o v e d s e a r c h 在测试和验证本文涉及的观点和算法中，采用以开源软件l u c e n e 作为底 层a p i 的一个小型的搜索引擎系统，该系统实现了从网页抓取，文本处理，分词 技术，索弓l 入库，数据库操作，排序显示等搜索引擎所能做的全部工作。是一个 具体而微的搜索引擎系统。并且这个系统把相同条件下的改进算法和以前的算 法进行了详细的对比，做出了客观的结论。 1 3 论文的组织结构 本文的结构按如下的方式进行组织： 第一章，绪论，提出选题的意义，背景和本文的工作，着重研究了互联网的 信息特征和目前搜索引擎的不足之处。概括了本文将要研究的问题。 第二章，搜索引擎综述：介绍互联网的发展和搜索引擎产生的必然联系，阐 述了搜索引擎的发展历史和各个历史条件下具有代表性的搜索引擎的特征。搜 索引擎的分类和模块组成。 第三章，介绍搜索引擎的一些改进策略，如数据挖掘，在数据挖掘的基础上 提出个性化的搜索引擎，推荐技术。阐述了个性化搜索的基本模型。并对搜索 引擎的其它改进方式，如自动文本聚类，做了简要介绍。 第四章，提出了改进搜索引擎的排序算法：改进的p a g e r a n k 算法，另外提 出一种基f 推荐机制和社区发现机制的结果处理方法：基丁社区发现和信息推 荐的排序算法。 第五章，介绍实现的搜索引擎系统l m p r o v e s e a r c h ，和底层抓取器s p i d e r ，详 细描述了它的各个组成。 第六章，总结所做的工作，并对搜索引擎的发展做了展望。 第二章搜索引擎综述 2 1互联网的发展历史 互联网从诞生到现在也不过短短的二十多年，但却席卷了真个社会并渗透 到各个领域，了解搜索引擎的历史，需要先对互联网的历史有一个清晰的认识。 2 1 1诞生时期：a r 尸：a n e t 的出现 1 9 8 3 年，美国国防部高级研究计划管理局( a r p a ：a d v a n c e dr e s e a r c h p r o j e c t sa g e n c y ) 和美国国防部通信局研制成功了用于异构网络的t c p i p 协 议，美国加利福尼亚伯克莱分校把该协议作为其b s du n i x 的一部分，这一举措 使得t c m p 协议最终应用到实践上从而标志着真正的i n t e m e t 诞生，同时也是人 类从工业时代跨入到互联网时代。 2 1 2 逐步发展成形：n f s n e t 产生 过了三年，也就是1 9 8 6 年，美国国家科学基金会( n a t i o n a ls c i e n c ef o u n d a t i o n ，n s f ) 利用a r p a n e t 发展出来的t c p i p 的通讯坍议，在五个科研教育服务 超级电脑中心的基础上建立了n s f n e t 广域网。由于美国国家科学基金会的鼓励 和资助，很多大学、政府资助的研究机构甚至私营的研究机构纷纷把自己的局 域网并入n s f n e t 中，从此互联网在学校，研究所，军方项目中得到大量实施。同 时，a r p a 网的军用部分己脱离母网，建立自己的网络- m i l n e t 。a r p a n e t - 网络之 父，逐步被n s f n e t 所替代。到1 9 9 0 年，a r p a n e t 已退出了历史舞台。如今，n s f n e t 己成为i n t e m e t 的重要骨干网之一。 2 1 3 飞速发展：万维网时代 1 9 8 9 年，由c e r n 开发成功w w w ( w o r l dw i d ew e b ) ，为i n t e m e t 实现广域超 媒体信息截取，检索奠定了基础。到了9 0 年代初期。i n t e r n e t 事实上已成为一个“网 中网”：各个子网分别负责自己的架设和运作费用，而这些子网又通过n s f n e t 互 联起来。由于n s f n e t 是由政府出资，因此，当i j , i n t e r n e t 最大的老板还是美国政 府。只f i 过存一定程度上加入了些私人小老板。i n t e m e t 在8 0 年代的扩张1 i 草 第二章搜索引擎综述 带来量的改变，同时亦带来质的某些改变。由于多种学术团体、企业研究机构， 甚至个人用户的进入，i n t e m e t 的使用者不再限于电脑专业人员。新的使用者发 觉，加入i n t e r n e t 除了可共享n s f n e t 的巨型机外，还能进行相互间的通讯，而这 种相互间的通讯对他们来讲更有吸引力。于是他们逐步把i n t e r n e t 当作一种交 流与通信的工具，而不仅仅是共享n s f n e t 巨型机的运算能力。从上面的发展可 以看到，九十年代以前的网络，i n t e r n e t 的使用一直仅限于研究与学术领域。商 业性机构进入i n t e m e t 一直受到这样或那样的法规或传统问题的困扰。事实上， 象美国国家科学基金会等曾经出资建造i n t e r n e t 的政府机构对i n t e r n e t 上的商业活 动并不感兴趣。 2 1 4 成熟阶段和全盛时期 1 9 9 t 年，美国的三家公司分别经营着自己的c e r f n e t 、p s i n e t 及a l t e r n e t 网 络，可以在一定程度上向客户提供i n t e r n e t 联网服务。他们组成了“商用i n t e r n e t 协 会”( c i e a ) ，宣布用户可以把它们的 r t t e m e t 子网用于任何的商业用途。i n t e r n e t 商 业化服务提供商的出现，使工商企业终于可以堂堂正正地进入i n t e m e t 。商业 机构一踏入i n t e r n e t 这一陌生的世界就发现了它在通讯、资料检索、客户服务 等方面的巨大潜力。于是，其势一发不可收拾。世界各地无数的企业及个人纷 纷涌入i n t e m e t ，带来i n t e r n e t 发展史上一个新的飞跃。特别是，进入二十一世纪 以来互联网的发展更是一发不可收拾，网页数量成指数级增长，根据第5 届 搜索引擎年会的会议报告，截至2 0 0 0 年1 月，全球网页超过l o 亿，最新统计结 果表明：2 0 0 4 年全球搜索引擎市场规模达n 8 7 亿，2 0 0 6 年已经增长到2 0 4 亿。随 着w e b 2 ，o 思想的提出，互联嘲用户能充分享受到以用户为中心的全新体验，更 加愿意参与到互联网的世界中来，博客，网摘，用户社区，论坛等大量涌现，使 得网页数最的激增愈演愈烈。 互联网的蓬勃发展和网页数量的激增，带来了网络时代的欣欣向荣，同时 也带米了i 午多问题，其中一个备受人们关注的问题，就是信息过载和信息迷向。 信息过载，是指在信息高速发展的今天，人们的生活充斥了大量需要去了解的 知识和信息，尤其是在互联网这种现象会越来越明显，人们只能在被信息淹没 的仕t 界中挣扎。信息过载带来的一个直接问题就足信息迷向，信息过载使用户 迷失在信息世界中，不知道如何占找f 1 己需要的信息，或苦不知道占找ej t l 最 需受的信息。搜索引警j e 足为j 解决h 上信息过载和信息迷向而产生。 6 中国科学技术大学硕士学位论文 2 2 搜索引擎的发展历史 互联网信息的激增，以及用户对精确信息的需求，直接导致了信息检索课 题的产生和发展，尤其是在互联网领域对信息检索的依赖，使得信息检索一搜索 引擎成为人们工作和生活不可或缺的工具。搜索引擎是通过采集标引众多网络 站点来提供全局性网络资源控制与检索机制，通过整合全球互联网信息资源， 并将其合理的重组，从而方便用户查找所需要的信息。搜索引擎发展可以归结 为如下几个时期： 2 2 1起源和萌芽时期 1 9 9 0 年，互联网还没有得到全面的推广，但是，通过网络传输文件已经比较 普遍，由于文件分散在互联网各个f t p 主机上，查询起来相当不方便，当时，美 国蒙特利尔大学学生，a l a ne m t a g e 发明了一种自动索弓i f t p 站点的工具a r c h i e ， 通过a r c h i e 能够搜索f r p 文件名列表，但是用户必须输入精确的文件名，才能找 到需要的信息。a r c h i e i 作原理和现在的搜索引擎已经非常相似，它依靠脚本程 序自动搜索网上共享的文件，然后对相关信息进行索引，提供给用户查询。不 过它只限于文件索引功能，随后出现的一些类似于a r c h i e 的搜索工具，最终加入 了榆索网页的功能。 2 2 2 逐步发展时期 随后。由于互联网的逐步扩大，人们对网页抓取和新网点的发现产生了 浓厚的兴趣，一种专门在网络间爬来爬去，检索信息的机器人程序出现了，这 就是后来搜索引擎用来爬取网页的蜘蛛程序一一网络蜘蛛，这个软件是麻省 理工学院的m a t t h e wg r a y 发明的，并将其称为：w o r l dw i d ew e bw a n d e r e r , 抓取 机器人的独立发展，为搜索引擎底层信息的获取产生了很大影响。后来人们 改进了w o r l dw i d ew e bw a n d e r e r 这个传统的蜘蛛程序：将所有网页与其他网 站链接，即从跟踪一个网站的链接开始，就有可能榆索整个互联网。到1 9 9 3 年 底，一些基于此原理的搜索引擎纷纷登场，其中以j u m ps t a t i o n 、t h ew o r l dw i d e w e bw o r m 和r e p o s i t o r y b a s e ds o f t w a r ee n g i n e e 咖g ( r b s e ) s p i d e r 最负盛名。无论 是j u m ps t a t i o n 还是w w ww o r m 都不能称为真正的搜索引擎，他们只是以搜索 工具在数据库( 包含索引数据库) 中找到匹配信息的先后次序排列结果，因此 跟信息的关联程度无关。r b s e 更进一步，在排序结果中，引入了关键字串匹配 的概念，这些为真正含义的搜索引擎的出台，奠定了坚实基础。 7 第一章搜索引擎综述 2 2 3 第一代搜索引擎阶段时期 真正意义上的搜索引擎是1 9 9 4 年创立的l y c o s ，他由m i c h a e lm a u l d i n 将j o h n l e a v i t t 的s p i d e r 程序接入其索引程序中产生的。同年四月，美国斯坦福大学的 两名博士生，大卫菲勒和美籍华人杨致远共同创办了大家熟知的超级目录索 引y a h o o ，从此搜索引擎进入高速发展的历史时期。据统计，1 9 9 6 年，互联网已 有十几个大型综合性搜索引擎，各种专用的搜索引擎也达七十多个。在中文网 页世界，由于汉字处理的特殊性和中文信息资源站点正处于初步发展时期，中 文搜索引擎相对出现得比较晚，在1 9 9 7 年，首个中文网络搜索引擎g o y o y o 在香 港问世，随后中文搜索引擎才陆续在网上发布。这些被后人称为第一代搜索引 擎。代表：y a h o o ，a l t a v i s t a ，和i n f o s e e k ，当时网页的数量还不是很多，被索引 的数据也不超过1 0 0 万个网页。 2 2 4 第二代搜索引擎时期 1 9 9 8 年，以g o o g l e ，百度为代表的第二代搜索引擎拉开了搜索引擎发展的 序幕，其宗旨在于提高查准率，在这个目标指导下，进行了新的检索技术的研 发，因此这个时期的搜索引擎着重考虑用户对搜索引擎和搜索结果的体验，网 页结果的排序质量又是影响结果的最重要指标之一，g o o g l e 的p a g e r a n k j t # 序算 法在很大程度上解决了这一难题，关于p a g e r a n k 算法的探讨，下面的章节会有 详述。第二代搜索引擎规模是在瓦联网数据库极大丰富的背景下产牛的，也是 在互联网信息过载和信息迷向的时期到来，搜索引擎在一定程度上缓解了这些 问题，但互联网数据依然在增加，信息过载的问题，时刻对搜索引擎带来冲击。 因此，第二代搜索引擎，仅仅只是信息过载时期，权宜的解决之道。 2 2 5 下一代搜索引擎 新代的搜索引擎主要解决搜索引擎和用户之间的语义沟通i 口j 题，如个性 化搜索，基于语义理解的搜索引擎等。同时随着w e b 2 0 理念的提出，互联网用 户的信息获取模式由被动模式转化为主动的信息获取，同时六度分隔理论进一 步志入人们的视野，网络的社会化开始日趋成熟，如何搜捕用户的让区活动信 息，也将成为搜索引擎发眨的一个很大的完点。 中国科学技术大学硕十学位论文 2 3 搜索引擎的分类 按照信息搜集方式和服务提供方式不同，搜索引擎系统可以分为以下几大 类： 2 3 1目录式搜索引擎 这类搜索引擎一般以人工或者半自动方式搜集或者整理信息，建立起搜索 引擎。通常，信息处理入员查看人工形成信息摘要，包括对w e b 站点的评价、分 类以及简要的描述，并将这些信息置于事先确定的分类框架中。分类的模式一 般采用层次树状结构，从树的根节点逐层向下列出从一般到特殊的分类和各级 子类，最底层的叶子节点则指向各个互联网上相关的网页链接。 这类搜索引擎主要为用户提供浏览服务和检索服务，由于加入人工处理 的环节，所以信息准确，导航质量高，但是由于人工需要耗费大量的人力和 财力，维护的工作量相当之大，信息更新也很难做到跟互联网同步，因此，这 种目录式搜索引擎不适合大范围的互联网，只适合在某个特定的网站中。比 如大型的门户网站，采用这种方式为用户提供检索服务早期的搜索引擎， 如y a h o o ，l o o k s m a r t ，o p e n d i r e c t o r y 等，目前这类搜索引擎也采用了机器人爬取 等先进技术，但还足保留了以前传统的目录结构。 2 3 2 全文搜索引擎 全文搜索引擎也就是上文提到的第二代搜索引擎，它由一个称为蜘 蛛( s p i d e r ) 的网络机器人程序以某种策略自动的在互联网上搜集和发现信 息，由索引器为搜集到的信息建立索引，通过检索器，根据用户的查询输入 检索索引数据库，并将查询结果返回给用户。这类搜索引擎的优点在于，搜 集的信息量大，更新及时，不需要人工干预。具有高效性和智能化，但同时 存在了一个较大的隐患：返回的搜索结果太多，很多是无关信息，用户需要 根据自己的喜好筛选结果。这类搜索引擎的代表：g o o g l e ，a l t a v i s t a ，i n k t o m ， l n f o s e e k , f a s t f a s t s e a r c h ，l y c o s ，国内的天网，悠游，o p e n f i n d ，和百度也属于这 类搜索引擎的典范。 2 3 3 元搜索引擎 元搜索引擎是建立在已有搜索引擎的基础之上的一种搜索引擎，它把其 它已存存的搜索引肇做为自己的成员搜索引擎，并把他们的结果重新组合，返 9 第：章搜索引擎综述 回给用户。对于每一个用户的检索请求，元搜索引擎自己并不做任何处理。而 是按照各个成员引擎的查询格式做相应的转化之后，再分发到各个成员搜索 引擎。各个成员搜索引擎返回结果给元搜索引擎之后，元搜索引擎进行结果 组合，并按权重的序列输出给用户。这类搜索引肇的特点是：能够分散处理 负载，增加检索的范围，使结果的信息量更加大，更加全面，同时还具有良好 的扩展性，可以加入多个搜索引擎，而且各个成员引擎可以缩小规模，提供 更好的性能，检索响应时间更短，同时还可以保证检索的内容最新。缺点是 不能够充分使用搜索引擎的功能，用户要做更多的筛选。这类搜索引擎的代 表：l n f o s p a c e ，d o g p i l e ，v i v i s i m o ，m e t a c r a w l e r ，l n f o m a r k e t 等。 2 4 搜索引擎的基本组成 搜索引擎可以由抓取器，文本处理器，索引器，检索器，查询接口组成，下 面的示意图2 1 充分表达了搜索引擎的各个模块组成： 图2 t ：搜索引擎的结构示意图 l o 中国科学技术大学硕士学何论文 2 4 1网页抓取 为了搜索到互联网上的海量数据，搜索引擎需要了解互联网上有些什么样 的数据，互联网不仅仅含有庞大的静态的网页，而且包括纷繁复杂的动态网页， 多媒体文件，文本文件( 包括d o c 和p d f 等文件) 。这些数据不能依靠互联网自动的 提供给搜索引擎，而是需要通过搜索引擎的软件系统抓取到本机。 将数据抓取下来作为处理对象，是搜索引擎最初的工作。搜索引擎抓取网 页的时间一般都是先于查询的，搜索引擎先会傲好抓取网页的工作，即在用户 提出查询以前，搜索引擎已经将网页数据处理好，这一步称为离线处理。从常 识可知，在网页比较畅通的情况下，从网上下载一篇网页需要一秒的时间，搜索 引擎不可能在这么短的时间抓到成千上网的网页，并将其处理完毕，满足用户 的查询匹配要求的。搜索引擎完成网页抓取的工作，是通过搜索器完成的。 2 4 1 1 抓取器简介 搜索器俗称为网络蜘蛛( s p i d e r ) ，也称为机器人( r o b o t ) ，爬行者( c r a w l e r ) 或者 蠕虫( w o r m ) ，其本质是一种计算机程序，按照某种策略自动在在互联网上爬行 并搜集互联网上的资料，它要尽可能多的搜集各种类型的新信息，同时由于网 上的信息更新很快，需要定期更新已经搜集过的资料，防止出现链接无效和链 接信息更换的情况，因此要求搜索引擎抓取网页具有持续性和周期性，并且周 期不能太长( g o o g l e 公司一般2 8 天，重复一次查询) 2 4 1 2 搜索器的抓取原理 涉及到如何具体抓取网页，可以有不同的考虑。其中常见的方法是： 将w e b 视作为一张有向图，搜索过程如下：首先给定起始u r l 集合s ( 根节点集 合) 开始，沿着网页中的链接( 新的u r l 节点) ，按照不同的策略遍历( 先深、先 宽、或者某种别的) ，不停的从s 中移除u r l ，下载相应的网页，解析出网页中的 超链接u r l ，看是否已经被访问过，将未访问过的那些u r l 加入集合s 。整个过 程可以彤象地想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w e b ) 上爬行( c r a w l ) 。 2 4 1 3 抓取的问题 搜集网页需要注意的一个重要问题就是放率。一般而言，网站为了扩人自 己的影响力和知名度，愿意让自己的网页皱搜索引擎索引到，从而能提高网站 的访问量。但另外一方面，叫站小希望搜索引擎的频繁访问而防碍自身的活动， l l 第：覃搜索引擎综述 例如搜索引擎的反复抓取活动目前已经占据了互联网的大部分带宽，网站不希 望搜索引擎阻碍用户的访问活动和自身的工作，加入搜索引擎无节制的抓取， 很有可能会造成网站速度过慢，甚至可能会造成网站的瘫痪。一些运行较为完 备的网站往往设置了监视器运行，查看是否有单个i p 的地址过分的访问网站， 一旦发现，则将马上屏蔽掉这个i p 地址。因此，适当的抓取网页，限制单位时间 内对一个网站的抓取数量，是一个成熟的搜索引擎所必须考虑到的问题。 抓取网页另外需要考虑的问题就是质量问题，由于互联网上3 0 的信息具 有重复性，另外大量的垃圾信息的充斥，因此希望搜索引擎能在相| 一条件下( 时 间相同，网页数量一致) 能尽量抓取质量高的网页，换言之，就是不能漏掉很重 要的网页。如果让重要性和受欢迎的程度等同起来，即越多人点击的网页，认 为越重要，则可以考虑一个网站中，网页的重要程度与链接深度有关，链接深度 不高的网页，往往是更加重要的网页( 跟g o o g l e 的p a g e r a n k 算法很相近的思想) 。 在设计的搜索引擎中，网页的抓取也是按照宽度搜索优先的策略进行的。 还有一个问题就是网页的重复问题，包括u r l 重复和网页内容的重复，由 于网页的抓墩是通过u r l 组成的图搜索，因此不可避免的会产生一张庞大而且 极易循环的图表。这样容易使抓取行为进入死循环。因此必须记录下搜索引擎 抓取到的网页，防止重复抓取，对于网页内容重复，搜索引擎应该能有效的将其 组合在一起，避免结果在排序中莺复出现。当然在具体的实现上，还包括海量 信息的处理知识，如何最优化查找表等问题。 2 4 2 文本预处理 2 4 2 1 互联网的文档和预处理 互联网的文档大部分是半节构化的h t m l ，包括由动态网页( a s p , j s p ，x h t m l 等) 转化到客户端的h t m l 文档，其次为具有某种格式的文档，如p s ，d o c ，p d f 文 档，p p t 文档，r t f 文档，x l s 文档等，这就搜索引擎能从这些不同的文本中提取出需 要的信息，比如，h t m l 文档通过不同的命令标识符来表示不同的字体，颜色， i 7 = 置，链接等版式，提取文本信息需要去掉这些标识，留下对我们有用的文字信 息，但另方面，又需要保留某些标识，如标题，链接，因为这些暗含了某监特 定的意义( 比f t l j - 关键澜出现在标题中显然比关键调出现在文章中更 有分鼍) ， 可以根据这蝗信息来衡鞋搜索的结果和搜索词的相关程度。例；【l j p a g r a n k 的排 咩算法，就会利用到网页的u r l 链接。对于其它文本，需要将文本信息从文件 格式中剥离出来。仪仪杆f 对蛮询有用的文字信息。 2 中国科学技术大学硕士学伉论文 因此对于不同的文档格式，搜索引擎必须为它们提供不同的接口，并获得 标题。链接等有价值的文字信息区域，这些就是对文本的预处理。通过分析和 处理，为搜索引擎查询数据做必要的准备，这些都可以称为对文档的预处理。 另外，按照多媒体的类型可分为图像，文本，音频，视频等，按照内容性质 可分为链接信息和网页本身信息，网页抓取器按照需要可能仅仅保留文本信息 作为进一步分析的需要。其余的多媒体信息，由于容量方面的考虑，如果不是 做专业的图像搜索或者视频搜索( 如垂直搜索引擎中的多媒体搜索) ，这些一般 忽略掉。 2 4 2 2 文档进一步处理 仅仅有这些处理是不够的，由于机器对语言的理解带有机械化，而人类的 语言丰富多变。要求计算机从语义上对用户的查询进行理解，在目前而言，是 一个相当有挑战性的课题。目前搜索引擎所采取的方式为：将句子划分为词汇， 这些词汇通过逻辑关系组合成一个完整的查洵表达式，然后通过查询条件和文 章中的词汇进行匹配，达到检索的目的。 因此，将句子划分为词汇成为文档处理不可避免的问题。 2 4 2 2 1 西文处理英语也有一定程度的负荷，比如需要把不同时态的词语， 单复数1 i 同的词语，等效为同一个词语，这样可以使得检索的时候更加全面，增 加查全率事实上，所有的英文搜索引擎对单词的处理，都是先将不同的词汇 转化为原形，然后再做处理的。 2 4 222 中文处理前面提到，搜索引擎采取的信息匹配策略是将句子划分为 词汇，这些词汇，然后再做进一步的匹配工作，对于英文而言，句中的词与词之 间有天然的空格符号将其分离，而中文就不同，只能通过句法去理解和分离出 具有不同含义的词汇，这样就无形中给搜索引擎带来了额外的工作，即把句子 切割成很小的词汇单元。 分词技术中文分词技术一般可以分为以下三类：第一，字符串匹配的方法，基 于字符串匹配方法需要利用到字典按照匹配规则又可以分为正向最大匹配、 逆向最大匹配、双向匹配，最少切分等。第二，基于理解的方法。基于理解的方 3 第一8 搜索引辈综述 法在分词的同时进行句法、语义分析，利用这些辅助信息来处理歧义切分现象。 第三，基于统计的方法。基于统计的方法对文本中相邻出现的字的组合进行频 率统计，将高频的组合定义为词，该方法不需要使用字典。在实际的应用系统 中，根据需要具体选择使用的方法，或者经常将几种方法结合起来使用。 一般而言，基丁理解的方法往往不适合机器对语言的切割，在目前的条件 下，通过机器来参与对高层语意的理解是一个相当有挑战性的课题，因此，下面 从算法的角度上对基于字符串的匹配算法和基于统计的方法做一下简要介绍。 l ：基于字符串的匹配算法： 结合汉字的特点( 单字成词) ，基于最大匹配算法一般都有实际的可行 性( 与此相反的是最小匹配算法，一般都不会采用这样的算法，而目分词的结 果也不太理想) ，通常情况下，基于逆向匹配的算法分词精度略高于正向匹配算 法。 匹配算法的基本思想是先建立侧库，对给定的待分词字串，以某种方法 切取其子串，如该子串与词典某项匹配成功，则该子串是词，继续切分其余部 分；否则该子串不是词，重新切取给定汉字串的子串进行匹配。字符串匹配法 根据切取方向的不同，又可分为正向最大匹配法( m a x i m u m m a t c h i n g m e t h o d m m 法) 、逆向最大匹配法( r e v e r s em a x i m u mm e t h o d ，r m m 法) ，以及二者结合的 双向匹配法( b i _ d i r e c t i o nm a t c h i n gm e t h o d ，b m 法) 。 双向匹配方法将最人前向匹配法( m m ，m a x i m u mm a t c h i n gm e t h o d ) 和逆 向最大匹配法( r m m r e v e r s em a x i m u mm a t c h i n gm e t h o d ) 相结合，即针对一 个字符串，分别从两个方向进行处理。最大正向匹配法基本思想为：设d 为 词典，m a x 表示d 中的最大词长，s t r 为待切分的字串。m m 法是每次从s t r 中 取长度为m a x 的子串与d 中的词进行匹配。若成功，则该子串为词，指针后 移m a x 个汉字后继续匹配，否则子串逐次减一进行匹配。逆向最大匹配法的基 本原理与m m 法相同，不同的是分耐的扫描方向，它是从右至左取了串进行匹 配。 2 ：基于最大概率的匹配算法摹于最大概率的匹配算法，也称为基于概率的 匹配算法，分词的时候很容易出现的一个问题就是歧义现象，下面的例子就足被 引用剑的例子：对“结合成分子时”进行中文分词，会出现下图2 2 所示的众多结 果。 但符合人的语占二j 惯的只会有一种，把上述的句子分裂成为：“结 合”“成”“分严”“时”这种划分。怎样才能做到这样的划分呢? 中文从形式看， 4 中国科学技术大学硕士学位论文 方式l j方式2 扣方式3 p方式4 p 结结p结一结一 合一 舍一 合一 合j