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

中文摘要 互联网的迅速发展，使得现有的搜索引擎面临着巨大的挑战，面对众多杂乱无章的 信息，搜索引擎如何能够快速准确检索到用户需要的信息，在搜索引擎中就显得十分重 要。因此，搜索引擎排序算法也就成为众多搜索引擎关注的关键问题之一。 在现有搜索引擎排名算法中，基于网页链接结构的经典算法就是经常提到的 p a g e r a n k 算法和h i t s 算法，这些算法也是国内外众多学者和研究人员研究的主题，并 取得了一定的成绩，形成了一些比较成熟的基于p a g e r a n k 算法和h i t s 算法的综合改进 算法。 本文首先说明了国内外搜索引擎排名算法的研究背景、发展现状，然后分析了搜索 引擎的工作原理和关键技术，以及搜索引擎的三级评测指标，为本文的原型系统测试和 算法验证提供了一定的依据。然后，剖析了传统p a g e r a a 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 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 s r t a c t t h er a p i dd e v e l o p m e n to ft h ei n t e r a c t , m a k et h ee x i s t i n gs e a r c he n g i n ei sf a c i n gah u g e c h a l l e n g e s ，i nt h ef a c eo ft h en u m e r o u sd e s u l t o r i l y , h o wc a ns e a r c he n g i n eu s e r sn e e dt o q u i c k l ya n da c c u r a t e l yt h ei n f o r m a t i o nr e t r i e v a l ，i ti sv e r yi m p o r t a n t t h e r e f o r e ，s e a r c he n g i n e r a n k i n ga l g o r i t h mw i l lb e c o m et h ef o c u so fm a n ys e a r c he n g i n e si so n eo ft h ek e yp r o b l e m s i nt h ec u r r e n ts e a r c he n g i n e r a n k i n ga l g o r i t h m s ，w e b - b a s e dl i n ks t r u c t u r eo ft h ec l a s s i c a l a l g o r i t h m i so f t e nm e n t i o n e dh i t st h ep a g e r a n ka l g o r i t h ma n dt h e a l g o r i t h m , t h e s e a l g o r i t h m sa r ea l s oan u m b e ro fd o m e s t i ca n df o r e i g ns c h o l a r sa n dr e s e a r c h e r so ft h et o p i c ， a n da l s om a d es o m ea c h i e v e m e n t s ，t h ef o r m a t i o no fs o m eo ft h em o r es o p h i s t i c a t e da l g o r i t h m b a s e do np a g e r a n ka l g o r i t h r na n dt h ei n t e g r a t e dh i t si m p r o v e da l g o r i t h m t h i sp a p e rf i r s td e s c r i b e st h ed o m e s t i ca n di n t e r n a t i o n a ls e a r c he n g i n er a n k i n ga l g o r i t h m r e s e a r c hb a c k g r o u n d ，a n dt h ed e v e l o p m e n to ft h es t a t u sq u o ，a n dt h e na n a l y z e st h ew o r k i n g p r i n c i p l eo fs e a r c he n g i n e sa n dk e yt e c h n o l o g i e s ，a n de v a l u a t i o no fs e a r c he n g i n e st h r e e i n d i c a t o r sf o rt h i sp r o t o t y p es y s t e mt e s t i n ga n dv e r i f i c a t i o na l g o r i t h m st op r o v i d es o m eb a s i s t h e n , t h ea n a l y s i so ft h et r a d i t i o n a lp a g e r a n ka l g o r i t h ma n dt h ei m p r o v e dp a g e r a n k a l g o r i t h m ，a n a l y z e st h e i re x i s t i n ga d v a n t a g e sa n dd i s a d v a n t a g e s ，f o r 懈t of u r t h e ri m p r o v et h e p a g e r a n ka l g o r i t h mp r o v i d e st h ep o s s i b l e c o n v e n t i o n a la l g o r i t h m sa n di m p r o v e da l g o r i t h mp a g e r a n k , c o m b i n i n gc l a s s i f i c a t i o n t e c h n o l o g ya n dt i m eo ft h e m es i m i l a r i t yf a c t o ro ff e e d b a c ka l g o r i t h mo fc o m p r e h e n s i v e p a g e r a n ka l g o r i t h m , t h ei m p r o v e da l g o r i t h mi sm a i n l yf r o mt h ew e bp a g el i n ks t r u c t u r e p r e t r e a t m e n t , t h et h r e ea s p e c t so fp a g e r a n ka l g o r i t h mw a si m p r o v e d , t h ep r o p o s e da l g o r i t h m b a s e do nac o m p r e h e n s i v ei m p r o v e m e n to fp a g e r a n ka l g o r i t h m t h ep r o t o t y p es y s t e mh a s b e e nd e s i g n e da n d , a tt h es a m et i m e ，t oi m p r o v et h e a l g o r i t h mi sv e r i f i e d v e r i f i e d , t h e i m p r o v e da l g o r i t h mc a ni m p r o v et h ep r e c i s i o no fs e a r c he n g i n e s ，a tt h es a m et i m e ，i tc a n i m p r o v et h es y s t e m sr e c a l lr a t e k e yw o r d s ：s e a r c he n g i n e ，p a g e r a n ka l g o r i t h m , d a t e b a s ec o r r l a t i o n ，c l a s s i f i c a t i o n t e c h n o l o g y , t u n ef e e d b a c kf a c t o r 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：7 蜂指导教师签名：槛 3 b 年6 只1 2e t 2 4 0 年0 s 窍ae t 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特，l , j ) j n 以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的 说明并表示谢意。 学位论文作者签名：彦抑彳 | o 年杏r | 2 日 西北大学硕士学位论文 1 1 本文的研究背景 第一章绪论 随着信息技术的快速发展，互联网已成为人们工作、学习最重要的知识来源和信息 来源。根据中国互联网络信息中心2 0 1 0 年1 月发布的第2 5 次中国互联网络发展状况 统计报告，截止到2 0 0 9 年1 2 月，我国上网用户规模达到3 8 4 亿人，互联网普及率达 到2 8 9 9 6 【l 】。互联网之所以有如此多的网民，主要在于互联网上的信息几乎包容了人类 发展过程中的所有知识，并且还在以几何级的速度在增长。互联网在给人们带来大量信 息的同时，也出现了一些问题，比如，在众多杂乱的信息中如何迅速检索到有效信息， 以及搜索结果不能达到用户需要等问题。因此，搜索引擎已成为互联网的重要组成部分， 对互联网的进一步普及产生着巨大的影响。 由于互联网的迅速发展，互联网上的信息呈现着信息量大且分散，自治性强，资源 多样的特点。因此，现有搜索引擎搜索出来的结果有时存在不一致和不完整，出现这种 问题的原因，可以总结为以下几个方面： 1 互联网上存在一些信息量很少、价值很一般的网页。 2 互联网还存在着一词多义，同一个词在不同主题，不同领域，有其特殊的含义。 当用户在查询时，搜索引擎就会将各种情况都糅合在一起提交给用户。 3 重复页面多。由于常用文档的广泛传播和著名网页被其它站点的引用，互联网 上有许多的重复页面。研究表明，互联网上有6 0 的页面是重复页面【2 】。 4 大多数搜索引擎采用基于关键词的检索算法。因此，有一些人或公司就专门针 对这方面进行研究，为了提高自己网页的检索排名，采用一些不正当的手段。这样搜索 ”弓l 擎在搜索时就会优先搜索出质量一般的网页提交给用户。 面对互联网的种种问题，如何快速、准确地从互联网上获取有价值的信息，就成为 评价搜索引擎的重要指标，搜索引擎的排序算法也就成为了人们关注的主题。 1 2 国内外研究现状 p a g e r a n k 算法是1 9 9 8 年由s e r g e yb r in 和l a w r e n c ep a g e 3 1 提出的基于链接分析 第一章绪论 的网页排序算法。同年，j k l e i n b e r g 提出了h i t s 算法，接着相继出现了，如a r c 、s a l s a 、 p h i t s 等基于链接分析的页面分级算法。这些算法在实际的应用和使用中，取得了很好 的效果。 g o o g l e 是目前世界上很受欢迎的搜索引擎之一，它提供了较高的准确率和快速搜索 速度，这主要因为是g o o g l e 使用了复杂的文本匹配算法和p a g e r a n k 算法相结合的技术。 在p a g e r a n k 算法的基础上，很多学者相继提出了改进后的一些p a g e r a n k 算法。比 如华盛顿大学计算机科学与工程系的m a t t h e wr i c h a r d s o n 和p e d r od o m i n g g o s 【4 】提出的 结合链接和内容信息的p a g e r a n k 算法。还有，斯坦福大学t a h e rh a v e l i w a l a t 5 1 等人提 出的主题敏感的p a g e r a n k 算法。 在国内，也有一些学者提出了基于p a g e r a n k 算法的改进算法，比如，上海交通大 学宋聚平博士【6 】提出的结合网页h t m l 语言的p a g e r a n k 算法，以及北京大学计算机系【7 】 提出的利用h t t p 协议，记录网页最近一次被修改时间，作为控制参数，计算网页的排 名。 p a g e r a n k 算法中对于网页链出是同等对待，对于不同链接是不考虑其重要性的，然 而，在实际的w e b 链接中，不同链接其重要性是不同的。因此，j k l e i n b e r g 就提出了 h i t s 算法嘲，该算法引入了中心页( h u b ) 和权威页( a u t h o r i t y ) ，让其互相加强，从 而找到a u t h o r i t y 网页，实现w e b 结构及资源的自动发现。 1 3 本文的研究意义及主要工作 本文重点是对搜索引擎排序算法的研究，旨在通过对现有算法的修正，来提高搜 索引擎排名的查准率，提高现代网络的公平性。 本文的主要工作可以概括为以下几个方面： 1 首先对搜索引擎的相关知识和技术进行研究，分析了典型搜索引擎，还有搜索 引擎的相关知识和技术，以及搜索引擎的性能指标。 2 对经典搜索引擎排序算法p a g e r a n k 算法、h i t s 算法进行分析，分析其存在的优 缺点。 3 在现有p a g e r a n k 算法的基础上改进，改进后的p a g e r a n k 算法是一种基于用户 兴趣的网页相似度和时间反馈的综合排序算法。 4 原型系统研究和设计。 2 西北大学硕士学位论文 1 4 本文的组织结构 本文各章节的组织结构： 第一章介绍了本文的研究背景和国内外对该主题研究的现状，在此基础上提出本文 研究的主要内容和方向。 第二章对经典搜索引擎进行介绍，然后分析搜索引擎的工作原理和主要技术，以及 搜索引擎的主要性能指标，为后续章节评测搜索引擎性能提供理论支持。 第三章首先对经典搜索引擎排序算法进行研究，评价其优缺点，然后对现有国内外 针对p a g e r a n k 算法的改进算法进行剖析。 第四章是在第三章的基础上，提出了针对p a g e r a n k 算法改进的综合排序算法，该 算法综合了分类技术，引入了余弦相似度模型以及近似网页内容摘要信息，从而修正了 传统p a g e r a n k 算法，提高了系统的查准率，改善了系统的查全率。 第五章原型系统研究。在n u t c h 上构建搜索引擎，通过搜索h t t p ：w w w h a 0 1 2 3 c o m 网站上的网页，验证了修正后的p a g e r a n k 算法，经验证，修正后的算法可以提高搜索 结果的查准率，并在一定程度上改善了系统的查全率。 第六章总结和展望。对本文的工作做了总结，对以后的研究做了展望。 1 5 本章小结 本章首先介绍了本文研究主题的研究背景和国内外的研究现状，然后说明了本文研 究的意义和本文所做的主要工作，最后对本文的结构给出了总体框架。 3 第二章搜索引擎的相关知识 第二章搜索引擎的相关知识 1 9 9 4 年至今，搜索引擎的发展无论是在数量还是质量上都发生了很大的变化。 第一代搜索引擎的索引网页的数量少于1 0 0 万个j 很少重新搜集网页和更新索引， 而且这一时期的搜索引擎检索速度非常慢，一般都需要等待很长的时间。在实现技术上， 基本上是沿用较为成熟的信息检索技术，网络技术和数据库等技术。实际上，第一代搜 索引擎是利用一些现有技术，实现一个互联网上的应用。在当时，网络搜索程序每天承 受大约1 5 0 0 次的查询。 第二代以a 1 t a v i s t a 【9 】为代表的搜索引擎，大多采用分布式方式来提高数据的规模、 响应速度和用户数量等关键技术，这一时期的搜索引擎一般都保持大约一个5 0 0 0 万网 页的索引数据库，每天能够满足1 0 0 0 万次的用户检索请求。 第三代搜索引擎是指1 9 9 8 年开始发展起来的搜索引擎，这一时期的搜索引擎不仅 索引数据库规模空前的大，而且还出现了主题搜索和地域搜索，搜索数量和搜索质量也 明显提高，出现了搜索引擎的鼎盛时代。 2 1 搜索引擎的分类 搜索引擎【1 0 1 是指因特网上的在万维网中主动搜索信息并能自动索引、提供查询服务 的一类网站，这些网站通过网络搜索软件( 又称为网络搜索机器人) 或网站登录等方式， 将因特网上大量网站的页面收集到本地，经过加工处理而建成数据库，从而能够对用户 提出的各种查询作出响应，提供用户所需的信息。 搜索引擎按照搜索机制的不同，可以分为目录型、关键词型和混合型搜索引擎1 1 1 1 。 第一类是目录型搜索引擎，其典型代表是y a h o o ! ( h t t p ：嗍y a h o o c o m ) ，这类 搜索引擎是通过专业的网页编辑人员根据网站内容对网上的网页进行精选，建立一个索 引目录，给用户提供服务。这类通过手工维护的系统的优点是检索准确率高、检索明确， 可以有效的覆盖热门的主题，但它们的缺点是过于主观，检索范围小，容易产生漏检， 并且需要昂贵的代价来建立和维护，同时更新速度慢，不可能覆盖所有的主题。 第二类是关键词型搜索引擎，这类搜索引擎通过机器人程序自动、不断地从网上搜 集和分析网页，建立索引数据库，为用户服务。其典型代表是a l t a v i s t a 搜索引擎。这 4 西北大学硕士学位论文 类通过关键词匹配实现查找，并自动更新的搜索引擎，它们的优点是搜集的网页数量巨 大，形成庞大的数据库，实现了检全率高，能够全文检索的特点，但是同时出现了误检 率高，返回结果需要用户筛选的缺点。 在这种情况下，就出现了混合型中文搜索引擎，这类搜索引擎是目录式搜索引擎和 关键词搜索引擎的结合，用户可在某一分类下使用关键词检索，提高了检准率。 搜索引擎除了按照搜索机制分类，还可按其工作方式的不同，将其分为全文搜索引 擎( f u l lt e x ts e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和 元搜索引擎( m e t as e a r c he n g i n e ) 。通常我们所说的搜索引擎都指的是全文搜索引擎。 1 - 全文搜索引擎 全文搜索引擎是指从互联网上提取网站的相关信息，建立数据库，然后从数据库中 检索与用户相匹配的记录，再按照一定的顺序排列，将结果返回给用户。因此，全文搜 索引擎才是真正的搜索引擎。全文搜索引擎又可以按照搜索结果的来源，将搜索引擎分 为拥有自己检索程序的搜索引擎和租用其它搜索引擎的数据库的搜索引擎。第一种是拥 有自己检索程序的搜索引擎，这种搜索引擎自建网页数据库，检索结果直接从自身数据 库中调用；另一种是租用其它搜索引擎的数据库，按照一定的格式排列搜索结果。全文 搜索引擎的代表搜索引擎有g o o g l e 、a l t a v i s t a 等。 2 目录索引 目录搜索其实严格来讲并不是真正的搜索引擎，搜索结果的查询也不是进行关键词 查询，而是根据目录分类找到所需信息。目录索引中具代表性的搜索引擎有y a h o o 、o p e n d i r e c t o r yp r o j e c t ( d m o z ) 等。 3 元搜索引擎( m y r as e a r c he n g i n e ) 元搜索引擎是在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果 返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等( 元搜索引擎列 表) ，中文元搜索引擎中具代表性的有搜星搜索引擎。中文搜索引擎的排序结果，可以 按照来源排列搜索结果，比如d o g p i l e ；也可以按自定的规则将结果进行排序，比如 v i v i s i m o 。 除了以上的分类方式以外，还可以将搜索引擎分为集合式搜索引擎、门户搜索引擎 和免费链接列表三种。 1 、集合式搜索引擎：通常我们看到的h o t b o t 就是集合式搜索引擎，该搜索引擎是 由用户从提供的4 个搜索引擎中选择，而不是同时调用多个引擎进行搜索，因此称这类 第二章搜索引擎的相关知识 搜索引擎为“集合式 搜索引擎。 2 、门户搜索引擎：比如a o ls e a r c h 、m s ns e a r c h ，这种搜索引擎没有分类目录和 网页数据库，其搜索结果基本上都来自其他的引擎。 3 、免费链接列表( f r e ef o ra l ll i n k s ，简称f f a ) ：，这种搜索引擎的网站一般只 是简单地滚动排列链接条目，还有少部分采用分类目录。因此，这种网站的规模相对较 小。 这些搜索引擎虽然是非主流的搜索引擎，但是由于这些网站也是为用户提供查询服 务的，因此，我们将其也称为搜索引擎。 2 2 搜索引擎的工作原理 根据搜索引擎的分类，我们可以给搜索引擎下个定义，搜索引擎就是指从互联网上 搜集大量的网页，这些网页数量可以是几千万到几十亿，将搜集的网页中的关键字进行 检索，建立索引数据库的全文搜索引擎。当用户需要查找某个关键词，并将该关键词输 入，进行查询的时候，包含该关键词的所有网页都将作为检索到的结果被检索出来，再 经过排序算法计算之后，检索出的页面就将按照与该关键词相关度高低的顺序排列起 来。现有搜索引擎中普遍采用的技术是超链接分析技术，这种技术在分析网页时，不仅 要分析索引页中的文字，还要分析索引指向该网页的锚文档，甚至还要分析链接到网页 周围的文字。因此，这种技术的运用为提高查询结果的准确率提供了可能。 一般来说，搜索引擎系统的搜索过程是由三个阶段来完成，即抓取网页、加工处理、 查询服务这三个阶段。在组成上，搜索引擎一般是由蜘蛛程序( 也叫网页爬行器) 、切 词器、索引器、查询器几部分组成。蜘蛛程序其实是一个搜索程序，主要负责网页信息 的获取工作，一般是同切词器和索引器一起使用，它们共同负责将抓取到的网页内容进 行分词处理，并自动加注标引，建立索引数据库。查询器是根据用户提出的查询条件检 索索引数据库，并对检索出的结果进行集合运算和排序，再提取出网页中的简单摘要信 息提供给需要查询的用户。根据搜索引擎处理信息的过程，可以将搜索引擎的工作原理 分为三个步骤。 1 从互联网上抓取网页 利用s p i d e r 程序或者r o b o t 机器人程序，从互联网上自动抓取网页，并沿着任何 网页中的所有的u r l 地址反复搜索其他网页，并将这些网页进行收集、整理。 6 西北大学硕士学位论文 2 建立索引数据库 由分析索引系统程序对收集回来的网页进行分析，根据一定的算法进行大量复杂的 相关度计算处理，根据这些算法，利用网页中的网页文字和链接的每一个关键词的相关 度，建立网页索引数据库。 3 搜索排序 当用户输入关键词要求搜索后，由搜索系统程序从网页索引数据库中找到和该关键 词相符合的所有关联的网页，然后根据已有的相关度算法，对搜集到的网页进行相关度 数值的排序，相关度越高的网页，排名就越靠前。最后，系统将搜索结果返回给用户， 返回的页面中包括搜索结果的链接地址和页面内容摘要等信息。 根据搜索引擎的工作原理，搜索引擎系统一般是由数据采集、数据分析和数据查询 三部分组成。数据采集是由蜘蛛程序或网页爬行程序自动抓取网络上的页面，再将这些 页面存储到数据库中，然后对采集到的网页数据进行分析和处理，便于用户搜索查询。 通过分析，搜索引擎系统由搜索器、索引器、检索器和用户接口这四部分组成的【1 2 1 ，结 构如图1 所示。 2 3 搜索引擎的主要技术 图1 搜索引擎的系统结构 1 搜索器 搜索器通常是一个计算机程序，这个计算机程序主要是在互联网上不停地运行，当 发现需要的网页就去搜集和抓取，它要尽可能快而且尽可能多的搜集网络上各种类型的 信息，同时还要定期对搜集过的旧信息进行更新，以免在搜索时，出现死链接或无效链 7 第二章搜索引擎的相关知识 接。搜索器一般是由u r l 服务器( u r ls e r v e r ) 、抓取器( c r a w l e r ) 、存储器( s t o r es e r v e r ) 和u r l 解析器( u r lr e s o l v e r ) 四个部件组成，抓取器在该模块中处于核一t l , 地位。网页抓 取模块一般是由一个机器人( r o b o t ) 程序或一个蜘蛛程序来完成。 蜘蛛程序在搜集信息的时候一般采用以下两种策略： 首先任意选取一个起始的u r l 集合，然后顺着这个u r l 集合中的超链 接，用宽度优先或深度优先等方式，在互联网上循环地发现信息。虽然在选取起 始u r l 时是任意的，但在选择的时候，选取的常常是选取包含了很多链接的一些 非常流行的站点。 将w e b 空间可以按照域名，m 地址进行划分。每个搜索器负责一个区 域的搜索。搜索的类型包括网页文件、字处理文件和多媒体信息等。在搜索机制 的实现方面一般采用分布式技术和并行计算技术，这样大大提高了信息发现和信 息更新速度。 2 索引器 索引器的功能是对搜索器搜索到的信息进行理解，抽取出一些索引项，生成文档和 文档库，用这些文档库来表示索引表。索引表一般是一个倒排序表，即通过索引项，查 找相应的文档。索引表还要记录索引项在该文档中的位置，检索器就会根据此信息计算 出索引项之间的相邻关系。 索引器在理解信息的过程中，可以使用集中式或分布式索引算法，但是，当涉及的 数据量很大时，在系统中就必须实现即时索引( i n s t a n ti n d e x i n g ) ，否则就会出现速度不 匹配的问题。在检索中，索引算法的好坏直接影响着索引器性能的好坏，索引质量的好 坏直接影响到搜索引擎搜索性能的好坏。 3 检索器 检索器的功能是根据用户查询，在索引库中快速检索出所需文档，并且进行文档与 查询的相关度计算，同时对检索结果进行排序，并能够给用户提供相关性反馈机制。检 索器的信息检索模型一般有三种模型f 1 3 】，分别为基于集合理论的模型、基于代数理论的 模型和基于概率统计理论的模型。 4 用户接口 用户接口主要作用是方便用户使用搜索引擎，高效、方便、及时的找到有效信息， 并能显示查询结果和提供用户相关性反馈机制。在用户接口的设计上，设计人员主要考 虑要适合人类的思维习惯和使用习惯，一般采用人机交互的理论和方法设计。 8 西北大学硕士学位论文 2 4 搜索引擎的关键技术 在搜索引擎的众多技术中，多线程技术、网页抓取和超链接分析技术是其关键技术， 下面对其进行分析。 1 多线程技术：在搜索器搜索的过程中，需要抓取很多站点的u r l ，如果在搜索中 采用单线程蜘蛛程序搜索，那么在抓取时，速度就会很慢，不能满足用户的实际需要。 因而在实际的使用中，可以采用分布式、多线程技术，同时让多个蜘蛛程序同时抓取， 以提高搜索的速度。 2 网页抓取：网页抓取技术是基于网络的h t t p 协议。网络上的资源有很多种，比 如有网页、有w o r d 文档，还有其他类型的一些文件，所以在进行网页抓取时，需要指 出u r l 所指向资源的类型。 3 超链分析：超链分析技术的应用是搜索引擎很重要的一个环节，需要在搜索时对 h t m l 的各种标志要有全面的了解，需要对内容进行反复测试，还应考虑各种情形发生 的可能性。超链分析技术是提取出网页中相对于当前页的相对u r l ，因此需要将当前页 的相对u r l 转换成绝对的u r l 。在这个过程中需要根据当前页的u r l 作出各种可能的 判断。 2 5 搜索引擎性能评测指标 搜索系统要满足用户对信息查询的需求，提高用户的检索体验。需要几个比较重要 的指标。 1 网页覆盖率，即提高查全率，来保证查准率。 2 返回结果的准确性，要求返回结果中前几页的准确性要高。 3 重复信息的过滤，即返回结果尽可能不出现重复结果。 4 网页更新速度快。主要体现在新网页的发现和死链接的及时删除。如果结果中 出现大量的死链接和过时信息的链接，将会降低用户体验。 5 搜索服务的时间，也就是用户提交检索请求后得到结果返回的等待时间，一般 低于一秒一下。 6 搜索服务的系统稳定性。 因此，对于搜索引擎产品的评价，一般采用三级指标体系为评价标准【1 4 】，一级指标 9 第二章搜索引擎的相关知识 主要为搜索结果、搜索过程和搜索界面的评价，二级指标是一级指标的具体指标。搜索 结果的二级指标中有搜全率、搜准率、搜快率、无错率和相关率；搜索过程的二级指标 有功能性、反应速度、方便性；搜索界面的二级指标有界面美观和个性化。对于搜索引 擎中的二级指标搜索过程和搜索界面来说还有三级指标。在这些指标中，影响搜索引擎 性能的因素是多方面的，对于一级指标搜索结果来说，搜全率和搜准率的权值最高，分 别为0 2 6 8 和0 2 3 9 ，因此通过表1 搜索引擎的各级评价指标的权值可以看出，搜全率和 搜准率是影响搜索引擎的结果的关键因素。 表1 搜索引擎评价指标 一级指标二级指标三级指标序号权值 搜全率 l0 2 6 8 搜准率 20 2 3 9 搜快率3o 0 9 9 无错率 4 0 0 5 8 9 相关率 5 0 0 6 7 5 是否有高级搜索 60 0 3 6 1 搜索结果是否支持多国语言 70 0 1 2 7 是否有网页快照 80 0 0 7 7 功能性 是否有类似搜索90 o l 是否有附加功能：词典、计算器等1 00 0 0 7 2 是否有分类：图片、图像、论坛等 l l 0 0 2 8 9 进入搜索产品的速度 1 20 0 1 4 5 反应速度 翻页速度 1 30 0 0 8 1 l o 西北大学硕士学位论文 表l 搜索引擎评价指标( 续) 一级指标 二级指标三级指标序号权值 反应速度数据库更新速度1 4 0 0 3 是否有使用帮助 1 50 0 1 3 6 搜索结果 是否有下载功能条 1 60 0 1 2 7 方便性 是否有纠错能力( 错别字)1 70 0 0 9 9 支持关键词的多种输入方法( 拼音)1 80 0 0 9 6 页面设计( 美观、简洁、重点突出)1 9 0 0 0 9 6 页面美观 搜索界面 结果排序( 整齐、清晰、重点突出) 2 00 0 2 2 7 搜索页面设置( 显示条目设置) 2 10 o n 3 个性化 语言设置( 语言偏好设置) 2 2o o 1 0 4 虽然，搜索引擎不等于信息检索，但也属于信息检索问题，因此，对于搜索结果的 评测，也采用了评测信息检索系统的方法。目前，用于衡量检索系统性能的标准很多， 但一般是将相关性文档的排序作为其主要依据。在相关性文档的评测指标中，又以准确 率( 又称查全率) 和召回率( 又称查准率) 作为其依据。准确率p ( p r c c i s i o n ) 是指检索结 果中与查询相关的文档数和检索结果中的文档总数的比率，用来衡量搜索引擎的查全 率；召回率r ( r e c a l l ) 1 5 】是指检索结果中与查询相关的文档数和文档中所有与查询相关的 文档数的比率，用来衡量搜索引擎的查准率。在搜索引擎中，通常使用这两个指标对搜 索引擎系统性能进行评测。比如，可以用m 表示检索到的相关文档，t 表示检索到的不 相关的文档，n 表示没有检索到的相关文档，k 表示没有检索到的不相关文档，则评测 指标就可以定义为： 查全率p 刊( m + t ) 召回率 r - - m ( m + n ) 对于搜索引擎系统来说，用户总是希望获得最佳查全率和召回率相互结合的文档， 但是，在实际检索中要同时获得高的查全率和召回率是很难实现的。在实际应用中，查 准率高则查全率低，获得信息的绝对量就少；反之，获得有用信息的代价就高。目前， 第二章搜索引擎的相关知识 搜索引擎系统很难搜集到所有的w e b 网页，因此，要得到高的查全率就很难，相比较 而言，获得较高的准确率相对就容易一些。 2 6 本章小结 本章主要介绍搜索引擎的相关知识，分析研究了搜索引擎的定义和分类，以及搜索 引擎的工作原理，还有提出了搜索引擎的主要技术和评价标准。通过分析发现，影响搜 索引擎性能的关键因素是搜索结果，而影响搜索结果的关键指标是搜全率和搜准率。通 过对本章的分析和研究，目的是为后面的原型系统研究及算法验证，提供技术支持。 1 2 西北大学硕士学位论文 第三章经典搜索引擎排序算法研究 搜索引擎排序算法就是将搜索引擎查询结果按照一定规则排序，提供给用户的一种 方法。现有的大多数搜索引擎是以p a g e r a n k 算法、h i t s 算法为基础，通过链接关系找 到相对比较重要的网页，在此基础上，进行改良，形成综合的排序算法。 3 1p a g e r a n k 算法的分析 网页级别算法作为网页的组织管理工具，充分利用了互联网的巨大链接结构，即一 个网页被其他网页链接的数量就决定了该网页的重要性。网页分级算法可以保证系统对 用户的需求给出快速响应，把最重要的网页优先显示给用户。研究者分析发现在网络上 超级链接的结构是非常丰富、重要的资源。如果能够充分利用超链接的结构，就可以很 方便的实现网页的分级。基于这种超链接的思想，s e r g r yb r i n 和l a w r e n c ep a g e 在1 9 9 8 年提出了p a g e r a a k 算法，基于g o o g l e 的复杂文本匹配算法和搜索程序所使用的就是 p a g e r a n k 算法相结合的技术。通过p a g e r a n k 算法在g o o g l e 中的使用，可以证明，该 技术运用在搜索引擎中是非常有效的，特别是在网络资源膨胀的情况下。网络资源的膨 胀必然会产生很多的链接，这些链接的产生就为评价文件的重要性提供了更多的依据。 在网页分级算法中，除了考虑网页链接的数量之外，还要考虑分析被链接的网页。对于 重要的、高质量的网页在搜索结果中可以得到较高的网页级别，从而获得较靠前的排名。 所以，网页级别就成为网页重要性综合指标，代表了网页本身的特性，是网页数据采用 评定链接结构的综合运算方法进行分析的结果。 经过分析，得到高评价的重要页面就会给予较高的网页等级，那么它在搜索结果内 的排名也就会相应提高。下面是p a g e r a n k 和其它排名因子之间的对照【1 6 】。 表2 捧名因子对照表 捧名因子排名价值 网页雨t l e仅能被列出一次 正文中的关键词连续的重复只会降低关键词的重要性，重要的是接近度 第三章经典搜索引擎捧序算法研究 表2 捧名因子对照表( 续) 锚文本加权值极高，但存在上限，超过上限的将被忽略或降低权值 p a g e r a n k没有上限的限制，但需要大量工作 通过表2 排名因子对照表可以发现，对于页面中影响排名的因素来说，虽然 p a g e r a n k 因子需要大量工作，可是这些计算是不会影响到页面排名的，而其它因子会 因为这样或那样的原因而影响到网页的排名。网页的等级一般是由该页面的链入数量和 该页面的链入网页的p r 值，以及该页面的链入网页的链出数量决定的。因此，假如要 计算网页a 的等级，那么它的p r 值就是链入网页a 的页面除以该页面的链入页面本身 的链出数量的和，因此，其算法就可以定义如下： p 酬1 - d ) + d ( p r ( t o c ( t o + + p r ( t n ) c ( t n ) ) = ( 1 - d ) + d 喜笔署 ( 3 1 ) 其中，p r ( a ) 是页面a 的级别，p r ( t ；) 是页面t 。的级别，页面t ；链向页面a c ( t 。 ) 是页面t 。链出的链接数量，d 是阻尼系数，它的取值在0 - - - 1 之间，根据l a w r e n c ep a g e 和s e r g e yb r i n 给出的实际值，一般将d 在应用中设为o 8 5 。p r ( t 。) c ( t 。) 表示为每一 个指向a 页面的页面，重复相同的操作步骤。 该算法不以站点排序，页面的级别是由一个个独立的页面决定，每个链入页面的贡 献值都是不同的。如果t 页面中链出越多，它对当前页面的a 的贡献就越小。a 的链入 页面越多，其网页级别也越高。因此，决定页面级别的因素，主要是其页面的链入页面 数量。阻尼系数的使用，可以减少其他页面对当前页面a 的排序贡献。 l a w r e n c ep a g e 和s e r g e yb r i n 在解释该算法时提出了用户行为的随机冲浪模型( t h er a n d o ms u r f e rm o d e l ) ，他们把用户点击链接的行为视为一种不关心内容的随机行 为。用户单击页面内的链接概率，完全由页面上的链接数量决定。一个页面通过随机冲 浪到达的概率就是链入它的别的页面上链接的被单击概率的和。阻尼系数的引入，是因 为用户不可能无限地单击链接，常常会因为劳累而随机跳入另一个页面。d 可以看作用 户无限单击下去的概率，卜d 就是页面本身所具有的网页级别。 对于公式3 1 的p a g e r a n k 算法，可以进行修订，得到公式3 2 。 p r ( a ) = ( 1 - d ) n + d ( p r ( t 1 ) c ( t l 卜+ p r ( t n ) c ( t n ) 只l 司) n + d 喜笔等 ( 3 2 ) 其中，n 是互联网上所有网页的数量。在公式3 1 中，随机冲浪访问某个页面的概 1 4 硬北大学硕士学位论文 率由互联网的总数决定，而在公式3 2 中，网页级别是一个页面被随机访问的期望值( 为了计算简单，计算中是不考虑n 的值的) 。 3 2p a g e r a n k 算法的原理 对于p a g e r a n k 算法的原理，可以用图表来阐述。假设有五个网页a ，b ，c ，d 和 e ，他们相互链接。 图2 页面的链接 为了计算简单，可以将阻尼系数d 设为o 5 。则下面我们计算一下链接后这五个网 页各自的p a g e r a n k 的情况。 p r ( a ) = 0 5 + o 5 p r ( d ) p r ( b ) = 0 5 + 0 5 ( p r ( a ) 2 ) p r ( c ) = o 5 + o 5 ( p r ( b ) 2 ) p r ( d ) = 0 5 + o 5 ( p r ( a ) 2 + p r ( c ) + p r ( e ) ) p r ( e ) = 0 5 + o 5 ( p r ( b ) 2 ) 解得：p r ( a ) = i 2 5 9 2 5 9 2 6 p r ( b ) = o 81 4 81 4 8 2 p r ( c 户0 7 0 3 7 0 3 7 0 p r ( d 户1 5 1 8 5 1 8 5 2 p r ( e ) = o 7 0 3 7 0 3 7 0 有：p r ( a ) + p r 佃) + p r ( c ) + p r ( d ) + p r ( e ) = 5 在计算过程中，先给每个网页一个初始值。在迭代过程中，每个网页的网页级别的 和是收敛于整个网络页面数的。所以，每个页面的平均网页级数是l ，实际上的值在( 1 - d ) 和( 州l - d ) ) 之间。它们的迭代过程如表3 所示。 第三章经典搜索引擎排序算法研究 表3 迭代过程表 迭代次数 p r ( a )p r ( b )p r ( c )p r ( d )p r ( e ) 0lllll llo 7 50 6 8 7 51 5 9 3 7 50 6 8 7 5 21 2 9 6 8 7 50 8 2 4 2 1 8 7 50 7 0 6 0 5 4 6 8 7 51 5 2 0 9 9 6 0 9 3 80 7 0 6 0 5 4 6 8 7 5 31 2 6 0 4 9 8 0 50 8 1 5 1 2 4 5 10 7 0 3 7 8 11 31 5 2 0 0 4 2 4 20 7 0 3 7 8 11 3