（计算机系统结构专业论文）搜索引擎检索技术研究.pdf

摘要 摘要 随着i n t e l n e t 迅猛发展，搜索引擎已经成为人们进行信息获取必不可少的工具。 检索技术作为搜索引擎的核心技术之一，对信息准确、快速地获取起到了至关重 要的作用。 本文在传统向量空间模型的基础上，提出了一种改进的向量空间模型，该模型 充分考虑了文档结构对词的重要性的影响，利用该模型进行相似度计算时，避免 了向量空间模型查全率和查准率不高的缺点。在检索模型和缓存技术研究基础上， 设计并实现了一个高效的检索系统，该检索系统包括查询器和缓存机制两个部分： 查询器实现了简单查询和复杂查询两种查询方式；缓存机制制定了基于l r u 和 l f u 的两种基本缓存策略，并采用哈希表缓存查找算法提高缓存查找效率。实验 结果表明本文设计的检索系统的检索性能和缓存性能，都达到了实用的水平。 关键词：搜索引擎检索模型查询器缓存机制 a b s l l - a c t a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fi n t e r n e t ，s e a r c he n g i n eh a sb e c o m e a l l i n d i s p e n s a b l et o o lf o rp e o p l et og e ti n f o r m a t i o n a st h ec o r et e c h n o l o g yo fs e a r c h e n g i n e ，r e t r i e v a lt e c h n o l o g yp l a y sa ni m p o r t a n tr o l ei ng e t t i n gi n f o r m a t i o na c c u r a t e l y a n dr a p i d l y b a s e do rt h es t u d yo ft r a d i t i o n a lr e t r i e v a lm o d e l s ，t h ep a p e rb r o u g h tf o r w a r da m o d e lw h i c ht o o kf u l lc o n s i d e ro ft h ei m p o r t a n c et h a tf i l es t r u c t u r et ot h ew o r d s i t a v o i d e dt h es h o r t c o m i n g so fl o wa c c u r a t ea n de n t i r eq u e r yr a t ew h e nu s i n gt h em o d e lt o c a l c u l a t et h es i m i l a r i t y b a s e do nt h es t u d yo f r e t r i e v a lm o d e la n dc a c h et e c h n o l o g y ，t h e p a p e rd e s i g n e da n di m p l e m e n t e d a ne f f i c i e n tr e t r i e v a ls y s t e mw h i c hi n c l u d e dq u e r ya n d c a c h em e c h a n i s mf o rt h et w op a r t s ：t h eq u e r yh a ss i m p l ea n dc o m p l e xr e t r i e v a lm e t h o d s ； t h ec a c h em e c h a n i s mm a d et w ob a s i cc a c h es t r a t e g i e sb a s e do nl r ua n dl f u ，a n di t a l s ou s e dt h ec a c h eq u e r ya l g o r i t h mo fh a s ht a b l et o i m p r o v ee f f i c i e n c y t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h er e t r i e v a la n dc a c h ep e r f o r m a n c eo ft h er e t r i e v a l s y s t e mh a sr e a c h e dap r a c t i c a l1 e v e l k e y w o r d ：s e a r c he n g i n e r e t r i e v a lm o d a l q u e r y c a c h em e c h a n i s m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：迦墨：! ：芏 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 日期：堡兰：! ： 日期：2 1 1 堡：! ! ! 呈 第一章绪论 第一章绪论 l 。1 课题研究的霹的和意义 随着i n t e m e t 的迅速发展，社会信息化的推进和网络应用的日益广泛，w e b 已 经成为存取信息的主要平台。它允许任何人、在任何地点、任何时间传播和获取 信息；用户既是信息消费者，又是信息的生产者。这一机制为信息在全球范围发 布和传播提供了机会，同时也弓| 发了“信息爆炸。全球用户量最大的搜索弓| 擎 g o o g l e 在其网站上标明已索引了8 1 亿个网页【l 】，中国互联网络信息资源的第1 5 次数量调查显示，截至2 0 0 4 年1 2 胄底，中篱域名数量首次突破百万大关，全囡 网站达到6 6 9 万个，网页总数超过3 亿个，网民已达9 4 0 0 余万，使用宽带上网的 就达4 2 8 0 万【2 】。 人们在利用w w w 过程中，最主要的获取信息资源的途径是借助搜索引擎来 实现。c n n i c ( q b 囤互联网络信息中心) 于2 0 0 4 年1 2 月发布的中国互联网络发展状 况统计报告的最新统计资料表明【2 】，有8 5 的入是通过搜索雩 擎发现新黼站的，在 经常使用的网络服务中搜索引擎占7 0 ，仪次于电子邮件。美国著名网络评估公 司尼尔森公司2 0 0 4 年1 2 月2 3 尽公布的最新报告显示，今年l o 月闻有l 亿美匿 人，即美国全国人口的3 9 ，网民总数的7 6 使用了搜索引擎网站，平均每人的 使用时闯为4 0 分钟。其中，5 2 的网民在使用搜索弓| 擎时最重视信息内容的相关 性，3 4 最重视信息内容的可信度。由于网络存在大量的、分散的信息，人们在搜 索自己需要的信息时，需要花大量的时间等待或是判断，才能筛选出部分重要的 相关信息。w w w 信息检索成为一个重要而又困难的问题，因此，网络信息检索 成为目前的一个热门研究课题。有不少研究活动讨论如何增进搜索结果的精确度， 或者加快用户找到相关重要阙页的速度】。 我国i n t e m e t 发展非常迅速，中国教育和科研计算机网目前己经链接3 0 0 余所 高等院校，是国内信息资源特别是中文信息资源最为丰富的麓络。但是中文信息 的查询技术还不成熟，尤其是在教育网上缺少查询系统，这给用户查找信息资源 带来很大的困难，因此，如何快速、有效、经济地从海量信患资源中检索到用户 所需要相关的准确信息，同时以一个方便用户浏览的界面显示出来，成为当前一 个非常重要的研究热点。 检索系统是搜索引擎中提供查询服务的模块，通过w e b 页面的方式为客户提 供查询服务，直接决定了用户可以获得的服务质量以及对搜索引擎的满意度。检 索系统是在大量的索弓| 数据中进行查找，将找到的结果按网页的重要程度依次显 2 搜索引擎检索技术研究 示给用户。其中为了提高系统性能，还需要缓存机制4 。当缓存中有数据与用户 的查询请求匹配时，不必在索引数据中检索，直接返回结果。因此，检索系统在 搜索引擎中具有重要作用。高效，实用的检索系统，不仅适用于搜索引擎，也能 用于其它相关的检索领域，无论从技术角度还是市场角度，都有十分重要的意义。 本文的重点就集中在查询器的设计与实现以及高效缓存机制的设计。 1 2 国内外研究现状 网上信息以爆炸的速度不断丰富和扩展，如何在上西万个网站中快速有效地 找到自己想要的信息，是i n t 锄e t 用户面对的突出问题。搜索引擎( s e a r c he n g i n e ) 正是针对这个问题而出现的，并成为i n t e m e t 用户查找信息和站点的重要方法。 i n t a n e t 上有三类工具帮助查找和定位信息资源： ( 1 ) 层次或目录( d i r e c t o r ) ：目录通常是由人工收集站点，按字母、学科或时间、 缝理区域等放置各鼙录下。由于人工的参与，强录逶常有较好的查询喃廒。例如 y a h o o 。 ( 2 ) 搜索弓| 擎( s e a r c he n g i n e ) 【s 】：也称作“s p i d e r 摊壮c r a w l e r s ”网，它以种自动 的方式收集信息资源并对其索引。由于信息量大，覆盖面广，能收集到一些目录 没有的站点。 ( 3 ) 元搜索引擎【1 弼【l l 】：实际上是一种智能中间代理，它对关键字迸行处理，向 一些最为流行的搜索引擎提交查询要求。对返回结果排序【1 2 1 ，除去重复的响应。 哥前已经有的元搜索弓| 擎有d o g p d e , i n f e r e n c ef i n d , m e t ac r a w l e r 及清华大学的 m e t a s e a r c h 等。 s t a n f o r d 大学在其d l i 项露中开发了g o o 酋e 接索孳| 擎，在w 曲高效搜索、大 规模索引、文档的相关度评价等方面作了深入的研究，提出了一种基于链接分析【l 3 】 f 1 4 】【1 5 】的网贾排名算法( p a g e r a 藏必1 6 】f 1 7 】【1 8 】算法) 来计算网页的排名，并同时利用锚文 本( a n c h o r s ) 信息进行网页相关度评价。i b m 研究中心研制了c l e v e 系统，由 k l e i b e r g 1 9 】提出了类似于p a g e r a n k 的h i t s 2 0 】( 2 l 】【2 2 1 算法，主要不同是将网页分为 a u t h o r i t y t 2 3 】渊和h u b 两类f 2 5 】，并就h i t s 算法在相关度f 2 弼评价、网页分类、主题 搜索等方面的作用进行了研究。除了p a g er a n k 和h i t s 算法外，还由r l e m p e l 和s m o r a n 提出了s a l s a 算法瑟强，该算法考虑了用户回退测览网页的情况，保留 了p a g e r a n k 的随机漫游和h i t s 中把网页分为a u t h o r i t y 和h u b 的思想，但取消 a u t h o r i t y _ 和鞭曲之闻的相互加强关系。n e c 美因研究所开发了一个专门用予搜索 学术文章的r e s e a r c hi n d e x 。其目的是建立一个网上图书馆，只收集科技人员广泛 使用的p d f 秘p o s t s c r i p t 文件，用“p d f 蚪，”p o s t s c r i p t 等检索项组成查询送往其他著 名的搜索引擎，对返回的结果进行信息提取( 主题、摘要、作者、引用文献等) ，组 第一章绪论 3 成了一个2 7 万篇文献的索引库，供科技人员查询。现在，n e c 开始致力于下一代 元搜索引擎i n q u i r u s 的开发。 国内先后有北京大学、清华大学、华南理工大学、国家智能研究中心等高校 和研究单位对搜索引擎技术进行了研究，开发出了几个实用的系统。清华大学开 发的“网络指南针”，利用智能、高效的网络搜索算法收集网页，自动识别和转换常 见的中文编码，向用户提供中文、英文、拼音、英汉翻译、b i g 5 码等多种输入查 询服务，并提供普通分类、学科分类、图书分类查询，共计3 , 9 0 0 多个分类目录， 收集的网页超过2 0 万页。北大的“天网”中英文搜索引擎，在系统规模及系统性能 方面达到了国外中型搜索引擎系统的技术水平，拥有1 0 0 万网页、1 4 万n e w s 文章 和7 万邱文件，在功能、性能、查准率、查全率等方面基本达到了实用。华南理 工大学的“木棉”搜索引擎，分w e b 检索和f t p 检索两大部分。w e b 检索支持中英 文混合查询、布尔查询、结构属性查询、模糊查询等多种查询方式。f t p 检索实 现基于文件主要属性的结构查询，以及模糊匹配等。目前系统收集约5 0 万网页。 经过了多年的发展之后，现在的搜索引擎功能越来越强大，提供的服务也越来越 全面。据研究统计，目前i n t e m e t 上搜索引擎已达数千种之多。随着多元化信息的 增长，统一的用户入口己经不能满足用户的更深入的查询需求，搜索引擎将向智 能化、个性化、精确化、专业化、交叉语言检索、多媒体检索等适应不同用户需 求的方向发展。 随着中文网络的发展，人们对中文信息查询提出要求。目前中文搜索站点日 益增多，国内的百度、网易、c n n i c 等许多公司或机构都推出了自己的产品，y a h o o 、 g o o g l e 等世界著名厂商也开始提供中文服务。对于一个成功的搜索引擎来说，高 性能的检索系统是必不可少的。中文搜索引擎还处于起步阶段，为了能够给用户 提供更好的中文信息查询服务，如何设计高性能的检索系统，显得尤为重要。 1 3 论文的主要内容和贡献 在搜索引擎系统中，检索模块是向用户提供查询服务的，是唯一与用户交互 的模块，直接决定了用户对搜索引擎产品的满意度。本文对信息检索模型进行了 研究，设计并实现了一个检索系统。下面将本文所做主要工作概括如下： ( 1 ) 分析和研究了相关的搜索引擎技术和网络缓存脚 1 2 9 1 3 0 技术的算法； ( 2 ) 研究了搜索引擎的结构，对检索系统的功能进行了详细分析。首先要分析 用户的查询表达式，然后进行检索运算，最后提交查询结果。 ( 3 ) 研究多种信息检索模型，分析其优缺点，结合实际应用提出了一种改进的 向量空间模型。研究了查询器的各种技术，对查询器的工作流程进行分析，设计 并实现了一个高效的查询器； 4 搜索引擎检索技术研究 ( 4 ) 设计了一种缓存机制，该机制包括缓存区和缓存区管理器两个部分。研究 了多种缓存替换策略，提出了适合本系统的两种基本缓存策略。对缓存区以及缓 存区管理器进行详细设计。 ( 5 ) 检索性能和缓存性能分析。 1 4 论文结构 本文共分为五章： 第一章绪论。提出论文研究的对象以及国内外相关研究发展现状，介绍本文 所做工作及其意义。 第二章搜索引擎技术。对搜索引擎的工作原理，分类以及体系结构等方面做 简单介绍。并对搜索翠| 擎的关键技术进行简要叙述。 第三章信息检索模型。本章研究了传统的信息检索模型，在向量空间模型的 基础上，提搬了一种改进的向量空阆模型。利用该模型进行相似度计算，避免了 向量空间模型查全率和查准率不高的缺点。试验结果也表明，该模型具有更高的 查全率和查准率。 第四章检索系统的设计与实现。本章对检索系统进行了设计与实现。首先， 详纲分析了查询器的功能，并针对其功能做了详细的分析设计。采用了动态摘要 算法以及共事内存区技术，实现了高性能的查询器。然后，详细分析了搜索引擎 检索系统中缓存的系统结构，包括缓存区管理器和缓存区。在设计缓存去管理器 时，制定了基于l r u 思怒和l f u 思想两种最基本的缓存置换策略，并采用了基于 哈希表查找的查找算法。详细设计了缓存区的结构，它既是一个哈希表又是一个 双向链表。最后进行? 缓存性能测试和系统性能测试。 第五章结论与展望。对全文所做工作进行总结，并提出需要改进之处和进一 步研究方向。 第二章搜索引擎技术 第二章搜索引擎技术 2 。1 搜索引擎的分类 搜索引擎是指运行于i u t e r n e t i u t m n e t 上，以i n t e m e t i n t r a n e t 网络的各种信息 资源为对象，以信息检索方式提供用户所需信息的数据库服务系统。搜索引擎的 基本概念出现于2 0 世纪2 0 年代，但它的真正发展和应用却是2 0 世纪9 0 年代的 事情，特别是在2 0 世纪9 0 年代中期得到快速的发展，现在墨成为网络上的研究 热点和重要组成部分。根据搜索引擎使用的技术，现在的搜索引擎主要分为三大 类：冒录式搜索弓| 擎，机器人搜索弓| 擎和元搜索雩| 擎。 2 1 1 目录式搜索引擎 目录式搜索引擎【3 u ( 也称分类式搜索引擎) 主要通过人工发现信息，由编辑人 员根据信患资源熬内容按定的主题进行分类组织，并形成信怠摘要，将信息置 于事先确定的分类框架中，组织成一层一层的分类目录，目录下面有更具体的子 墨录。信息的类别也由大到小、由粗到细，整个搜索引擎形成了一个层次型的类 别目录。用户可以逐层浏览，选择不同的主题对网络信息进行过滤，所选择的主 题类别越小，信息的相关性就越高，用户就越有可能找到自已所需要的信息。这 类搜索引擎的性能主要取决子对所获取网页的人工麴类或自动分类算法的精确度 如何。其代表有：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 , g og u i d e 等。例如，中文雅虎 ( y a h o o ) 有1 4 个一级目录，最深有6 级子霉录，其使用的是手工录入方式得到w e b 页面摘要信息，而非全页面内容信息。其形成的具体方式是：首先维护人员对新 w e b 站点进行浏览，然蜃对测览内容进行杰容提取，并形成摘要信息和关键字， 最后将这些信息分类进行存储。由于y a h o o 的普及程度非常高，因此现在y a h o o 系统的维护人员不再需要到i u t e r n e t 上去寻找新w e b 站点，面是由新w 曲站点灼 发布者主动通过页面提交本站点的有关信息，系统的维护人员只需要对这些提交 的信息进行归类存储，然质对外发布公开。 y a h o o 给用户提供了两种查询方式：漫游查询和关键词自动搜索。漫游查询即 用户利用浏览器在y a h o o 的w e b 页面上按燕题目录进行逐层深入地查找所需要的 内容信息。关键溺自动援索方式是系统根据用户提交的查询关键词，尝动对冒录 树结构进行搜索查找，返回符合条件的结果集。 目录式搜索孳l 擎的突出特点是具有比较好的信息质量，但由于采用手工进行 6 搜索引擎检索技术研究 w e b 页面信息的获取和维护，所以存在以下不足： ( 1 ) 信息覆盖率低，信息实时更新不够及时，目录维护耗费的入力资源大。 ( 2 ) 基于关键词而非全文进行查询，可能在查询时造成某些相关信息的遗漏。 ( 3 ) 采用漫游查询方式的效率不高，并且由于目录查询树结构的不断增大，查 询莱一特定主题的代价和时闻开销会越来越大。 为了解决目录式搜索引擎存在的问题，人们引入了人工智能技术，用机器人( 也 称之力r o b o t , s p i d e r , w a n d e r e r , w o r m ) 代替手王去发现、加工、整理信息，这样就 出现了机器人搜索引擎。 2 1 2 机器入搜索引擎 为了解决叠录式搜索弓| 擎存在的阕题人们引入了人工智能技术用机器人代替 手工去发现加工整理信息这样就出现了机器人搜索引擎，机器人搜索引擎【i o 】不需 要入工收集信息而是由一个被称作“机器人 的计算机程序在网络上不停地爬行 和搜索，依据一定的网络协议在i n t e r n e t 中自动获取网页信息并通过对网页内容和 特征的分析采用一定的策略组织信息并建立自墨的索引数据库为用户提供查询服 务。h o t b o t ，i n f o s e e k ，g o o g l e ，e x c i t e 、天网等就是这类检索系统的典型代表。本文 设计的检索系统就是基于机器人搜索引擎的。 2 1 3 元搜索引擎 由于单个搜索引擎的覆盖范围往往不会太广，为了找到自己所需要的信息， 用户常常需要使用多个搜索引擎，以期望找到更多、更全、更准确的信息。但由 于不同的搜索弓l 擎在其查询语法以及接口界面上往往不同，需要用户重新学习和 适廒不同的检索方法，这给用户使用多个搜索引擎带来了极大的不便。为了解决 这个闯题，研究人员开发了元搜索雩| 擎。元搜索雩| 擎统一了不同搜索弓| 擎的查询 接口，由统一的元搜索引擎接口对用户提交的查询请求进行处理，分别将其转换 为符合底层搜索引擎查询语法要求的子查询，嗣时淘多个搜索弓| 擎提交查询的结 果，由底层搜索引擎在各自的索引数据库中进行查询。在各个搜索引擎返回检索 结果后，元搜索引擎将子查询结果进行汇总、去重、重耨排序等处理，最后向用 户返回最终的检索结果【3 2 】【3 3 】。 元搜索引擎系统一般都没有自己的索引数据库，而是以一个代理的兔色，利 用其它搜索弓| 擎的数据库来进行服务。在层次上，元搜索弓| 擎要比机器入搜索引 擎和目录式搜索引擎要高。元搜索引擎系统的底层搜索引擎可以是机器人搜索引 擎，也可戬是霹录式搜索弓l 擎。元搜索弓| 擎的优点是返露结果的信息量更大、更 第二章搜索引擎技术 7 全，其查全率较高，解决了单个搜索引擎覆盖范围相对狭窄的局限，缺点是不能 够充分利用下层搜索引擎的排序功能，用户需要做更多的筛选。这类搜索引擎的 代表是m e t a c r a w l e r ，s a w y s c a r c h ，l n f o m a r k e t 等，例如，m e t a c r a w l e r 可以同时检 索九个搜索引擎，有y a h o o ，o p e n t e x t ，l y c o s ，w e b c r a w l e r , l n f o s e e k , e x c i t e ，l n k t o m i ， g a l a x y , a i t a v i s t a 等，在各个搜索弓| 擎返回检索结果焉，经过去重，再掇据它童己 的相关度排序算法 3 4 1 3 5 】进行结果重排。 2 2 搜索引擎的工作原理和体系结构 2 2 1 搜索弓l 擎的王作原理 以机器人搜索弓l 擎为例。机器人搜索引擎豹工雅过程分为三大步：是在网 上发现信息，如m 删网页、n e w s g r o u p 文章、f t p 文件等等；二是把发现的信息 收集到本地，经过信息分类和索弓| 等加工处理把信息存储在本地数据库；三是提 供服务，即通过相应的算法和接口在本地数据库中查找到信息，并以一定的形式 返回给用户。 搜索弓l 攀主要由三个模块组成，分别为搜集模块，预处理模块和服务模块。 搜索引擎三段式工作流程如图2 1 所示。 图2 1 搜索引擎三段式工作流程 其中搜集模块即为网页搜集，由网络爬取器自动完成。预处理是对抓取到的 原始网页数据进行索引处理，获得索引数据库。服务指的就是检索系统，为用户 提供查询服务。 2 2 2 搜索雩| 擎的体系结构 由图2 2 可知，搜索引擎主要由搜集器，索引器，检索器，目志分析器组成。 搜索引擎先由搜集器到网上搜集网页原始数据，然盾由索引器对原始数据进行处 理，建立索引数据库，最后由检索系统向用户提供查询服务。这其中还有日志分 析器对过程进行记录，便于目后对用户行为进行分析，获得有用信息，有动于改 进系统。 搜索引擎检索技术研究 2 3 1 网络爬虫技术 圈2 2 搜索引擎体系结构 2 3 相关技术 网络爬虫( 又称r o b o t ) 【3 6 】 3 7 】是个特殊的w w w 客户端程序，主要工作是 访阍并读取w e b 页面，然后跟随链接进入其他w e b 页惹。r o b o t 定期( 如每个月 或每两个月) 返回到同一个站点中寻找发生的变化。r o b o t 从一个事先制定好的 u r l s 列表出发，这个列表中的u r l s 通常是从以往访问记录中提取出来的，特别 是一些热门站点和新阚页，从u s e n e t 等地方检索得到的u r l 列表也常被用作起始 u r l 列表，此外，很多搜索引擎还接受用户提交的u r l 列表，这些u r l 列表也 会被安排在列表中供r o b o t 访阂。r 曲访闻了个网页后，会对它进行分析，提 取出新的u r l ，将之加入到访问列表中，如此递归地访问w c b 。r o b o t 作为一个 程序，可以用c 、p e r l 、j a v a 等语言来编写，可以运行在u n i x 、s o l a r i s 、w i n d o w s 、 n t 、o s 2 和m a c 等平台上。r o b o t 设计是否合理将直接影响它访问w e b 的效率， 影响搜索数据库的质量，另外，在设计r o b o t 时还必须考虑它对网络和被访问站 点的影响，因为r o b o t 一般都运行在速度快、带宽高的主机上，如果它快速访问 第二章搜索引擎技术 9 一个速度比较慢的目标站点，就有可能会导致该站点出现阻塞甚至当机。r o b o t 还 应遵守些协议，以便被访闯站点的管理员能够确定哪些内容能被访问，哪些不 能。 站点爬行是r o b o t 技术中最关键的一部分。爬行是寻找站点上所有用户可以 访问的网页的过程。r o b o t 从一个地蛙开始，寻找该页嚣上的链接，然焉r o b o t 重 复它在第一页发现链接的过程。在爬行过程中必须主要解决几个问题：消除重复、 辨别类型、限割范匿、限制深度。网页中通常存在着相互链接，指惫圭页的链接 也是常见的。站点爬行时对页面重复处理可能使r o b o t 陷入死循环中。所以一般建 立一个已访问u r l 的列表，在处理新链接前先检查此表。有时链接指向的不是h t m l 文档，可能指向图片或应用程序。这就要求r o b o t 具有不同类型不同处理的要求。 另外，还需限制r o b o t 的爬行范围，一般r o b o t 只处理指向同一服务器的链接。对 于某些信息层次穰深的站点应设定r o b o t 的爬行深度，以便r o b o t 能自动结束对此 站点的爬行。 我翻考虑摄取的时机；事先还是鄂时。我们都有经验，在网络比较畅通的情 况下，从网上下载篇网页大约需要1 秒钟左右，因此如果在用户查询的时候即 时去网上抓来成千上万的网页，一个个分析处理，和用户查询匹配，不可能满足 搜索引擎的响应时间要求。不仅如此，这样做的系统效益也不高( 会重复抓取太 多的网页) ，面对大量的用户查询，不可能想象每来一个查询，系统就到网上“搜 索”一次。 因此，我们可以看到，大规模搜索引擎服务的基础应该是一批预先搜集好的 网页。在具体的搜集过程中，如何掇取一篇一篇的的网页，也可以有不同的考虑。 最常见的一种是所谓“爬取”：将w e b 上的网页集合看成是一个有向图，搜集过程 从给定起始u r l 集合s ( 或者说“种子”) 开始，沿着网页中的链接，按照先深， 先宽或者某种别的策略遍历，不停的从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 ) 。 这种方式的一个困难是要从每一篇网页中提取出所含的u r l 。由于h t m l 的灵活 性，其中出现u r l 的方式各种各样，将这个环节徽褥彻底并不容易。另外一种可 能的方式是在第一次在全面网页搜集后，系统维护相应的u r l 集合s ，往后的搜 集直接基于这个集合。每搜刭一个潮页，囊暴它发生变化并含有新的u r l ，则将 它们对应的网页也抓回来，并将这些新u r l 也放到集合s 中；如果s 中某个u r l 对应的网页不存在了，则将它从s 中删除。这种方式也可以看成是一种极端的先 宽搜索，即第一层是一个很大的集合，往下最多只延伸一层。 1 0 搜索引擎检索技术研究 2 3 2 索引技术 信息索引就是从已发现的网页中提取一些特征，以便用户很容易地检索到所 需的信息。即通过一定的方法产生一个索引项集合来作为一篇文档或查询请求的 内部表示。 索引的方法主要分为两种：一种基于关键词的索引；另一种是基于概念的索 引。第一种是大多数搜索引擎使用的方法，是从文档中提取重要的词作索引。在 文档中项部出现的词以及在整个文档中出现多次的词可以认为是比较重要的。第 二种方法与前种不同之处在于试着了解语义，用一个词能代表许多意义相近的词， 这样既节省了索引空间，也为检索时可返回有关主题的所有文档，甚至这些文档 中的词与检索词并不精确匹配。e x c i t e 是当前网络中比较著名的基于概念检索的搜 索引擎。 本论文中仅介绍基于关键词的全文索引，也就是对每篇文档全文提取关键词 进行索引。建立索引需要进行两方面的技术处理：关键词的提取，建立倒排文档 索引【3 8 】【3 9 】【4 0 】。 分词就是从每个页面文档中提取一定数量的关键词或者知识。为了提取关键 词或知识，必须分割出单个词或句子。可以通过对英文文章或句子的语法和语义 分析来提取出该文章的主要意思。但这些方法都是基于英文本身就有明显的词间 分割这个事实上的，因而英文根本不存在分词问题。但对于汉语等无明显词间隔 的语言来说，必须要先对原文进行分词，然后再提取它。 中文分词【4 l 】技术属于自然语言处理技术范畴，对于一句话，人可以通过自己 的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解，其处理过程就 是分词算法。现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于 理解的分词方法和基于统计的分词方法。 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一 个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成 功( 识别出一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和 逆向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最 短) 匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与 标注相结合的一体化方法。由于汉语单字成词的特点，正向最小匹配和逆向最小 匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧 义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使 第二章搜索引擎技术 用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。实际 使用的分词系统，都是把机械分词作为- 种初分手段，还需通过利用各种其它的 语言信息来进一步提高切分的准确率。 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其 基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信怠来处 理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。 在总控部分的协调下，分词子系统可以获撂有关词、句子等的句法和语义信息来 对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用 大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信 息组织成机器可宣接读驳的形式，因此蟊前基于理解的分词系统还处在试验阶段。 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可麓构成一个词。因此字与字相邻共现的频率或概率毙够较好 的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互现信息。定义两个字的互现信息，计算两个汉字x 、y 的相邻共现 概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阂 值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进 行统计，不需要切分词典，因而又靖皤做无词典分词法或统计取词方法。但这种方 法也有定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例 如“这一”、“之”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差， 时空开销大。实际应用的统计分词系统都要使用部基本的分词词典( 常用词词 典) 遴行串匹浆分词，同时使用统计方法识别一些新的词，帮将串频统计和串匹 配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词 结合上下文识别生词、自动消除歧义的优点。 目前在自然语言处理技术审，中文处理技术比西文处理技术要落后很大段 距离，许多西文的处理方法中文不能直接采用，就是因为中文必需有分词这道工 序。中文分词是其他中文信息处理的基础，搜索弓l 擎只是中文分词的一个应用。 其他的比如机器翻译( m t ) 、语音合成、自动分类、自动摘要、自动校对等等， 都需要用到分词。因为中文需要分词，可缝会影响一些研究，僵同时也为一些企 业带来机会，因为国外的计算机处理技术要想进入中国市场，首先也是要解决中 文分词闻题。在中文研究方面，相毙乡 莺人来说，中国人有十分明显的优势。 1 2 搜索引擎检索技术研究 分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再 高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页， 如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索 引擎来说，分词的准确性和速度，二者都需要达到很高的要求。目前研究中文分 词的大多是科研院校，清华、北大、中科院、北京语言学院、东北大学、i b m 研 究院、微软中国研究院等都有自己的研究队伍，而真正专业研究中文分词的商业 公司除了海量科技以外，几乎没有了。科研院校研究的技术，大部分不能很快产 品化，而一个专业公司的力量毕竟有限，看来中文分词技术要想更好的服务于更 多的产品，还有很长一段路。 一个文件要建立倒排索引，就先把它抽成纯文本的格式，然后把一个一个的 单词切割出来，每个单词在索引数据文件里是一条记录，单词作为关键字，后面 跟着文件的标识i d ，文档的重要程度等。其实原理很简单。 假设有3 篇文章，f i l e l ，f i l e 2 ，f i l e 3 ，文件内容如下： f i l e l ( 单词1 ，单词2 ，单词3 ，单词4 ) f i l e 2 ( 单词a ，单词b ，单词c ，单词d ) f i l e 3 ( 单词1 ，单词a ，单词3 ，单词d ) 建立的倒排索引就是这个样子： 单词1 ( f i l e l ，f i l e 3 ) 单词2 ( f i l e l ) 单词3 ( f i l e l ，f i l e 3 ) 单词a ( f i l e 2 ，f i l e 3 ) 在使用索引进行查找时，首先对需要索引的文档进行预处理，建立关于这些 文档的索引结构。倒排索引技术在当前大多数的信息检索系统中得到了广泛的应 用，它对于关键词的搜索非常有效，在l u c e n e 中也是使用的这种技术。 2 3 3 排序技术 网页创建了一条指向其它网页的超链接，特别是指向另一网站的超链接，包 含了一种有价值的人为判断，它表明了两个网页之间内容的相关性和延续性。如 果把网页和网页上的超链接看作是一个有向图的点和边，则互联网就是一个巨大 的有向图，在这个有向图上，同一主题的网页之间的链接密度远远大于不同主题 网页之间的链接密度。于是，依据主题的不同，互联网形成了一个个内部耦合紧 密，外部疏松的网络社区。同样地，在网络社区中，与主题相关的权威页面的链 接密度大于一般的页面。如果能够通过分析有向图的链接情况得到这些权威页面 以及它们的排名，就可以提高搜索引擎的检索质量。基于结构分析的基本思想就 第= 章搜索引擎技术 是充分利用超链接结构所包含的这种信息。常用的超链分析算法有两种：p a g e r a n k 和h i l l t o p 。 1 p a g e r a n k 算法 p a g e r a n k 的原理类似予科技论文中的弓| 用机制：谁的论文被弓| 用次数多，谁 就是权威。说的更白话点：张三在谈话中提到了李二，李四在谈话中也提到李 李二，王五在谈话孛还提到李二，这就说萌李二一定是缀有名的入。在嚣联网上， 链接就相当于“引用”，在黔网页中链接了a ，相当于b 在谈话时提到了a ，如果 在c 、d 、e 、f 中都链接了a ，那么说明a 鼹页是最重要的，a 网页的p a g e r a n k 值也就最高。如何计算p a g e r a n k 值有一个简单的公式： 薅页a 缀鬟= ( 1 一系数) + 系数( 两淼+ 两淼“一 式( 2 1 ) 网页n 级别、 网页n 琏出个数 其中：系数为一个大于0 ，小于1 的数。般设置为o 8 5 。网页1 、网页2 至 踺页n 表示所有链接指向a 的网页。由以上公式可以看出三点： ( 1 ) 链接指向a 的网页越多，a 的级别越高。即a 的级别和指向a 的网页个 数威正比，在公式中表示，n 越大，a 的级别越高； ( 2 ) 链接指向a 的网页，其网页级别越高，a 的级别也越商。即a 的级别和指 向a 的网页自己的网页级别成正比，在公式中表示，网页n 级别越高，a 的级别 也越高； ( 3 ) 链接指向a 的网页，其链出的个数越多，a 的级别越低。即a 的级别和指 向a 静网页叁己的瘸页链逸个数成反比，在公式孛现实，两页n 链出个数越多， a 的级别越低。 每个隧页有一个p a g e r a n k 值，这样形成个巨大的方程缀，对这个方程组求 解，就能得到每个网页的p a g e r a n k 值。互联网上有上百亿个网页，那么这个方程 组就有上百亿个未知数，这个方程晟然是有解，但计算毕竟太复杂了，不可能把 这所有的页面放在起去求解的。 总之，p a g e r a n k 有效地利用了瓦联网所拥有的庞大链接构造的特性。从网页 a 导向网页b 的链接，用g o o g l e 创始人的话讲，是页面a 对页面l j i 的支持投票， g o o g l e 根据这个投票数来判断页面的重要性，但g o o g l e 除了看投票数( 链接数) 以外，对投票者( 链接的页面) 也进行分析。重要性高的页露所投的票的评价会 更高，因为接受这个投票页面会被理解为重要的物品。从新浪、雅虎、微软的首 页都有我网页的三个链接的话，可能毙我在其它网站找三十个链接还强。 1 4 搜索引擎检索技术研究 2 h i l l t o p 算法 其实h i l l t o p 算法的指导愿怒和p a g e r a n k 麴是一致豹，都是通过隧页被链接 的数量和质量来确定搜索结果的排序权重。但h i l l t o p 认为只计算来自具有相同主 题躲相关文档链接对于搜索誊的价值会更大：郾主题相关网页之闻的链接对于权 重计算的贡献比主题不相关的链接价值要更高。如果网站是介绍“体育”的，有1 0 个链接都是从“体育”相关的网站链接过来，那这l o 个链接比另外l o 个从“电器” 相关网站链接过来的贡献要大。b h a r a t 称这种对主题有影响的文档为“专家文档， 从这些专家文档页面到目标文档的链接决定了被链接网页“权重得分”的主要部分。 p a g e r a n k 结合h i l l t o p 算法确定网页与搜索关键词的匹配程度的基本排序过 程取代了过份依靠p a g e r a n k 的值去寻找那些权威页面的方法。这对于两个具有同 样圭题焉且p r 楣近的网页撵序过程中，h i l l t o p 算法就显得非常的重要了。h i l l t o p 同时也避免了许多想通过增加许多无效链接来提高网页p a g e r a r t k 值的做弊方法。 相关性是指搜索词和页瑟的相关糕度。仅仅通过链接、字体、位置等表面特 征，不能真正判断搜索词和文章的相关性，更何况许多时候这些特征不会都同时 存在。这也是许多对搜索引擎做弊方法能有效的原因。另外，有些文章中没有出 现搜索词，但说的就是和搜索词十分相关的内容。表面特征只能治标，不能治本。 治本的方法应该是增加语义理解，例如主题词和关键词的提取，从语义上分析， 得獭搜索词和网页的相关程度，分析的越准，效果就会越好。搜索弓| 擎的排序技 术应该也会朝着解决这两个不足的方向发展：语义相关性和排序个性化。前者需 要完善的自然语言处理技术，后者需要记录庞大访闻者信息和复杂的计算。 2 3 。4 缓存技术 1 缓存技术原理及分类 缓存技术是提高系统性能和可扩展性的一种重要手段，在计算机各个领域都 有广泛应用。缓存技术最先应用于p c 机中，是一种硬件设备，用于减少c p u 与 内存之间的速度差异。p c 祝在慢速的内存和快速c p u 之阆插入速度较快，容量较 小的s 删，起到缓冲作用，使c p u 既可以较快速度存取s r a m 中的数据，又不 使系统成本上升过高，这就是缓存技术。 缓存技术的有效性建立在被缓存对象访问序列存在的局部性特征上，包括时 间局部性和空间局部性。时间局部性指的是过去经常被访闯的对象在将来也可能 被褥次访问，或者说最近被访问的对象更有可能在将来被再次访问；空间局部性 指的是与过去经常被访问的对象“相邻”的对象在将来可能被访问。具有时间局 部性的访问行为可以从缓存中得到好处，而具有空间