已阅读5页,还剩67页未读, 继续免费阅读
(计算机应用技术专业论文)基于分布式的智能搜索引擎.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中文摘要 随着i n t e r n e t 网上的知识呈几何级数式的增长,搜索引擎作为个查询用户 所需信息的工具,其作用越来越受到人们的重视。目前,一个优秀的搜索引擎 能够大大地提高一个网站的点击率,搜索引擎已经成为网站的门户。简单地讲: 搜索引擎通过一个称之为“网络蜘蛛”的程序,将网页上的内容按一定的方式存放 在自己的数据库里,并昼夜不停地维护、更新该数据库,当用户提交查询时, 就从数据库中找出与该关键字相关联的信息,并按照一定的顺序返回给用户。 与其它的技术一样,搜索引擎的发展也离不开对其理论基础的研究。本文在 对当前第二代搜索引擎系统进行理论分析的基础上,结合最有代表性的g o o g l e 公司的搜索引擎系统进行了详细的系统分析,并讨论了其中的关键数据结构和 算法,在这个基础上,我结合我当前正在进行开发的p 1 s 个人智能搜索引擎项目, 给出了我的基于分布式系统的架构以及相关的算法,并给出了具体的实现。同 时也考虑到第二代搜索引擎系统的种种不足,给出了智能搜索引擎系统的理论 概述,并结合月前我的项目,进行了个性化搜索的研究,给出了两种创新的个 性化搜索方法。 本文具体进行了两个方面的论述: 1 、分布式搜索引擎系统的设计与实现。尽管当前的搜索引擎系统已经广泛 采用了分布式的系统架构,但是由于受到搜索引擎系统软件的设计和算法的制 约,每个公司的实现方式不太一样,本文根据我当前正在开发的p i s 智能搜索引 擎系统,提出了一个比较适合于基于主题的分布式搜索引擎的架构,对其中的 分布式页面抓取系统和分布式等级计算系统进行了详细的论述,并给出了具体 模块的设计与实现方法,同时也提出了一种新的基于页面分类的页面等级计算 算法t 0 p i cp a g e r a n k 算法。 2 、智能化搜索引擎系统的设计。智能化的搜索引擎系统已经被提出了很多 年,但是至今依然发展缓慢,本文中我结合智能搜索引擎的相关理论知识,提 出了两种基于智能化搜索系统的个性化搜索方法基于b l o g 的个性化方法和 基于a j a x 的个性化方法,通过与传统的个性化方法进行融合,能够提供出更精 确的个性化搜索,针对不同的用户,我们的个性化搜索系统能够提供出更加个 性化的返回结果集。 关键字:搜索引擎,智能化,个性化,页面分类,p a g e r a n k ; a b s t r a c t w i t ht h er i s i n go ft h ei n t e m e t sk n o w l e d g eo nt h ew a yo fg e o m e t r i cs e r i e s ,t h e s e a r c he n g i n ei sl o o k e da sat o o lt h a tt h eu s e r sg e ti n f o r m a t i o nw i t hi t ,a n di t b e c o m e sm o r ea n dm o r ei m p o r t a n t a tp r e s e n t ,a ne x c e l l e n ts e a r c he n g i n ec a n i n c r e a s et h en u m b e ro ft h ew e b s i t e s a c c e s s i n gl a r g e l y s i m p l y , w i t ht h ep r o g r a mt h a t i ti sn a m e da s “s p i d e r ,t h es e a r c he n g i n es a v e st h en e t w o r k si n f o r m a t i o ni n t ot h e d a t a b a s ea n dt h ed a m b a s ei sm a i n t a i n e da n du p d a t e da l ld a y w h e nt h eu s e r sp u ti na s e a r c h ,t h es e a r c he n g i n ew i l lf i n dt h ei n f o r m a t i o nt h a ti sc o r r e l a t e dw i t ht h eu s e r s k e yf r o mi t so w nd a t a b a s ea n dt h er e s u l tw i l lb er e t u r n e db yt h ed c 6 n c da l g o r i t h mo f s o r t i n g a st h eo t h e rt e c h n o l o g y , t h es e a r c he n g i n e sd e v e l o p m e n tg o e sw i t hi t st h e o r y s s t u d y o nt h eb a s eo ft h es e a r c hm o d e l sa n a l y z ea n dt h ei m p l e m e n to fg o o g i e ,t h i s p a p e ra n a l y z e sa n dd i s c u s s e st h e 皿n c i p l ea n di m p l e m e n to ft h ef a s h i o ns e a r c h e n g i n e ss e v e r a lt e c h n o l o g y , i n c l u d i n gt h ed a t as t r u c t u r ea n da l g o r i t h m a n dt h e ni g a v em yp r o p o s a la b o u tt h ef r a m e ,t h ea l g o r i t h ma n dt h ei m p l e m e n to ft h ed i s t r i b u t e d s e a r c he n g i n e i nv e wo ft h es h o r t a g eo ft h ef a s h i o ns e a r c he n # n es y s t e m , i e x p o u n d e dt h et h e o r yo ft h ei n t e l l i g e n ts e a r c he n g i n e ,a n dd i dm yr e s e a r c ha b o u tt h e i n d i v i d u a ls e a r c he n g i n e a tl a s t ,1g a v et w on e wm e t h o d so ft h ei m p l e m e n to ft h e i n d i v i d u a ls e a r c he n g i n es y s t e m t h ep a p e rd i s c u s s e dt w oa s p e c t sc o n c r e t e l y : 1 t h ed e s i g na n di m p l e m e n to ft h ed i s t r i b u t e ds e a r c he n g i n e a l t h o u g ht h e d i s t r i b u t e ds y s t e mw a sa d o p t e di nm a n ys e a r c he n g i n es y s t e m s ,b e c a u s eo ft h el i m i t o ft h ed e s i g no ft h es y s t e ms o f t w a r ea n dt h ea l g o r i t h m t h ei m p l e m e n ti sd i f f e r e n t o n t h eb a s eo fm y p m j e c to ft h ep i sp e r s o n a la n di n t e l l i g e n ts e a r c he n g i n e ,ig a v ea n e a v f r a m e :o ft h ed i s t r i b u t e ds e a r c he n g i n e ,w h i c hi s a d a p t e df o rt h et o p i c - b a s e d d i s t r i b u t e ds e a r c he n g i n es y s t e m ,a n dd i s c u s s e dt h ed i s t r i b u t e dc r a w ls u b s y s t e m ,t h e p a g er a n kc o m p u t i n gs u b s y s t e m ,a n dt h en e wp a g cr a n ka l g o r i t h m - - t o p i cp a g e r a n k ; 2 t h ed e s i g no ft h ei n t e l l i g e n ts e a r c he n g i n e t h ep r i n c i p l eo ft h ei n t e l l i g e n t s e a r c he n f i n es y s t e mw a sp r e s e n t e dm a n yy e a r sa g e ,b u tt h ep r o c e s so ft h e a d v a n c e m e n tw a ss l o w i nt h ep a p e r , o nt h eb a s eo ft h ee x p l a n a t i o no ft h et h e o r yo f t h ei n t e l l i g e n ts e a r c he n g i n es y s t e m ,1g a v et w on e wm e t h o d so ft h ei m p l e m e n to ft h e i n d i v i d u a ls e a r c he n g i n es y s t e m - - t h ei n d i v i d u a ls e a r c he n g i n es y s t e mo fb l o g b a s e d n a n da j a x - b a s e d b yc o m b i n a t i o nt h ec o n v e n t i o n a la n dt h en e wm e t h o d so ft h e i n d i v i d u a ls e a r c he n g i n e ,o u rs y s t e mc a ng i v em o r ea n dm o r ep r e c i s ea n di n d i v i d u a l r e s u l t sf i o mi n d i v i d u a lt 0i n d i v i d u a l k e yw o r d :s e a r c hb g i n e ,i n t e l l i g e n ts y s t e m ,i n d i v i d u a ls y s t e m , p a g e sc l a s s i f i e d , p a g e r a n k h i 此页若属实请申请人及导师签名。 独创性声明 本人声明,所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知,除了文中特别加以标注和致谢 的地方外,论文中不包含其他人已经发表或撰写过的研究成果, 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名:差垒丝日期型:! ! :! 占 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定, 即:学校有权保留送交论文的复印件,允许论文被查阅和借阅; 学校可以公布论文的全部内容,可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名:兰金丝导师签名 注:请将此声明装订在学位论文的目录前。 日期知,。6 武汉理工大学硕士学位论文 1 1 论文选题考虑 第一章绪论 2 0 世纪末是万维网开始膨胀的时期,它的发展速度是十分惊人的。据统计, 万维网已经连通了世界上几乎所有的国家,并且万维网正在急速发展。目前, 万维网已经成为世界上最大的信息源,成为全球范围内科研、教育、商业和社 会、新闻、学校和专业机构介绍、图书及娱乐等信息的集大成者。万维网信息 量的急剧增加所带来的最直接的问题就是:面对如此庞大的世界级数据源,网 络用户如何从这些浩如烟海的资源中找到符合自己需求的信息。这已经成为如 何有效地利用万维网信息的最大障碍之一。随着信息量的增长,人们越来越多 地关注如何开发和利用这些资源,高效地定位特定信息变得越来越重要。为了 帮助用户在万维网上搜索自己需要的信息,计算机专家和信息管理专家开发出 了万维网信息检索工具搜索引擎。 搜索引擎是指在万维网中主动搜索信息并能自动索弓 _ 且提供查询服务的一 类软件系统。它通过使用网络搜索软件( 又称网络搜索机器人) 或网站登录等方 式,将互联网上大量网站的页面收集到本地,经过加工处理而建成数据库,从 而能够对用户提出的各种查询做出响应,提供用户所需的信息。搜索引擎的出 现使得在数秒钟内检索出大量的文献成为可能。 目前搜索引擎的研究和应用已经取得了巨大的进步,但是从当前搜索引擎 实际的现状来看,仍然存在下述几个问题有待去进一步研究: ( 1 ) 网络信息资源日新月异,每天都是以几何级数成倍增长。目前世界上 最大的搜索引擎公司c , o o g l e 公司的总页面数大概在3 0 亿左右,但是这大概仅仅 占整个互联网上资源总量的3 0 ,而且由于互联网上网络资源的增长速度远远 超过g o o g l e 公司页面数增长的速度,也就是说,互联网上有超过7 0 的资源用 户是无法通过搜索引擎检索到。这个问题从第一代搜索引擎开始就一直存在, 而且在以后的相当长的一段时间内将一直存在,但是这并不意味着我们对此无 能为力,已经提出来很多年的分布式计算理论将能够给这个问题的解决带来曙 光。 ( 2 ) 目前人们对搜索引擎越来越依赖,但是同时也带来了一系列的问题。 搜索引擎通过对用户输入的关键字在自己的索引数据库中进行模糊查询,然后 武汉理工大学硕士学位论文 将结果返回给用户,随着搜索引擎数据量的递增,返回的大量信息都不能满足 用户的需求,另外,对不同的用户,相同关键字的检索结果是一样的,这也是 不能接受的。以上两个问题,正是智能化搜索引擎和个性化搜索引擎需要解决 的问题。 在本文中主要从上述两个方面来进行分析和阐述,并具体提出了有一定创 新性的解决方案。 1 2 本课题研究的理论基础 自然语言是通向人类知识宝库的一把钥匙,作为智能搜索引擎,首先要掌 握这把钥匙才能方便自如地跟人类交换信息,随着信息时代的发展,网上信息 的极大丰富以及使用系统的用户的不断增加,对于搜索引擎的体系结构方面也 提出了更高的要求。集中式的架构已经很难满足大型网站系统的需求,甚至成 为信息导航的瓶颈,因为随着信息量的增大和用户的增加,它对w e b 服务器提 出了太高的要求,为了很好地介绍本文,首先需要介绍分布式系统设计和自然 语言理解的有关知识。1 2 1 1 2 1 自然语言理解理论引入 现代科技的发展使人类进入了信息时代,对于人类而言,最自然,最重要 效率最高的信息载体之一就是自然语言,人类能够利用自然语言进行信息的传 递和交流,这是人类与动物的本质区别之一。语言是思维的载体,是人际交流 的重要工具,在人类历史上以语言文字形式记载和流传的知识占知识总量的8 0 以上。在信息化社会里,语言信息处理的技术水平和每年所处理的信息总量已 成为衡量一个国家现代化水平的重要标志之一。l 列 语言是人类最重要的交际工具。语言交际的模式主要是表达和理解,一方 表达,另一方理解。语言交际就是在一定的场合,依据一定的规则,表达和理 解一定的意思,句法,语义和语用在实际中是三位一体的。 从第一台电子计算机诞生到现在半个多世纪过去了,人类已经由发明工具 延伸自己的四肢进化到延伸自己的大脑,计算机一开始只是科学家,工程师的 计算工具,现在已经逐步进入大众的日常生活i n t e r n e t 将世界各地的电脑连成一 片,人们可以在网上查询或发布信息可以在网上聊天,漫游,购物甚至在网上 2 武汉理工大学硕士学位论文 生存。“电脑+ 网络”正在从延伸人的大脑发展为延伸人的生存空间,网络社会 使人类的交际行为和方式发生重大变化,语言开始从单纯人类最重要的交际工 具发展到可以进行人和机器之间的交流。 从表达方和理解方来看,现在交际行为至少有以下四种模式: a 人表达 人理解 b机器表达 人理解 c 人表达 机器理解 d机器表达 机器理解 以电脑为发送信息的“一方”或接受信息的“另一方”,研究电脑如何表达 人的语言( 模式b ) 是“自然语言生成”,研究电脑如何理解人的语言( 模式c ) 是“自然语言理解”。机器翻译( m t ) 需要电脑理解一种自然语言,然后转化 生成为另一种语言,所以是既包含自然语言理解研究,也包含自然语言生成研 究( 属于模式d ) ,还包含语言之间的转换研究。因此,研究自然语言处理不可 以不研究语言交际,不可以不研究人脑的语言机制和模拟人脑的语言机制。 1 2 2 自然语言理解研究进程 人工智能是以建立智能化的,自主的计算机为目标的- 1 7 学科,它研究的 课题包括:专家系统,问题求解,逻辑和不确定问题,自然语言处理,机器人 学学习机,视觉和模式识别等等。其中自然语言处理是人工智能的核心课题, 包括自然语言的分析理解和综合生成。起初,自然语言处理强调立新主义,用 人工智能的方法( 如状态空间搜索,知识表示和机器学习等) 来处理自然语言。 在这个阶段,人们集中力量建立各种规则系统,试图通过规则地演算来解决语 言的分析和生成问题,但是不久,人们发现自然语言远不是一个精确定义的符 号体系,精心构造的规则只能在严格受限的领域内起作用,无法处理大规模真 实文本中的种种复杂的语言现象。 到了年代后期,计算语言学开始注重对大规模真实文本的处理,出现了 语料库语言学,其特点是以经验主义为旗帜,以对大规模真实文本的统计为主 要方法。语料库语言学认为,人类的一切语言知识都蕴含在大规模的语料之中, 可以通过统计来发现这些知识,以前人们凭主观内省而得到的语言知识是不完 整的,甚至可能是错误的,语料库语言学在真实文本的词性标注上打了一个大 胜仗。以前人们制定了各种语言学规则来标注词性,正确率并不高,而运用统 武汉理工大学硕士学位论文 计方法和训练语料,已标注过的语料,来标注词性准,确率高达9 5 左右。然 而,语料统计的方法也不是万能的,随着语言信息处理层次的提高,简单的统 计模型越来越暴露出其缺点,难于处理长距离依赖的语言现象,难以获得高度 概括的知识以顺利地处理训练语料之外的语料,目前,在对大规模真实文本进 行自动句法分析这一关键问题上还没有取得突破性进展。 1 2 3 分布式系统设计理论的引入 显然,未来对计算速度,系统的可靠性和成本实效性的要求必然将促使发 展另外的计算机模型来代替冯诺依曼结构的计算机,随着计算机网络的发展, 一个新的梦想成为可能分布式计算。当用户需要完成任何任务时,分布式 计算提供对尽可能多的计算机处理能力和数据的透明访问,同时实现高性能和 高可靠性的目标,在过去的十多年里,人们对分布式计算系统的兴趣迅猛增加。 分布式计算的主题是多种多样的,许多研究人员在研究有关分布式硬件结构和 分布式软件设计的各方面问题以开发利用其潜在的并行性和容错性。 分布式计算系统( 或分布式系统) 多种多样并涉及不同的体系结构,对一 些用户来说,一个分布式系统是为解决单个问题而紧密结合在一起工作的多处 理机的集合,对另一些用户来说,一个分布式系统可能意味着一个由地理上分 散的各自独立的处理机组成的计算机网络,这些处理机连接在一起以实现对不 同资源的共享。然而,分布式系统这个词在计算机系统中被如此广泛应用以至 于它的使用变得有点贬值,许多这方面的混乱来源于缺乏对物理的分布和逻辑 的分布的区分,通过区分这两个概念,就可以更准确地描述一个分布式系统的 属性。1 1 】 对于分布式系统,我们使用以下定义:一个分布式系统是一个对用户看起 来像普通系统,然而运行在一系列自治处理单元上的系统,每个处理单元有各 自的物理存储器空间并且消息的传输延迟不能忽略不计。在这些处理单元间有 密切地合作,系统必须支持任意数量的进程和处理单元的动态扩展。 1 2 4 分布式系统设计的目的 建立一个分布式系统的主要目的在于:1 1 j ( 1 ) 固有的分布式应用。分布式系统以一种很自然的方式开始存在,例如, 4 武汉理工大学硕士学位论文 在我们的社会中人群在地理上是分布式的并且分布式地共享信息,一方面,一 个分布式数据库系统中的信息产生于不同的分支机构,所以能够快速地完成本 地访问,另一方面,系统也提供了全局视图来支持各种全局操作; ( 2 ) 性能成本。分布式系统的并行性降低了处理的瓶颈,提供了全面改进 的性能,也就是说,分布式系统提供了更好的性能价格比; ( 3 ) 资源共享。分布式系统能有效地支持不同位置的用户对信息和资源, 硬件和软件的共享; ( 4 ) 灵活性和可扩展性。分布式系统可以增量扩展,并能方便地修改或扩 展系统以适应变化的环境而无需中断其运行: ( 5 ) 实用性和容错性。依靠存储单元和处理单元的多重性,分布式系统具 有在系统出现故障的情况下继续运行的潜力; ( 6 ) 可伸缩性。分布式系统能很容易地扩大以包括更多的资源( 软硬件) ; 5 武汉理工大学硕士学位论文 第二章搜索引擎的组成原理 2 1 搜索引擎的概述 w e b 搜索引擎( s e a r c he n g i n e ) 是随着w e b 信息地迅速增加,从1 9 9 4 年开 始逐渐发展起来的技术。实际上,搜索引擎是指因特网上专门提供查询服务的 一类网站,它以一定的策略在互联网中搜集,发现信息,对信息进行理解,提 取,组织和处理,并为用户提供检索服务,从而起到信息导航的目的。用户的 查询途径主要包括自由词、全文检索、主题词检索、分类检索以及其他特殊信 息的检索。 目前搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务。搜 索引擎站点也被美誉为“网络门户”。搜索引擎技术因而成为计算机工业界和学 术界争相研究、开发的对象。 目前,按照信息搜集方法和服务提供方式韵不同,搜索引擎系统可以分为 三大类:瑚 ( 1 ) 目录式搜索引擎:以人工方式或者半自动方式搜集信息,由编辑员查 看信息之后,人工形成信息摘要,并将信息置于事先确定的分类框架中。信息 大多面向网站,提供目录浏览服务和直接检索服务。 ( 2 ) 机器人搜索引擎:由一个称为蜘蛛( s p i d e r ) 的机器人程序以某种策略 自动地在互联网中搜集和发现信息,由索引器为搜索到的信息建立索引,由检 索器根据用户的查询输入检索索引库,并将查询结果返回给用户。服务方式是 面向网页的全文检索服务。 ( 3 ) 元搜索引擎:这类搜索引擎没有什么自己的数据,而是将用户的查询 请求同时向多个搜索引擎递交,将返回的结果进行重复排除、重新排序等处理 后,作为自己的结果返回给用户。服务方式为面向网页的全文检索。 2 2 搜索引擎的组成原理 一个搜索引擎程序主要由搜索器( c r a w l e r ) 、索引器( i n d e x ) 、检索器 ( s e a r c h e r ) 和用户接口( u i :u s e ri n t e r f a c e ) 等四个部分组成,主要存储设备 由页面存储器( r e p o s i t o r y ) 和存储桶( b a r r e l ) 两部分组成。1 2 1 6 武汉理工大学硕士学位论文 搜索器( c r a w l e r ) 本质上是一种计算机爬虫( s p i d e r ) 程序,它时刻不停地 自动从i n t e r n e t 上不断抓取各种w e b 网页信息,再将页面原始内容经过压缩处理, 存入本地页面存储库,以备日后处理所用。 索引器( i n d e x e r ) 程序定期从页面存储库中取出网页原始信息,对其页面 内容进行分析和分解,以单词为主关键字进行索引,并初步进行排序处理,结 果存入适当的“存储桶( b a r r e l ) ”,即硬件存储单元中。 当互联网用户通过用户接口u l 提交查询时,检索器( s e a r c h e r ) 程序根据 用户输入的查询关键词,在已由索引器( i n d e x e r ) 完成索引和初步排序的存储 桶( b a r r e l ) 中进行查找,并采用特定的页面优先度算法对其结果进行最终排序, 使之尽可能符合用户查询需求。最后,用户接口u l 将最终查询结果呈现在互联 网用户面前。 图2 1 搜索引擎组成结构图 搜索引擎程序各组成部分的功能详细介绍如下: 2 2 1 搜索器( c r a w l o r ) 搜索器的功能是在互联网中漫游,发现和搜集信息。它常常是一个计算机 程序,日夜不停地运行。它要尽可能多,尽可能快地搜索各种类型地新信息, 7 武汉理工大学硕士学位论文 同时因为互联网上的信息更新很快,所以还要定期更新已经搜集过的旧信息, 以避免死连接和无效连接。目前有两种搜集信息的策略: 从一个起始u r l 集合开始,顺着这些u r l 中的超链( h y p e r l i n k ) ,以宽度 优先、深度优先或启发式方式循环地在互联网中发现信息。这些其实u r l 可以 是任意地u r l ,但常常是一些非常流行、包含很多连接的站点( 如y a h o o ! ) 。 将w e b 空间按照域名、口地址或者国家域名划分,每个搜索器负责一个子 空间的穷尽搜索。 2 2 2 索弓l 器( i n d e x e r ) 索引器的功能是理解搜索器所搜索的信息,从中抽取出索引项,用于表示文 档以及生成文档库的索引表。 索引项有客观索引项和内容索引项两种:客观索引项与文档的语意内容无 关,如作者名,u r l ,更新时间,编码,长度,链接流行度( l i n kp o p u l a r i t y ) 等等;内容索引项是用来反映文档内容的,如关键词及其权重,短语,单字等 等。内容索引项可以分为单索引项和多索引项( 或称短语索引项) 两种。单索 引项对于英文来讲是英语单词,比较容易提取,因为单词之间有天然的分隔符 ( 空格) ;对于中文等联系书写的语言,必须进行词语的切分。 索引表一般使用某种形式的倒排表( i n v e r s i o nl i s t ) ,即由索引项查找相应 的文档。索引表也可能要记录索引项在文档中出现的位置,以便检索器计算索 引项在文档中出现的位置,以便检索器计算索引项之间的相邻或者相近的关系 ( p r o x i m i t y ) 。 2 2 3 检索器( s e a r c h e r ) 检索器的功能是根据用户的查询在索引库中快速检索出文档,进行文档与 查询的相关度评价,对将要输出的结果进行排序,并实现某种用户相关性反馈 机制。 检索器常用的信息检索模型有集合理论模型,代数模型,概率模型和混合 模型四种。 8 武汉理工大学硕士学位论文 2 2 4 用户接口( u s e ri n t e r f a c e ) 用户接口的作用是根据用户输入进行查询,并显示查询结果,提供用户相 关性反馈机制。主要的目的是方便用户使用搜索引擎,高效率,多方式地从搜 索引擎中得到有效的,及时的信息。用户接口的设计和实现使用人机交互的理 论和方法,以充分适应人类的思维习惯。 鉴于g o o g l e 在这个领域的统治地位,而且耳前已经公开的关于搜索引擎领 域的理论研究都是围绕g o o g l c 的搜索系统来进行的,在我的这篇文章中,我也 主要围绕g o o g l e 的一些已经披露的资料来进行引用分析,当然,g o o g l e 的技术 也在不断创新,发展,而且有一些关键算法属于g o o g l e 的商业机密,我们不可 能获得,但是在当前第二代搜索引擎系统还没有重大突破的时候,利用当前已 经公开的相关的理论知识来进行研究已经足够了,而我们后面将要谈论的个性 化,智能化搜索也是基于这些理论进行的。 2 3g o o g i e 的体系结构 搜索引擎根据用户的查询请求,按照一定的算法从索引数据库中查找相应 的信息并返回给用户。为了保证用户查找信息的精度和新鲜度,搜索引擎需要 建立并维护一个庞大的索引数据库。搜索引擎主要由网络蜘蛛、索引库与搜索 引擎软件等部分组成。如图2 2 所示。【3 j 9 武汉理工大学硕士学位论文 2 3 1 网络蜘蛛 图2 , 2c , o o o e 的搜索引擎结构图 搜索引擎需要定期收集信息。定期地( 一般是2 8 天) 派出网络蜘蛛( 也称 c r a w l e r ,即“爬行者”) 根据预先设定的地址范围遍历对应的网页,如果网页发 生变化或者发现新的网页,则获取该网页,传回服务器,然后继续沿网络遍历, 直至访问完所有的链接。因此,网络蜘蛛访问页面的过程就是对互联网上信息 遍历的过程。为了保证网络蜘蛛遍历信息的广度,事先设定了一些重要的链接。 g o o g l e 可同时运行3 个c r a w l e r ,当服务器把u r l 列表提供给c r a w l e r 后, 每个c r a w l e r 可同时保持大约3 0 0 个网络连接。高峰时,通过c r a w l e r ,g o o g l e 每秒钟获取的网页可超过1 0 0 个。影响爬行速度的一个重要因素是d n s 查询, 1 0 武汉理工大学硕士学位论文 为此,每个c r a w l e r 都要维护一个自己的d n s 缓冲。为此,每个c r a w l e r 都要维 护一个自己的d n s 缓冲。这样每个连接都处于不同的状态,包括:查询、连接 主机、发送请求、得到响应。这些因素综合起来使得c r a w l e r 变成一个非常复杂 的系统。 信息库是用来存放网络蜘蛛获取的网页。在g o o g l e 的信息库中包含了每个 网页的h t m l 文档,为节省存储空间,对每个网页都用z l i b 算法进行了压缩。 之所以采用z h b 压缩算法,是综合考虑了速度与压缩率的因素,而不是一味地 追求压缩率。信息库中的文档按照如图2 3 所示的格式存放。 图2 3 信息库的数据结构描述图 其中,d o c l d 为文档的标示;e n c o d e 表示存放文档时所采用的编码方式;u r l l e n 表示该文档来源的u r l 地址的长度;p a g e l e n 表示文档的长度;u n 表示文档来 源的u r l :p a g e 存放该文档的内容。该结构充分考虑了h t m l 的特点,而且存放 方便。 2 3 2 索弓i ( 库) 网络蜘蛛将遍历时所获得的页面存放在数据库中。为了提高检索的效率, 需要按照一定的规则建立索引。6 0 0 9 l e 索引时,采用的是“倒排文件”技术。 很显然,如果索引不能及时更新,网络蜘蛛带回的新信息就不能被使用索引的 引擎的用户查到。也就是说,新信息更新周期等于网络蜘蛛停止工作的时间加 上遍历的时间再加上索引建立的时间。 相关数据结构描述如下: ( 1 ) 文本索引。文本索引需要按照一定的次序来保存每个文档的信息,以 便于信息的查找。在g o o g l e 中利用了固定长度的i s a m ( 索引序列访问模式) 进行索引,该索引按照d o c i d 进行排序。在每个索引条目中包含当前文本的状 态、一个指向信息库的指针、一个文本的检验值和一些统计信息。如果文本已 经被取回,则该条目还包含指向一个可变长度文件的指针,该文件包含文本的 u r l 和标题;否则,该指针指向一个u r ll i s t ( 只包含u r l ) 。这种数据结构 武汉理工大学硕士学位论文 可以保证数据的紧凑性和在搜索过程中能够通过一次查找就能取回记录。 另外,还有一个用来将u r l 转换成d o c i d 的对照文件。该文件包含了u r l 校验值和它相应的d o c l d 。该文件按照u r l 的校验值排序。为了能够方便地根 据u r l 找到对应地d o c l d ,首先计算该u r l 的校验值,然后根据二分查找法在 校验值文件中查找对应地d o c i d 。 ( 2 ) 采样表。在g o o g l e 中,文档中的每个词对应一个采样,采样包含该词 在该文档中的位置、字体和大小写信息。采样表在前向和后向索引中占据主要 的存储空间。因此高效编码是必须的。在这里,选择了即节省存储空间,速度 又比较快的紧凑编码法。 在紧凑编码法中,每个采样占用两个字节,如图2 4 所示。采样分为特定采 样和普通采样。特定采样包括出现在u r l 、标题、锚点文本和m e t a 标记中的采 样,其他采样统称为普通采样。在普通采样中,包含一个大小写位、3 个字体 大小位和用1 2 位表示的文档位置( 对于所有超过4 0 9 6 的位置都记成4 0 9 6 ) 。 字体通过相对表示法( 相对其他的文本) 表示,占据3 位( 由于1 1 1 表示该采样 为普通采样,因此字体大小只有7 种选择。在特定采样中,包含一个大小写位、 字体位设为7 表示该采样为特定采样,用4 位表示该特定采样的类型,用8 位 表示在文档中的位置。对于锚采样来说,8 位被分成两部分,其中4 位表示在锚 信息中的位置,另4 位表示出现该锚信息文档的d o e l d 的散列值。 为了节省存储空间,在前向索引中,采样表的长度和w o r d i d 结合起来存放; 在倒排序索引中,采样表的长度和d o c l d 结合起来存放。 l 普通采样大小写:1字体大小:3位置:1 2 l 特定采样大小写:17类型:4位置:8 l l 锚:大小写:1 7类型:4 散列值:4位置:4j 圈2 4 采样表的数据结构图 ( 3 ) 前向索引。前向索引是文档到词的索引,在处理文档的时候以文档为 单位建立这种索引比较方便。在g o o g l e 中,前向索引存放在“个存储桶中,每 个桶容纳一定范围内的w o r d i d 。如果一个文档包含的单词属于某个桶的话,那 么该桶首先记录该文档的d o c l d ,后面跟随w o r d l d 和对应的采样表。这种办法 将导致同一个w o r d i d 出现在不同的桶中,从而造成一定程度的空间膨胀。这种 武汉理工大学硕士学位论文 空间膨胀对于一定数量的存储桶来说不会太大,但是却可以大大提高索引阶段 的效率和减少编码的复杂性。由于各个桶存放一定范围之内的w o r d l d ,为节省 存储空间,只存储w o r d i d 相对于该桶中最小w o r d l d 的相对值,这种相对值可 以用2 4 位数据表示。 d o d dw b r d i :2 4 采样的个数:8采样采样采样采样 w b r d i d :2 4 采样的个数:8采样采样采样采样 w b r d i d :2 4 d o c i dw o r d i d :2 4 采样的个数:8 采样采样采样采样 w o r d i d :2 4 采样的个数:8采样采样采样采样 w o r d i d :2 4 采样的个数:8 采样采样采样采样 空w o r d l d 图2 5 前向索引的数据结构描述图 ( 4 ) 后向索引。前向索引便于建立,但是在信息查找过程中,是根据词来 找文档的,因此为了提高文档检索的速度,必须建立词到文档的索引,即后向 索引。在g o o g l e 的后向索引中,也包含了与前向索引类似的存储桶,如图2 6 所示。不同的是后向索引经过排序处理。对于每个有效的w o r d i d ,词典也包含 一个指向该w o r d l d 所在桶的指针。该指针指向一个d o c i d 的列表和与该w o r d i d 相关的采样表。该d o c l d 的列表包含所有出现该w o r d l d 所对应的词的文档。 w o r d in d o c s w o r d j dn d o c s b r 皿ln d o c s d o c i d :2 7i 采样的个数:5l 采样采样采样采样采样 d o c i d :2 7i 采样的个数:5j 采样采样采样采样采样 d o c l d :2 7l 采样的个数:5i 采样采样采样采样采样 d o c i d :2 7j 采样的个数:5l 采样采样采样采样采样 图2 6 后向索引的数据结构图 在后向索引中,一个主要的问题是如何对d o c i d 列表中的d o c i d 进行排序。 一种方法是简单地按照d o c l d 进行排序,该方法可以与实现多词查询时的d o c i d 列表合并;另一种方法是按照每个文档中该词出现的频率对d o c i d 列表进行排 序,该方法便于单个词的查询,而且在多词查询时很容易在d o c i d 列表的头部 武汉理工大学硕士学位论文 找到结果,但却不利于多个d o c l d 列表的合并。g o o g l e 采取了折中的办法,将 后向索引桶分成两类:一个存放标题或者锚信息的采样表,另一个存放所有的 采样表。如果在第一类桶中没有足够匹配结果的话,再在第二类桶中进行匹配。 ( 5 ) 其他方面。与其它搜索引擎相比,g o o g l e 的信息库中保存了更多的有 用信息。每个采样表包含位置、字体和大小写信息。另外,g o o g l e 还利用了 p a g e r a n k 技术;如果一个页面被多次引用,那么这个页面很可能是重要的;如 果一个页面尽管没有被多次引用,但却被一个重要的页面引用,那么这个页面 很可能是重要的;一个页面的重要性被均匀地传递到它所引用的页面。另外, g o o g l e 在计算查询串与文档相似度时,还充分利用了所保存的文档信息,比如 对于出现在标题、锚点和正文中的词条均赋予不同的位置权重,而对于不同的 字体大小也赋予了不同的权重。结果表明,用p a g e r a n k 技术与相似度函数相结 合对文档进行评价可以获得比较满意的结果。 索引过程: 为了加快信息检索的速度,g o o g l e 对信息库建立倒排索引。在建立倒排索 引时,着重考虑以下几个方面的问题: ( 1 ) 全文索引。g o o g l e 对信息库中的页面建立了全文索引,并且在建立索 引时,还同时考虑了超文本的不同标记所表示的不同含义,如粗体、大字体显 示的内容往往比较重要;放在锚链中的信息往往是它所指向页面信息的概括, 所以用它来作为它所指向的页面的重要信息。g o o g l e 还在建立索引的过程中收 集页面中的超链接,这些超链接反映了收集到的信息之间的空间结构,利用这 些信息可以提高页面相关度判别的准确度。 ( 2 ) 过滤无用词汇。网页中存在着许多对信息检索没有什么实际意义的词 汇,如英文中的“a ”、“a n ”、“t h e ”等,以及中文中的“的”、“啊”等,它们不 能明确表达网页的主题信息,因此没有必要对它们进行索引。g o o g l e 在建立索 引时,依据事先保存的一张无用词汇表,对网页中的无用词汇进行过滤。 ( 3 ) 对图象标记的处理。网页中存在着大量的图象信息,而图象检索技术 目前还不是很成熟。网页中的图象标记往往存放着图象的替换信息,这些信息 对相应的图象有一个基本的描述。g o o g l e 就专门针对这些图象的替换信息建立 了索引,以支持某种程度上的图象检索。 g o o g l e 具体建立索引的过程,可分为以下三个阶段: ( 1 ) 分析过程。该过程主要处理文档中可能出现的错误。这些错误包括: 1 4 武汉理工大学硕士学位论文 错误的h t m l 标记、非a s c i i 码字符、标记嵌套层次过深等。 ( 2 ) 对文档进行索引。经过分析的文档经过编码后被存进一个个存储桶中。 根据存放在内存中的词典( 散列表) ,文档中的每个词都被转换成对应的w o r d l d 。 然后将它们在文档中的出现情况转换成采样表,存放于前向桶中。并行索引可 以提高索引的速度,但并行索引的困难在于索引需要共享同一词典,而由于外 来词的存在,索引过程中需要对词典进行一定的修正。在g o o g l e 中,先不对外 来词汇进行索引,而是把它们记录在一个日志中,从而实现多个索引器的并行 处理,在所有的索引完成后,荐对这些外来词汇建立索引。 ( 3 ) 排序过程。为了生成最后的便于索引的后向索引,需要将前向索引存 储中的信息按照w o r d l d 排序,最后生成标题和锚点信息的后向桶以及一个全文 的后向桶。可以对桶逐个地进行排序,也可以并行处理,具体视系统资源而定。 由于一个桶不能全部存放于内存,g o o g l e 就按照w o r d i d 和d o c l d 适当地对桶进 行分割,然后进行排序,最后生成后向索引桶。 2 3 3 等级计算 影响搜索引擎性能的关键是网页页面排序算法。提高搜索引擎精确度就是 要研究最优的页面优先度算法,提供具有较高用户相关度的网页页面优先度排 序。目前多数搜索引擎采用了p a g e r a n k 算法作为页面优先度算法。1 4 j 互联网上数量巨大网页通过u r l 和锚点链接联系起来,形成庞大复杂的链 接网。我们将各个网页定义为点,并将链接的来源网页和目的网页用有向线段 联结起来,这样,整个互联网网页就形成有向图。根据有向图理论,所有结点 的出度和等于入度和,即所有网页的链接出度之和等于所有网
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 红日发展历程课件
- 红旗营销案例课件
- 核潜艇简介课件
- 红旗汽车培训课件
- 红旗动图课件
- 后勤类教学课件
- 红曲发酵技术课件
- 红旗案件介绍课件
- 航拍中国江西课件
- 2026及未来5年有光扎染短毛绒项目可行性研究报告(市场调查与数据分析)
- 2026福建福州旗山供水有限公司招聘2人考试模拟试题及答案解析
- 北京市朝阳区2026-2027学年度第一学期期中质量检测高三英语试卷(含答案)
- 2026山东省防疫安全协管员招聘考试(畜牧兽医)历年参考题库含答案详解
- 正大集团人才评估行测题目
- UL 9540A 2026 储能电池热失控传播测试标准中文版 模组防火试验规范
- 物业服务履约评价报告
- 光伏组件拆除方案
- 2026年出版社招聘考试面试题及参考答案
- 2025-2026学年江西省赣州市大余县部分高中高三上学期11月期中考试英语试题
- 小区物业消防安全培训课件
- 空乘课件教学课件
评论
0/150
提交评论