（计算机软件与理论专业论文）搜索引擎的研究与实现.pdf

兰州大学硕士研究生毕业论文 摘要 r s s ( r e a l l ys i m p l es y n d i c a t i o n 简单信息聚合) ，也可以称为r i c hs i t e s u m m a r y ”( 丰富站点摘要) ，或”r d fs i t es u m m a r y ( r d f 站点摘要) 已被广泛接 受和应用，丰富的r s s 站点资源正影响着互联网内容的浏览利用。对于一些以r s s 格式发布的内容的搜索，用一般的搜索引擎搜索效率低，更新速度慢，而r s s 搜 索引擎克服了这些缺点，实现了高效率、快速地搜索这种通过r s s 种子发布的页 面。本文介绍了搜索引擎的基本工作原理，r s s 的概念和r s s 搜索引擎的理论， 研究并实现了r s s 种子的收集、r s s 页面的解析、索引的建立以及搜索和搜索结 果的排序问题。 本文在介绍r s s 规范以及搜索引擎的基本概念的基础上，首先，研究并实现 了站点爬行器来收集r s s 种子。其次，研究了r s s 种子的解析，利用x m l 解析 器来解析r s s 种子，提取链接、标题、描述等要素。第三，对r s s 种子所描述的 页面文档解析进行研究，编写了功能较为完善的类库，可以提取文档的标题、链 接、描述，具有较强的可重用性。最后，研究了文本预处理、文档模型的建立和 搜索结果的排序等技术，分别采用了基于向量空间的文档模型、基于规则的中文 切词算法、倒排文件作为索引方式、向量相似度算法对搜索结果进行排序。 关键词：搜索引擎、网页排序、中文分词、词干提取、索引 i i i 兰州大学硕士研究生毕业论文 a bs t r a c t r s s ( r e a l l ys i m p l es y n d i c a t i o n ) ，a l s ok n o w n a sr i c hs i t es u r n r n a r y ，o rr d fs i t e s u n a n a a r yi sw i d e l ya c c e p t e da n da p p l i e d ，t h er i c hr e s o u r c e so ft h er s s s i t ei sa f f e c t i n g t h ei n t e r n e tb r o w s e rt ou s e f o rs o m ei no r d e rt of o r m a tt h ec o n t e n to fr s ss e a r c h ， s e a r c he n g i n eu s et h es a m es e a r c hi si n e f f i c i e n t , s l o wt ou p d a t e ，a n dr s ss e a r c he n g i n e t oo v e r c o m et h e s es h o r t c o m i n g s ，t h er e a l i z a t i o no fah i g he f f i c i e n c y , q u i c k l ys e a r c h t h r o u g ht h i sr s s s e e dr e l e a s ep a g e t h i sa r t i c l ed e s c r i b e st h es e a r c he n g i n e sb a s i c w o r k i n gp r i n c i p l e ，r s sa n dr s st h ec o n c e p to fs e a r c he n g i n et h e o r y , r e s e a r c ha n d r e a l i z a t i o no ft h er s so ft h ec o l l e c t i o no fs e e d s ，r s sp a g er e s o l u t i o n ，t h ee s t a b l i s h m e n t o ft h ei n d e x ，a sw e l la ss e a r c ha n ds o r ts e a r c hr e s u l t sp r o b l e m i nt h i sp a p e r , i n t r o d u c i n gt h er s ss p e c i f i c a t i o n , a sw e l la st h eb a s i cc o n c e p t so f s e a r c he n g i n eb a s e do n , f i r s to fa l l ，r e s e a r c ha n dr e a l i z a t i o no ft h es i t et oc o l l e c tr s s c r a w l e r s e e d s e c o n d l y , t h es t u d yo fa n a l y t i cr s ss e e d s ，u s i n gx m lp a r s e rt op a r s et h e r s ss e e d s ，e x t r a c tl i n k ，t i t l e ，d e s c r i p t i o na n do t h e re l e m e n t s t h i r d ，t h es e e d so f t h er s s p a g ed o c u m e n td e s c r i b e di na n a l y t i c a lr e s e a r c h ，p r e p a r a t i o no fal i b r a r yf u n c t i o nb e t t e r , y o uc a l le x t r a c tt h et i t l eo ft h ed o c u m e n t , l i n k , d e s c r i p t i o na n dh a ss t r o n gr e u s a b i l i t y f i n a l l y , t h es t u d yo ft h et e x tp r e - p r o c e s s i n g ，t h ed o c u m e n tm o d e la n dt h er a n k i n go f s e a r c hr e s u l t sa n do t h e rt e c h n o l o g y - b a s e d ，r e s p e c t i v e l y , o ft h ed o c u m e n tv e c t o rs p a c e m o d e l ，r u l e b a s e ds e g m e n t a t i o na l g o r i t h mf o rc h i n e s e ，a st h ei n v e r t e df i l ei n d e x i n g ， v e c t o rs i m i l a r i t ya l g o r i t h ms o r ts e a r c hr e s u l t s k e yw o r d s ：s e a r c he n g i n e s ，w e b s i t er a n k i n g ，c h i n e s ew o r ds e g m e n t a t i o n , w o r ds t e m e x t r a c t i o n ，i n d e x i n g i v 兰州大学硕士研究生毕业论文 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进 行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均己明确注明出处。除文中已经注明引用的内容 外，不包含任何其他个人或集体己经发表或撰写过的科研成果。对本 文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标 明。 本声明的法律责任由本人承担。 论文作者签名：固丝纲 日期：勋舰 兰州大学硕士研究生毕业论文 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权 归属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的 规定，同意学校保存或向国家有关部门或机构送交论文的纸质版和 电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用任何复 制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或 与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州 大学。 保密论文在解密后应遵守此规定。 敝作者鹕：幽导师獬：吖友冬醐：蚴 i i 兰州大学硕士研究生毕业论文 第一章前言 1 1 研究工作背景 随着信息技术的高速发展，互联网得到了飞速的发展，成为了人们学习、工作、 生活中的非常重要的知识和信息来源。根据c 岖c ( 中国互联网络信息中，c 。, ) 2 0 0 8 年7 月发布的中国互联网络发展状况统计报告 1 】，截止到2 0 0 8 年6 月底，我国 的上网计算机网民数量达到2 5 3 亿，网民规模跃居世界第一位。中国网站数量为 1 9 1 9 万个。关于网页的数日没有具体的统计数据，但根据科学杂志上提供的 集合估计算法，通过中国几个主要搜索引擎获得的搜索数据( 百度、g o o g l e 、搜狐、 网易) ，我们可以粗略地估计到当前中国拥有的网页数量己经超过了l 亿。i n t e r n e t 上的信息资源随着i n t e m e t 的发展而呈现出如下特点： 信息量巨大而且分散 自治性强 信息资源多种多样 信息的不致性和不完整性 为了获取用户所需的信息，必须借助一定的工具，他们通常使用如下两类网站： 第一类是目录系统，其典型代表是h a 0 1 2 3 ，它通过有专业知识的网页编辑人员 对互联网上的网页进行精选，建立一个索引目录，来给用户提供导航服务。这类 通过手工维护的很好的系统的优点是提供的网页准确率高，可以有效地覆盖热门 主题，但它们的缺点也是显而易见的。如过于主观，而且需要高昂的代价来建立 和维护，并且更新速度慢，同时不可能覆盖所有的主题。 第二类是搜索引擎。搜索引擎通过网络爬虫自动地从网上搜集和分析网页，建 立索引，为用户提供服务。这类通过关键词匹配实现查找的自动更新的搜索引擎 的优点是涵盖的网页数量巨大，因为它拥有基于关键词的全文索引，它为所有网 上的用户提供了一个统一的入口，所有的用户都可以通过搜索引擎到达自己想去 的网上的任何一个地方。搜索引擎对用户是这样地重要，成为了用户上网的必备 工具。根据中国互联网络发展状况统计报告 1 】用户经常使用的网络服务是：电 子邮件( 9 2 6 ) 、搜索引擎( 6 8 3 ) 、软件上传或下载服务( 4 5 3 ) 、信息查询( 4 2 2 ) 搜索引擎技术伴随着互联网的发展，取得了引人注目的成就。搜索引擎大约经 兰州大学硕士研究生毕业论文 历了如下三代的发展： 第一代搜索引擎出现于1 9 9 4 年。这类搜索引擎的索引量一般都少于1 , 00 0 ，00 0 个网页，极少重新搜集网页和更新索引。并且其检索速度非常慢，一般都要等待 1 0 秒甚至更长的时间。在实现技术上也基本沿用较为成熟的i r ( i n f o r m a t i o r e t r i e v a l ) 、网络数据库等技术，相当于利用一些己有的技术实现一个互 联网上的应用。在1 9 9 4 年3 月到4 月，搜索引擎平均每天承受的查询大约1 5 0 0 次。 大约在1 9 9 6 年出现的第二代搜索引擎系统大多采用分布式方案来提高数据规 模、响应速度和用户查询数量，它们一般都保持大约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 年到现在，出现了搜索引擎空前繁荣的时期，这一时期的搜索引擎的 发展有如下几个特点： 索引数据库的规模持续加大，一般的商业搜索引擎都保持有1 0 0 亿个以上的网 页。由于索引数据库的巨大规模，使得对于查询关键词的返回结果数量非常大， 搜索结果的相关度评价成为了研究的焦点。相关的研究又可以进一步地分为两类： 一类是对超链接的分析：另一类是对用户反馈信息的分析。 开始使用自动分类技术。 搜索引擎己经成为一个新的研究、开发领域。因为它要用到信息检索、人工 智能、计算机网络、分布式处理、数据库仓库、数据挖掘、数字图书馆、自然语 言处理等诸多领域的理论和技术，所以具有综合性和非常有强度的挑战性。又由 于搜索引擎有大量的使用用户，有很好的经济价值，所以引起了世界各国计算机 界和信息产业界的高度关注。目前的研究、开发十分活跃，并出现了很多非常有 价值的方向。 提高信息检索结果的精度、查询的有效性。 用户在搜索引擎上进行信息检索时，并不十分关注返回结果数量的多少，而 是看结果是否和自己的需求相吻合。对于一个查询，传统的搜索引擎动辄返回几 十万、数百万篇文档，用户不得不在返回结果中筛选。解决查询结果过多的现象 目前出现了如下几种方法：一是通过各种方法获得用户没有在查询语句中表达出来 2 兰州大学硕士研究生毕业论文 的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型；使用相关度反 馈机制等，使用户告诉搜索引擎哪些文档和自己的需求相关( 及其相关的程度) ，哪 些不相关，通过多次交互逐步求精。二是使用正文分类( t e x tc a t e g o r i z a t i o n ) 技术将 查询结果分类，使用可视化技术显示分类结果，用户可以只浏览自己关心的类别。 三是进行站点类聚或内容类聚，减少查询站点信息的总量。 基于智能代理的信息过滤和个性化服务 信息智能代理是另外一种利用互联网信息的方法。它使用自动获取的领域模 型( 如w e b 知识、信息处理、与用户兴趣相关的信息资源、领域组织结构等) 、用 户模型( 如用户背景、兴趣、行为、风格) 知识进行信息爬取、过滤( 包括兴趣过滤 和不良信息的过滤) 、索引，并自动地将用户感兴趣的、对用户有用的信息提交给 用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而提供 个性化的服务。智能代理可以在用户端进行，也可以在服务器端进行。 重视交叉语言搜索的研究和开发 交叉语言信息检索是指用户用母语提交查询，搜索引擎在多神语言的数据库中 进行信息搜索，返回能够回答用户提问的所有语言的文档。如果再加上机器翻译， 返回结果可以用母语显示。该技术目前还处于初步研究阶段，主要的困难在于自 然语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、互联网信 息遍布世界的今天，具有非常重要的意义。 1 2r s s 搜索引擎概述 1 2 1r s s 搜索引擎的基本概念 r s s 是一种描述和同步不同网站内容的格式，是目前最为广泛的x m l 应用。 r s s 搭建了信息迅速传播的一个技术平台，使得每个人都成为潜在的信息提供者。 发布一个r s s 文件以后，这个r s sf e e d ( 又称r s s 种子) 中包含的信息就能直接 被其他站点调用，而且由于这些数据都遵守标准的x m l 格式，所以也能在其他的 终端和服务中使用。而r s s 搜索引擎就是为专门搜索这种以r s s 格式发布的内容而 设计的。它的搜索过程和一般搜索引擎有不同之处：普通搜索引擎通过网络爬虫， 3 兰州大学硕士研究生毕业论文 在互联网上获取页面，并对页面进行解析、分词，建立索引，从而提供搜索服务。 而r s s 搜索引擎首先在网站上获取r s s 种子，因为种子中包括网站中文章的摘要，所 以只需解析这些摘要，切词，然后建立索引，从而实现搜索网站上文章的目的。 1 2 2r s s 搜索引擎的意义 r s s 协议的应用越来越广泛，比如博客、新闻聚合等都遵循r s s 标准，对于这 些内容的搜索，用普通的搜索引擎搜索效率低，更新速度慢，而r s s 搜索引擎改进 了这些缺点，实现了高效率、高速度地搜索这类以r s s 种子发布的页面。 1 3 本文研究的内容和创新之处 本文围绕基于r s s 的搜索引擎技术，研究并实现了r s s 页面的解析、索引的 建立以及搜索和检索结果的排序问题，并比较了基于r s s 的搜索引擎和经典搜索 引擎的区别和优缺点。具体情况包括如下： ( 1 ) 健壮和尽可能高性能的站点爬行器( s p i d e r ) 是构建搜索引擎的关键技术之 一。本文扩展了普通爬虫的功能，在互联网上广泛搜集r s s 种子。 ( 2 ) r s s 文档解析及解析过程中的中文切词是搜索引擎处理汉字页面的关键技术。 本文实现了r s s 解析器，可以处理标准的r s s 页面，方便提取r s s 页面元素，如 标题、文本、链接等标签内容，具有很强的可重用性。中文分词采用普遍使用的 二分切词法。 ( 3 ) 建立文档模型和索引是搜索引擎的重要部分，它为后续的搜索和结果排序提 供了基本的数据保障。本文中的文档模型采用了向量空间模型，索引模型采用倒 排索引结构。 ( 4 ) 搜索引擎给用户返回的查询结果中各个检索结果排列顺序十分重要，是影响 搜索引擎质量的关键阀题之一。本文实现了基于向量相似度的算法，对检索结果 进行排序。 4 兰州大学硕士研究生毕业论文 1 4 本文的组织结构 第1 章：介绍了本论文的研究工作背景，阐述了本文的主要研究内容和创新 之处。 第2 章：相关基本概念及研究现状说明。首先分析了经典搜索引擎的基本架 构。其次，以这些基本架构为大纲，较为详细地描述了各个功能模块的实际工作 流程。 第3 章：分析了基于r s s 的搜索引擎的理论基础。首先解释说明了r s s 规范， 其次讲述了r s s 种子的解析。对r s s 种子中的摘要部分建立索引，以及基于r s s 的搜索过程。对搜索结果的优化排序，日志模块理论分析。 第4 章：系统实现。在第三章理论分析的基础上，分析实现了系统的大部分 功能模块。 第5 章：总结和下一步研究工作展望。主要对本论文的研究工作进行总结， 并对下一步的工作进行展望。 5 兰州大学硕士研究生毕业论文 第二章传统搜索引擎分析 2 1 搜索引擎概述 搜索引擎通常通过r o b o t 或s p i d e r 爬取i n t e m e t 上的w e b 文档，进行噪音 过滤、分词、转换等处理工作。然后对文档信息进行预处理和形式化描述，抽取 特征并进行索引。文档的收集是w e b 信息检索的基础。文档的预处理为后续检索 工作提供了保障。一个典型搜索引擎的基本工作流程如下图所示： 甩 蕴 一 卢 建 一嚣卜 寓 鬟 囊 譬 _ 曩 辱i 一，a 主要包括如下四个过程：1 在互联网上发现、搜集网页信息：2 ，对信息进行提取 和组织建立索引数据库；3 由检索器根据用户输入的查询关键字，在索引库中快速检 索出文档。4 用户接1 2 1 ( 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 发现、搜集网页信息 发现、搜集网页信息主要可以采取以下两种做法：一种方法是用户主动向搜索 引擎报告或提交自己的资源。大多数搜索引擎的数据获取工作采用的是另外一种 方式，由高性能的网络爬虫自动完成。s p i d e r 是一个能够沿着超链接漫游w e b 页 面集合的程序，并且能够通过h t t p 等协议下载所漫游到的页面，它会定期根据 预先设定的地址去查看对应的网页，如网页发生变化则重新下载该网页，否则根 据该网页中的链接继续访问。s p i d e r 访问页面的过程是对互联网上信息遍历的过 程，它可以采用广度优先和深度优先两种算法进行网页遍历，为了保证爬虫遍历 信息的广度，一般事先设定一些重要的链接，然后对这些链接进行遍历。在遍历 过程中不断记录网页中新出现的链接，不断遍历下去，直到访问完所有的链接为 止。网络蜘蛛为实现其快速地漫游整个互联网，通常在技术上采用抢先式多线程 技术实现在网上信息的搜集。通过抢先式多线程的使用，能索引一个基于u r l 链 接的w e b 页面，同时启动一个新的线程跟随每个新的u r l 链接。当然在服务器上 的线程也不可能无限膨胀，需要在服务器的正常运转和快速收集网页之间找一个 6 兰州大学硕士研究生毕业论文 平衡点。在算法上各个搜索引擎公司可能不尽相同，但目的都是快速浏览w e b 页。 目前国内的搜索引擎公司中，百度的网络蜘蛛采用了可定制的、高扩展性的调度 算法使得搜索器能在极短的时间内收集到最大数量的互联网信息，并把所获得的 信息保存下来以备建立索引和用户检索。 2 索引数据库的建立 索引数据库的建立关系到用户能否最迅速地找到最准确、最广泛的信息，索引 数据一般按照倒排文件的格式存放。如果索引不能及时更新，s p i d e r 带回的新信息 就不能被使用搜索引擎的用户检索到。对网页采用基于网页内容分析和基于超链 分析相结合的方法进行相关度评价，能够客观地对搜集到的网页进行排序，。从而 最大限度地保证搜索出的结果与用户的查询串相关度高。在设计一个索引数据库 时，要针对实际需要确定索引的数据结构和存储方式。由于搜索引擎系统通常处 理的都是海量信息，因此还要设计一定的压缩策略，对索引文件进行有效的压缩， 以提高检索的效率。搜索引擎对网站页面建立索引的过程中采取了按照关键词在 网站标题、网站描述、网站u r l 等不同位置的出现或网站的质量等级等建立索引 文件，从而保证搜索出的结果与用户的查询串相一致。搜索引擎在索引库建立的 过程中，对所有数据采用多进程并行处理的方式，对新的信息采取增量式的方法 建立索引，从而保证能够快速地建立索引，使搜索结果能够得到及时的更新。搜 索引擎在建立索引库的过程中还对用户搜索的查询串进行跟踪，并对查询频率高 的查询串建立c a c h e 页。 3 。用户检索的过程 这是对前两个过程的检验，检验该搜索引擎能否给出和查询串匹配度高的信 息，检验该搜索引擎能否迅速地给出用户最想得到的信息。对于网站数据的检索， 不同搜索引擎有不同的做法。比如新浪采用c l i e n t s e r v e 结构、多进程的方式在索 引库中检索，大大缩短了用户的等待时间，并且在用户查询高峰时服务器的负担 不会过高( 平均检索时间在o 3 秒左右) ；而作为国内众多门户网站的网页检索技术提 供商的百度，其搜索引擎则运用了先进的多线程技术，采用高效的搜索算法和稳 定的u n i x 平台，因此可以大大缩短对用户搜索请求的响应时间。作为慧聪系列 应用软件产品之一的i - s e a r c h 2 0 0 0 采用的超大规模动态缓存技术，使一级响应的覆 盖率达到7 5 以上，独有的自学习能力可自动将二级响应的覆盖率扩充到2 0 以 e 。 7 兰州大学硕士研究生毕业论文 4 用户接口( u s e ri n t e r f a c e ) 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。 主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、 及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人 类的思维习惯和使用方式。 用户输入接口可以分为简单接口和复杂接口两类。 简单接口只提供用户输入查询串的文本框，复杂接口可以让用户对查询进行复 杂限制，如逻辑运算( 与、或、非) 、相近关系( 相邻、n e a r ) ，域名范围( 如e d u ，c o r n ) ， 出现位置( 如标题、内容) 、信息时间、长度等等。目前一些公司和机构正在考虑制 定查询选项的标准。 下面详细分析一下，各个模块的详细工作流程。 2 2 网页搜集 网页搜集的过程是从u r l 库( 初始时包含用户指定的起始种子u r l 集合，可以 是1 个或多个) 获得输入，解析u r l 中标明的w e b 服务器地址、建立连接、发送请 求和接收数据，将获得的网页数据存储在原始网页库，并从其中提取出链接信息 放入网页结构库，同时将待抓取的u r l 放入u r l 库，保证整个过程的递归进行，直 至i j u r l 库为空。搜索引擎为了提供检索服务，需要保存网页原文。网页搜集子系 统不但要能够获取以h t m l ，h t m ，t x t 结尾的u r l 对应的网页，还应该能够获取 不是以h t m l 结尾的u r l ，比如p d f ，d o c 。因为p d f ，d o c 等文件可以通过转换 程序生成为h t m l 或者t x t 文件，同样为搜索引擎提供检索服务。作为搜索引擎的 起始流程，搜集的网页要按照一定的格式存储，便于后续组织和提供服务。首先 必须要做的一件事情是根据一个给定的u r l ，组成消息体，发送给该u r l 指向的服 务器。特别需要增j i 口d n s 缓存和i p 范围控制功能。增j j i d n s 缓存的原因：1 ) u r l 数 以亿计，而主机数以百万计。为了避免频繁的查询d n s 服务器，造成类似于拒绝服 务攻击的副作用。2 ) 既加快网页信息的获取，又进一步降低对d n s 服务器的压力。 增j j i i p 范围控制的原因：1 ：有些站点不希望搜集程序搜走自己的资源。2 ：针对 特定信息的搜索，比如：校园网搜索，新闻网站搜索。3 ：网络资费方式也会对搜 集策略产生影响。将获取网页信息保存在磁盘中，需要按照规定的格式保存，便 于后续处理和提供服务。原始网页信息的存储格式应当设计为适合长期保存并易 8 兰州大学硕士研究生毕业论文 于处理，可以作为终端产品提供给用户使用。考虑到终端产品使用的便利性，要 求原始网页库的存储格式具备简单性的特点。 由于存储介质都是有寿命的，所以应当考虑当存储介质损坏时数据的可恢复 性。例如：磁盘的某个扇区损坏，导致部分数据不能读出，如果剩下的数据仍然 可以使用，就能将损失降到最少。对于海量数据来说，在存储和传输的过程中， 由于硬件和软件问题导致数据错误是不可避免的。因此，原始网页的存储格式还 应当具备隔离错误的特点。 完成搜集网页的工作，即使是只有一个g a t h e r e r ，也需要解决如何避免重复 搜集网页的衄题。因此定义两仑表，：未访问表：和兰己访问表”。：未访问表? 电存储 准备取入待访问队列的u r l ，“已访问表”中存储已经请求过网页的u r l 。：i 梢g a t h e r e r 因为访问新的网页解析出新的u r l 后，根据“未访问表”，“已访问表”，就可以判断 哪些工作已经完成，从而避免重复搜集。 2 3 预处理阶段 要实现搜索引擎，网络蜘蛛得到网页容只是最基本的前提。各种网页里包含 了大量的格式信息和其他广告等信息。只有通过一定的策略把垃圾信息去除才能 得到有效的文档内容。 网页内容分析有两个层面的任务，分析网页内部的基本信息和对网页内容的 结构进行识别。最终的目的都是提取有效的数据、过滤垃圾信息。另外在分析的 同时还要进行网页排重，避免相同的结果同时出现。真正的搜索引擎网页分析通 常包括基于网络拓扑的链接分析、基于网页内容的关键词统计和过滤，以及基于 网页结构的结构化分析。 2 3 1 网页分析功能需求 搜索引擎的索引和查询的每个基本过程中，都是以基本的语素项为单位的。 基本的语素项是通过网页或文档分析得到的，分析过程决定了最小的索引单元和 最终的匹配过程。通常英文文档的分析过程包括了单词提取、标点符号去除、大 小写转换、单词词干还原、连接词汇或高频词汇去除等操作。中文文档的分析过 程除了上述英文分析内容以外，还包括一个最重要的中文分词过程。 9 兰州大学硕士研究生毕业论文 不同搜索引擎在网页分析过程中会采取不同的策略。网页通常是h t m l 和 j a v a s c r i p t 脚本组成，通常包含了大量的格式化元素和附属信息、计算函数等内 容。网页分析首要任务是把网页中格式化信息和正文文本信息分离，为索引和排 序提供素材。中文文本没有空格分隔，建立索引之前必须经过切分成基本的词汇 单元。 除了提取文本的基本任务以外，网页内容分析还需要注意网页中比较重要的 元素，如网页中的各级标题、链接文字、锚文字、黑体文字、网页m e t a 标记等内 容。这些内容在分析的过程中增加了标记，在索引和排序过程中，可以作为重要 信息进行加权。g o o g l e 和b a i d u 等搜索引擎都会将链接文字描述作为关键词加以 索引。所以很多网站在设计时特别处理连接词汇的相关性，可以在搜索引擎中得 到很好的排序效果。 ， 除此之外，搜索引擎还需要提供摘要信息、附属的时间、来源地址等信息， 甚至网页的内容分类、相似网页等信息，一般也要在网页分析过程中获得。分析 中得到的链接地址可以进一本用来下载，不断增加搜索引擎网页收录数据量。 2 3 2 网页分析实现原理 开发网页内容分析系统，需要熟悉常见的静态或动态w e b 文件格式，例如 h t m l ，w m l ，x h t m l ，x m l 等。当需要处理的文档内容数量巨大时，需要利用最高效的 文本字符串处理和模式匹配技术，完成信息提取和内容分析的任务。从h t m l 网页 中，需要提取页面、音乐、图片、游戏的链接以及文本内容。 内容分析的基本技术流程包括格式化字符去除、文本正文分词、信息过滤等 基本任务。它们分别完成h t m l 标记符号的删除、索引词汇的分割以及垃圾信息的 过滤。由于互联网上的网页结构千差万别，看似简单的一个文本分析工作也及其 困难。尤其是结构化分析和视觉模块分析，经常会花费比较大的代价。 常用的网页分析方法包括简单语言标记去除、正则表达式信息抽取和d o m 树 内容抽取3 种。在搜索引擎开发中需要根据实际系统灵活应用。各种方法具体内 容介绍如下。 简单语言标记去除方法主要根据h t m l 语言的特点实现。基于所有语言标记都 采用尖括号分离，通过简单的程序遍历和赋值，可以删除所有尖括号标识出来的 语言标记。该方法处理后留下的内容基本是正文信息，但是包括一些噪声，尤其 l o 兰州大学硕士研究生毕业论文 对广告等信息无法有效去除。 正则表达式信息抽取主要利用模板方式提取有效信息。正则表达式是用于进行 文本匹配的工具，在编写处理字符串的程序或网页时，经常会有查找符合某些复 杂规则的标签字符串的需要。正则表达式就是用于描述字符串提取复合要求内容 的工具。正则表达式可以快速、精确地提取网页中的信息。 d o m 树内容抽取是利用每个网页都有一定层次结构的特点。d o m 树是把原始网 页内容转化建立树形结构存储。通过遍历生成的树型结构，可以灵活地访问网页 的任何内容。这种结构可以自行定义需要访问的节点内容，便于去除广告信息， 但实现时稍微复杂些。 实际的应用系统中还需要对检索内容进行分词，过滤高频词汇和虚词。 2 4 网页索引程序实现 网页索引的实现原理，类似于自己建立一个小型的数据库系统，或者建立一 个格式化文本文件。通常所说的网页索引库，并不一定是真正存放在数据库管理 系统中。只是网页文本中索引项的一种组织和存储方式。 2 4 1 网页索引功能需求 网页搜索引擎的索引最基本功能是为检索提供服务，为了满足实时响应要求， 索引的查询和访问必须具有足够的速度。这就是要求索引程序能够生成一种数据 存储和组织结构。能够从大量文件数据中快速找到某个单词或词汇。 传统的顺序扫描每个文件方法显然无法胜任，尤其在大型文件或海量信息的 环境。实际工作中通常对文档格式进行转化，形成适合快速检索的存储格式，便 于快速查找和定位。搜索引擎最常用的索引数据结构是倒排文档索引，用于快速 响应关键词检索。索引系统的基本实现思路非常简单，但是当索引涉及的数据量 膨胀到上亿网页，并发访问达到上千用户时，索引系统的每一个细节都成了影响 性能的关键问题。需要考虑的内容如下： 随着抓取的互联网信息的增多，必须采用分散存储的分布式索引系统。网 络带宽和爬虫能力的不断提高，索引技术越来越多地考虑海量数据的实际 存储问题。 兰州大学硕士研究生毕业论文 网页的不断变化需要对已经建立的索引进行更新，甚至需要对部分数据延 迟非常短。部分网页不再存在，需要及时从索引库中删除。整个索引与检 索服务同时进行，需要对索引的建立和加载进行管理，实现动态更新和实 时更新。 由于数据量庞大，为了能够保存上百亿、千亿的网页，对索引进行一定的 压缩也是非常必要的。 当数据量膨胀到无法直接索引，或者直接索引的时间空间消耗巨大时，出现了 多重和多级索引。 2 4 。2 网页索引实现原理 搜索引擎采用关键词匹配，核心算法上采用倒排索引结构。倒排索引是一种 以关键词作为索引关键字和链表访问入口的索引结构。通常保存在内存中以提高 访问速度。倒排索引利用索引关键字直接确定文档列表，最后确定希望找到的文 档列表。由于搜索引擎中的文件通常并不单独存放，而是存储在一个巨型文件库 里。为了节约内存，文档在索引中通常以文件库编号以及文件内偏移来代表。通 过关键词检索是方便的，检索的结果可以直接通过位置信息计算得到。在需要的 时候可以读取内存空间或磁盘文件得到。倒排索引的基本结构是： 其中的关键词是经过分词以后的文本词汇内容，倒排索引中的文件实际上是文 件所在的文件位置和偏移量。每个文件实际存储了文件的原始内容。 1 2 兰州大学硕士研究生毕业论文 同 要m 致l t - - 一一k 一 t i 。bd 。c u m e n t 曩 焉 r e p r e s e n i a o v ( 互 吉，一7 ， 一_ = i 。一j 。一j 一一一 曙- “慨 一p ( ) = 例排裹i 烹* 一n 7 支档芑静 倒排索引的数据结构中的每一个元素是一个关键词生成的索引项。附加了相关 的属性值、其他关联信息和存放位置。数据结构的最大的特点是改变了信息组织， 更加方便检索过程。通常的顺序文件查找方法是先确定文档，然后在文档中顺序 查找待确定的记录。而搜索引擎并不知道用户要查找的关键词在哪个文件里，除 非顺序地查看。而倒排索引能利用索引关键字直接确定文档列表，最后确定希望 找到的文档列表。 2 5 网页检索程序 2 5 1 检索功能需求 检索功能是搜索引擎体现自己最终价值的环节。良好的响应速度、合理的结 果集和排序次序都很重要。在得到检索结果之前，需要对用户输入的关键词进行 分析，按照索引过程相同的方法对文本进行切分。最终的检索过程是用户通过输 入关键词的语素向量与索引库中的语素向量的相似度计算和匹配得到。 检索通常要求支持布尔检索、词组检索等多种形式，这两种检索形式在搜索引 擎中非常普遍。随着智能化检索的要求，对检索预处理还包括了检索意图分析和 兰州大学硕士研究生毕业论文 用户个性化信息分析，或者根据用户行为对检索词进行分类。但具体来看，搜索 引擎主要功能仍然是对用户输入的检索关键字进行分析和切分。切分结果与索引 库中语素进行匹配，找到最匹配的检索结果，并按照一定的次序返回给用户。 2 5 2 检索实现原理 搜索引擎信息检索的模型主要有向量模型、布尔模型、概率模型和混合模型 四种。实际的搜索引擎信息查询实现方法都采用了向量检索和布尔查询相结合的 方式。搜索引擎的基本操作仍然是布尔运算，这种检索算法容易实现，并且速度 快，适合于海量的信息查找。但是布尔运算无法提供量化的相似度信息，不能进 行结果的排序，必须借助向量模型完成。 布尔查询的理论模型基础是基于集合论和布尔代数的一种简单检索模型。 这种模型把查询串转换成基本关键词组合的与或非组成的关键词组合。在 倒排索引结构中，布尔查询一般先对布尔组合中的一个关键词进行查询， 得到的对应结构列表进一步组合或归并计算得到目标结果。 向量模型在查询串和文档之间分配不同的权值，权值大小反映了文档库中 的文档与用户查询串的相关度。查询得到的结果文档集按照权值计算相关 度有序排列，所以向量模型得到的匹配文档可以是全部精确匹配，也可以 是部分地匹配查询串。 检索的基础实现原理是基础的匹配计算采用向量检索，但同时在多个索引词 或语素之问支持布尔组合查询操作。 2 6 用户接口( u s e ri n t e r f a c e ) 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。 主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、 及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人 类的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种。 简单接口只提供用户输入查询串的文本框：复杂接口可以让用户对查询进行 1 4 兰州大学硕士研究生毕业论文 限制，如逻辑运算( 与、或、非) 、相近关系( 相邻、n e a r ) ，域名范围( 如e d u ，c o m ) ， 出现位置( 如标题、内容) 、信息时间、长度等等。目前一些公司和机构正在考虑 制定查询选项的标准 1 5 兰州人学硕士研究生毕业论文 第三章基于r s s 搜索的分析 3 1r s s 规范 3 1 1 什么是r s s r s s 是互联网内容联合发布系统的一种格式。 r s s 是r e a l l ys i m p l es y n d i c a t i o n 的缩写( 对r s s 2 0 而言，是这三个词的 缩写，对r s s l 0 而言则是r d fs i t es u m m a r y 的缩写，1 0 与2 0 走的是两个体系) r s s 基于x m l ，所有的r s s 必须遵循w 3 c 网站上公布的x m l1 0 规范。 在一个r s s 文档中，根元素是 ，带有一个必备属性v e r s i o n ，用以指明 该文档遵循的r s s 规范，如果r s s 文档遵循r s s 2 0 规范，则v e r s i o 值必须是2 0 。 元素只有一个子元素，包含关于频道的一些信息。频道( c h a n n e l ) 是整个 b l o g ，项( i t e m ) 指一篇文章或日志( 也有称这为p o s t ) 。从属于 元素的是一个 元素，包含着关于c h a n n e l ( 元数据) 和内容的信息。 下面来介绍 的子元素 子元素- - 是 的可选子元素，包含3 个必要的及3 个可选元素 是c h a n n e l 中g i f ，j p e g 或p n g 图像的u r l 链接。 用来描述图像。当c h a n n e l 在h t m l 中表现时，相当于用来表示 标签的a l t 属性。 是站点u r l ，这个图像是指向这个站点的链接。( 说明，实际上，图 像的 和 应该和c h a n n e l 的 ， 的值是一样的。 可选的元素包括 和 ，数字表示图像宽度和长度上的像素。 包含的文字，表示图片在h t m l 网页中 标签的t i t l e 属性。 w i d t h 的最大值为1 4 4 ，缺省值为8 8 。 1 6 兰州大学硕士研究生毕业论文 h e i g h t 的最大值为4 0 0 ，缺省值为3 1 。 的子元素- - 是 的可选子元素。它指定了一个w e b 服务，支持r s s c l o u d 接口能够在h t t p - p o r t ，x m l - r p c 或s o a p l 1 中实现。它目的是允许处理向 c l o u d 登记，通知c h a n n e l 的更新，轻易实现r s s f e e d s 订阅协议。 一个例子： 在这个例子中，为了向c h a n n e l 请求通信，你将向r p c s y s c o m 发送一个 x m l - r p c 消息在8 0 端口，用路径r p c 2 。这个过程称为 m y c l o u d r s s p l e a s e n o t i f y 。 的子元素- - 是 的可选子元素。 。t t l 代表存活时间。它是一个分钟单位的数字，指示c h a n n e l 被缓存多长时 间，从源地址更新以前。 的子元素- - 包含一个可选的子元素 ，包括4 个必须的下级子元 素。 文本输入区提交按钮的标签。 一文本输入框的说明。 一文本输入框文本控件的名字。 一处理文本输入请求的c g i 脚本的u r l 地址。 元素的目的是神秘的。你可以用它来确定搜索引擎，或者允许 读者提交反馈。大多数的聚合器会忽略它。 一个c h a n n e l 可以包含许多个 。一个i t e m 可以代表一个“故事”一 大多类似报刊或杂志中的报道：如果说它的d e s c r i p t i o n 是报道的摘要的话，它 的l i n k 指向一篇完整的报道。i t e m 本身可以是完全的，如果这样的话，d e s c r i p t i o n 1 7 兰州大学硕士研究生毕业论文 可以包含文本( 允许个体编码h t m l ：看例子) ，li n k 和t i t l e 可以省略。i t e m 的所 有子元素是可选的，尽管如此，至少必须存在一个t i t l e 或d e s c r i p t i o n 。下面来 介绍 的子元素 的子元素 是一个可选的 子元素 它的值是i t e m 来自r s sc h a n n e l 的名字。区别于 ，它有一个必须的 属性，u r l ，指向源x m l i z a t i o n 的链接。 一个例子： t o m a l a k s r e a l m 这个元素的目的是为了传播链接的可信度，宣传新