（计算机应用技术专业论文）支持查询剪裁的搜索引擎数据缓冲策略.pdf

浙江大学硕士学位论文 摘要 摘要 商用搜索引擎对查询请求的处理速度有很高的要求，尤其是在因特网已发展 到数百亿网页规模的背景下，如何在保证返回结果质量的前提下，尽可能提高搜 索引擎查询处理能力成为了搜索引擎等领域的研究热点，其中对索引系统的优化 是众多优化方法关注的核心环节。在目前所采用的搜索引擎优化技术中，查询剪 裁和缓冲算法是两种极为重要的搜索引擎优化方法。 本文研究了结合查询剪裁的搜索引擎数据缓冲策略，主要工作包括： ( 1 ) 提出了一种新的基于“关键词组合命中信息列表交集”的查询剪裁方 法。该剪裁方法利用“关键词组合命中信息列表交集”的组织形式能体现出网页 对于特定查询条件的重要性，实现了与基于查询网页评价函数有机结合，同时提 升精确匹配查询的处理速度。 ( 2 ) 提出了基于一种新的索引系统架构的搜索引擎数据缓冲策略。新数据 缓冲策略将高频关键词组合的命中信息列表交集放入缓冲区，综合利用离线和在 线替换算法提升该缓冲区的性能。同时，由于在传统索引系统架构上部署该缓冲 存在诸多局限性，该文提出了一种新的索引架构，利用这种索引系统架构，可充 分利用索引系统的硬件资源，并能显著增强查询剪裁算法的效能。 ( 3 ) 设计并实现了一个结合查询剪裁的搜索引擎缓存管理原型系统，该原 型系统实现了基本的索引予模块功能。对原型系统的一系列实验表明，应用文中 所提出的结合查询剪裁的搜索引擎缓冲策略，在保证搜索引擎返回结果未受明显 影响的前提下，对查询请求的处理达到了较高的查询剪裁率，有效的提高了搜索 引擎的性能。 关键词：搜索引擎，网页评价函数，查询剪裁，p a g e r a n k ，倒排索引，缓冲管 理，精确匹配查询 浙江大学硕士学位论文 摘要 a b s t l m c t n e r a p i dc x p l o s i o no fw e bp a g c si ni n t c m e tr e q u i r e ss e 砌e n 百n e t or e s p o n d t h o u s a n d so fq u e r i c sp e rs e 咖l d m 啊t oe n h 种c et h es p e e do fs e 缸c h 髓g i n ew 讪l o u t t h ed e g m d a t i o no fq u e r yq u a l i t yb e c o m e sah o “ni n f o 衄a t i o nr e t r i e v a lr e s e 缸c h e s d u r i n gt h eq u e r yp r o c e s s ，m o s tt i m ea r cc o n s u m e dt os c a nt h eh u g ei v e r t e di n d c x - h c n c e ，o p t i l i l i z a t i o no fi n v e n e di n d e xa c c c s si st h ek c yt oe 血a n c es e 疵he n 舀e p e r f b 珊粕c e r e c e n t l y ，m a l l y印p f o a c h e s h a v e b c e np m p o s e d ， i n c l u d j n g t h e t e c h n j q u e so fq u e r yp m n i n ga n d c a c h e q u e r yp n l n i n gi su s c df b ra v o i d j n gt h ew h o l ea c c e s so ft l l ep o s t i n gl i s t ，孤d b u 骶由g j st or c d u c e 也e c o s t m o s te v a l u a t i o nf i l n c t i o no fe x i s t i n gt e c h i i i q u 骼o n l yc o n s j d e r t h ef 砬t o ro fq u e r y t e 珊so rt h e 卸a l y s i so ft h ep a g c 冲u ti 印o r ea l li m p o n a n tf a c t o fo fm eq u e r y i nt h i sa n i c l e ，m e 卸t l l o rp r 0 1 ) o dt oe s t a b l i s hab i gb u 疵r i tr c s i d 锚b o t hi n m e m o r ya n dd i s k ，i nw h i c ht h ei n t c r s e c t i o no fh i g hf r c q u e n c yt e 瑚p a i 耐p o s t i n gl i s t i ss t o r c d t l l i sa n i c l ea l s op r o p o s e da na p p r o a c ho fq u e r yp n i n j n g nc 锄a c c e i e m t e t h ee x e c u t i o no fm u l t i t e 珊sq u e r yb yt h ei n t e r s e c t i o n ，w h i c hc a nb e 目o u p c db yt l l e q u e r y - b 雒e de v a i u a t i o nf i l n c t i o n t bm a k ea ni n t e g r a t i o no ft h ep r o p o s c dm e t h o d ，t h i sa r t i c i cp f 0 畔dai 删 i n d e x 删t e c t 眦e ，w h i c h 啪h 锄e 鼹t h er c u r c e si ni n d e xs y s t e me f f i c i c n t l y 她d e n h a n c et l l ee 饪e c to fq u e r yp m n i n gd 舢a t i c a y t h ee x p e r i m ts h o w st h a tt h e e wp m p o s c d a p p m a c hc a n n gu pt h e p e r f b 珊柚c co fi n d e xs u b - s y s t e md r a m a t i c a l l y 姐di nt h el n e a nt i m ek c e pt h et o p k r e s u l t sw e l l k e y w o r d s ：s e a r c he n 垂n e e v a l u a t i o f l l n c t i o n ，q u e f yp m n i n g ，p a g e r 卸l 【 i i i v e n e d i n d e x ，b u 妇c rm a n a g 唧e n t ，p h r a s eq u e r y i n g 2 浙江大学硕士学位论文 第一章绪论 1 1 背景 1 绪论 在信息爆炸的今天，因特网正经历着深刻的巨变，如今因特网上的网页数量 已达数千亿之多，上网的用户也达数亿，而且随着链接网络的终端种类( 如手机 等移动设备) 以及数量的急剧增加，不论是因特网上的网页数量，还是上网的用 户还会保持快速增加的趋势。 因特网上的海量网页数据集使人们难以寻找到真正有用的信息，因此，搜索 引擎成为了人们浏览因特网的重要帮手。目前，人们对搜索引擎的性能以及功能 要求日趋严苛，对搜索引擎的优化，特别是对索引子系统的优化，已成为了搜索 引擎研究的重点。 在正式展开本文的背景介绍之前。我们先对些基本名词做出解释。 1 1 1 基本名词解释 在开始我们的讨论之前，有必要对一些基本的名词进行解释。 命中( h i t ) 指一个二元组( a ，p ) ，其中p 是某个网页，a 是某个关键词，关键词a 出现 在该网页中( 可能是多次) 。 如果一个关键词和一个网页构成一个符合上述条件的二元组，那么也可以说 该关键词命中该网页。 索弓i ( i n d e x ) 以某种形式保存了所有的命中信息。 t 0 p _ k 特指搜索引擎返回给用户的前k 个结果，在查询中，用户往往最关注这前k 个结果。 命中信息( p o s t i g s ) 用来记录某个关键词在文章中的出现( 注意命中可能包含多个出现) 情况， 包括位置字体以及大小写等等，一般采用如下的表示方法 ( d 0 删，五“【d l ，d “，o 知f ，其中五一表示该关键词在该网页中出现的次数， d ”描述了这一次出现( 对此不同的搜索引擎采用不同的表示方法) 。 查询 原始查询条件就是用户输入并送交搜索引擎处理的一个字符串，经过一 浙江大学硕士学位论文第一章绪论 定的处理后，能够转化为一组关键词的集合，称为处理后查询，一般用下面 的形式表达：q h 忉，- f o ，f ，厶 。本文中，如不特殊说明，查询特指处理后 的查询。用户一定时间段内的查询记录，称为一个查询序列，在本文中，被 用来对搜索引擎进行性能评测。 精确匹配 如果一个网页p 精确匹配原始查询q ( 一个字符串) ，那么q 作为一个整 体出现在网页p 中。如果一个网页p 精确匹配处理后查询q ( 一个关键词集 合) ，那么将q 中关键词连接起来形成一个字符串s ，比方将“ 中国人民 ” 变成“中国人民”，s 出现在网页d 中。 精确匹配查询( p h r 稻eq u e r y i n g ) 这种查询明确要求搜索引擎只返回那些精确匹配原始查询条件的网页。 查询剪裁( q 眦r yp 姗i n g ) 完成一个查询需要遍历所有查询中关键词的p o s t i n gl i s t ，这种遍历对 以及c p u 的消耗是搜索引擎系统的瓶颈所在，尤其是在进行多关键词查询 时。所以人们尝试着使用查询剪裁技术，来使这种遍历p o s t i n gl i s t 的操作提 早结束，但需要注意的是对查询返回的网页，特别时t o p k ，其质量不能受大 的影响。 平凡关键词( m m o nt e 珊) 指用户输入查询请求时，有时会输入一些本身没有具体含意1 的关键词， 比如“的”，“个”之类，而且这些关键词出现的频率极高，为了提高搜索引 擎的性能，搜索引擎在处理原始查询条件时忽略，或禁止这类关键词进入处 理后的查询条件。 s t o 坤i n g h s t 搜索引擎中，用来存放平凡关键词的列表。 静态网页评价函数和动态网页评价函数 静态网页评价函数只根据网页本身的重要程度给出一个分数，相对网页 静态评价函数的是网页动态评价函数，这种函数会根据网页对不同查询条件 的重要程度，为网页给出一个分数。 1 1 2 搜索引擎的分类 搜索引擎发展至今一共经历了两代，按导航方式分成目录浏览式搜索引擎和 1 虽然说有些关键词孤立的看，其车身没有具体的意义，但如果放在一个查询中，作为整体来看，并不尽 然，本文在后面的章节中会讨论这个问题 7 渐江大学硕士学位论文 第一章绪论 基于关键词的搜索引擎。需要注意的是，虽然基于关键词的搜索引擎出现较晚， 最终也获得更大的成功，但是不能简单的说，第二代搜索引擎绝对优于第代搜 索引擎。 1 1 2 1 目录浏览搜索 这类搜索引擎将网站分门别类，建立网站目录提供给用户。由用户自己来选 择进入哪个条目的网站。这种搜索引擎由于主要靠人工分类，所以无法收录网站 的全部内容，而只摘抄网站的一些核心信息。 这种搜索引擎的优点在于目录结构清晰，用户的参与度更好，因而对于寻找 关于某个主题，而不是关键词的网页更为准确。但由于其只能依靠手工来编辑， 因而分类体系不规范。此外，数据遗漏和更新不及时是始终困扰这类搜索引擎的 问题。 雅虎( h t t p ：，n ) l n 】i y a h 0 0 c o m ) 是其中最著名的代表。 1 1 2 2 关键词搜索 这类搜索引擎将整个w e b 看作是一个海量全文数据库，使用全文检索技术。 一张网页被看作是一组关键词的集合，用户可以通过关键词来寻找匹配该关键词 的网页。显然，这类搜索引擎需要将网页的信息全部提取出来，并做出进一步的 处理，以建立起一个对关键词的庞大索引。形成鲜明对比的是，目录浏览式搜索 引擎基本不做或只做少量的网页分析工作。 在用户体验上，这样的查询方式更为快捷方便，省去了目录浏览式搜索引擎 中用户亲自寻找相关网页的麻烦。 同时基于关键词的搜索引擎试图对查询的结果进行了尽可能的优化，最普遍 的做法是： 它自定义一个尽可能合理的网页评价函数，用来给网页排序 它最关注t o p k 个返回的结果的准确与否 但是目前基于关键词的搜索引擎还是建立在词法分析基础之上。它对查询以 及网页不进行语义上的分析，加之不同用户对网页的价值评判有着不同的标准， 这样当进行与某个主题相关的搜索时，在用户对返回结果的满意度上，它反而不 如目录测览式搜索引擎。 这类搜索引擎的代表是g o 0 9 1 e ( 丛p ；地幽监g 螋垂：嫂) 。 本文的背景就设定为基于关键词的搜索引擎。这类搜索引擎的主要特征就是： 数据量极大，即使是索引文件也是以g i g a b y t e s 为单位； 对于查询处理速度有极高的要求，现在的商用的搜索引擎要求每秒钟能够处 理数干次访问 最前面的返回结果要求极为准确，或说在某一网页评价函数下，保证有最高 的价值。 浙江大学硕士学位论文第一章绪论 本文的工作就是在这样的限制下展开的。后文中，如果没有特殊说明，“搜 索引擎”就特指基于关键词的搜索引擎。 1 1 3 基于关键词的搜索引擎基本工作原理 搜索引擎一般由如下子系统组成。如图1 所示 图1 搜繁引擎系统构成 网络蜘蛛，又称“网络爬行者”( w e bc r a w l e r ) ，它的工作主要是定期根据预 先设定的u r l 地址去抓取相应的网页，它在整个搜索引擎体系中扮演着信息采 集者的角色。 索引模块用于建立关键词到网页的对应关系，是整个搜索引擎的核心部分。 现在索引形式一般都是基于倒摊索引( i n v e n c di n d e x ) 【2 】的，倒排索引由一系列 命中列表( p o s t i n gl i s t ) 组成，它表示一个特定的词在所有网页集合憾里“所有 网页”的特指搜索引擎覆盖的所有网页) 中的命中信息( p o s t i l l 黔) ( 当然，没有 命中的不用记录) ，下面给出一个简单的倒排索引结构图形式，这里伪仅仅保存 了位置信息( 参考1 1 1 节) ，如图2 所示。 9 浙江大学硕士学位论文 第一章绪论 ! h 知k 唧：鼬嫩 ； i v o b i | l a f y：! v 爿姗 ； l 叵西三e 卜挣屯叠耍西圈圈 i 叵亟二工珥h 墅雯亘堕圈 ! i 巨二二e h 屯鍪纛鬟冀鬻i ；篓季羹翌鬻羹墓篓翼篓鍪麓| ! 羹薹羹羹冀羹羹羹霎囊鎏i 螽t 菌霾耄雾强瞪 屹：唯z 曝理嘤灞甥璎峪譬埋那白；勤鼢臼白非如雕弛驰赙酶融醐i | 曼耋荪 甜莩鑫羞品绻涩嘴灞登灞解甄盔蛩， 誉螫封冀箱都 将用户输 入的查询条件作为参数之一。现在使用的网页评价函数往往是由多种因素结合而 成，但总的来说，用户的查询请求是对网页重要程度做出评价最重要的依据。 同时，搜索引擎的优化方法紧紧依赖于所采用的网页评价函数，所以对用户 查询请求的分析和统计是必要且有益的工作。我们会先对用户的查询行为做出分 析，在这个基础之上，接着对现有的搜索引擎优化方法逐个展开讨论。 2 1 对用户查询请求的分析 用户查询请求在如下方面与搜索引擎优化策略紧密相关： 一次查询平均输入的关键词数目 一次查询请求用户平均浏览的结果页面个数 查询中关键词的局部性，包括单个关键词，以及关键词组合的局部性 有关高频词 有关平凡关键词 关于高级查询条件的使用 在逐个讨论这些特征之前，我们有必要引入一些概念。在一个查询序列 0 u e r s 下，如果定义# q 为查询q 中所有的关键词个数，那么定义函数 t 凸f ( q矾 r 娜) t 罗 撑孽，此外定义q u e r m s 中包含的不同的关键词集合为 面。西一 t e 姗s ( q u e y r e s ) ，显然t c n t ( q u e r 愿s ) 搬e 娜q u e r 固s ) 。另外会话( s e 豳n ) 指的是用户在很短时间内进行的一组查询，这组查询具有如下特征：它们都围绕 同一个主题，而有一个或数个核心关键词，始终出现在每一次查询中。 网络的数据量近年来呈爆炸式的增长，但用户的查询习惯的改变却几乎不会 浙江大学硕士学位论文第一章绪论 在基于内容的搜索，多媒体搜索，数据挖掘，自然语言理解以及扩展用户界面等 方面取得新的进展。 可以想象，随着w 曲网络规模的急剧增长，搜索引擎必将变的更加智能化， 使用更友好，才能满足未来用户的信息需求。 1 2 本文的工作 在本文中，我们对搜索引擎优化方法以及处理精确匹配的算法进行了分析， 并在现有的搜索引擎优化方法，特别是在查询剪裁算法以及缓冲算法的基础上， 提出了一种新的查询剪裁方法，并保证当搜索引擎使用基于查询的网页评价函数 时，不会对返回结果产生大的影晌。在海量网页数据集合上，这种查询剪裁方法 可以有效增大搜索引擎的吞吐量，并减少褒询响应时间。 同时，为了在索引系统中应用本文提出的索引优化策略，我们采用了一种综 合的索引架构。 在一个内部的分布式倒排索引系统上，我们使用了大约一亿张左右的网页集 合，来验证我们的算法。这个实验表明：本文提出的算法对搜索引擎性能有明显 的提升作用，并且有较高的可行性。 1 3 本文的组织 第一章阐述了搜索引擎的应用背景及发展历史，简要分析了搜索引擎的基本 原理与架构。特别是针对本文要研究的论题，着重讨论了索引的结构以及各种网 页评价函数。 第二章分析了现有优化搜索引擎的策略和算法，着重探讨和本文关系比较密 切的缓冲算法以及查询剪裁方法。同时指出了这些算法中可能存在的局限性以及 可能的结合点。 在第三章中，我们针对现有搜索引擎优化方法存在的局限性，描述了一种结 合查询剪裁的搜索引擎数据缓冲策略。 在第四章中，为了配合本文提出的优化策略，我们提出了一种综合的索引系 统架构。 第五章里，我们在一个原型系统中开展了一系列的实验，以测试本文所做的 工作对搜索引擎系统带来的性能提升。 最后在第六章中，我们总结了本文，并对本文提出的搜索引擎优化方法给出 了一些改进意见。 浙江大学硕士学位论文 第二章搜索日l 擎优化方法概论 2 1 1 查询中关键词数目 对用户同志的分析研究表明，大多数查询包含较少的关键词，s p i n k 等人f 1 8 】 在分析了1 0 0 万条查询日志后，统计出平均一个查询包含的关键词为2 4 个， 2 6 6 的查询只包含一个关键词，3 1 5 包含两个关键词，1 8 2 的查询包含3 个 关键词。可以看到接近6 0 的查询是包含少于3 个关键词的多关键词查询。7 3 4 的查询是多关键词查询，4 3 左右的查询包含3 个或以上的关键词。 2 1 2 用户测览的结果页面 有8 5 2 的用户只浏览第一页的查询结果页面，也就是说8 5 2 的用户关注 的结果不会超过一个结果页面中包含的条数，而有9 5 7 的用户不会浏览超过三 页的结果页面【6 】，这为搜索引擎优化方法提供了有力的依据，因为用户只关注 t o p k 个结果，那么搜索引擎可以全力去优化t o p - k 个结果，而对后面的返回结 果可以适度的放松。这种对查询结果的放松，往往能使索引系统有效降低工作负 荷，因为匹配一个查询请求( 布尔关系模型函数返回为t m e ) 的网页总数远远大 于用户关注的结果数目。 2 1 3 关键词的局部性 查询关键词的分布表示，z i p f 原则1 吲同样体现在用户查询请求中，也就是 说存在少量高频出现的关键词。研究表明，经过s t o p p i n gl i s t 过滤的若干个高频 关键词( 其数量仅仅占# t e 咖s ( q u e r m s ) 的o 0 4 ) ，其出现的次数约等于 t c h t ( q u e r s ) 的1 1 5 【6 】，如果适当增大高频词的范围，可以预见高频词集合 中的元素能够在t c n t ( q u e r m s ) 中占到更大的比重。这表明用户的查询请求具有 很强的规律性，针对这种规律性，特别是对出现的高频词做出优化，可以设计出 良好的缓冲以及查询剪裁算法。 另外关键词的组合也同样具有类似的规律性。 高频关键词或高频关键词组合的另一个特征是：它在定的时间段内往往稳 定的高频出现，这是因为高频关键词在这一时间段内是人们关注的热点。 需要指出的关键词组合的出现是指： 1 z i p f 原则是指一个词在一个有相当长度的语篇中的等级序号( 该词在按出现次数排列的词表中的位簧 他称之为珈1 l 【，简称r ) 与该词的出现次数( 他称为丘q u c n c y ，简称f ) 的乘积几乎是一个常数( 啪s t a n l ， 简称c ) 用公式表示，就是fxf = c 当然用户查询请求的分析表明，z i p f 原则不是完全适用，但在整体 t ，这个原则是适用的 1 7 浙江大学硕士学位论文 第二章搜索引擎优化方法概论 其本身出现 作为查询的一部分出现 某些关键词组合作为查询的一部分高频出现，这是由查询的会话特征所带 来：当用户输入一个查询请求，如果他对搜索引擎返回的结果不够满意，那么他 会增加，或删减查询中的关键词重新进行查询，但核心的关键词组合代表了用户 查询的主题，往往是不变的。 2 1 4 高级查询条件的使用 b a l l l e 的研究中表明【5 】，只有不到5 的用户使用过搜索引擎的高级查询功 能，所以在本文中并不涉及到针对高级查询条件的优化。当然针对高级查询条件 的优化可以是下一步的工作。 2 1 5 小结 通过以上的讨论，我们总结用户查询请求的特征：关键词数目少于等于3 个 的多关键词查询占绝大多数；绝大多数用户仅仅关注t o p - k ；少量的关键词在一 定时间段内始终高频出现；少量的关键词组合在一定时间段内始终高频出现；搜 索引擎提供的高级搜索功能被绝大多数用户忽视了。 2 2 对精确匹配的进一步讨论 第一章的讨论说明了必须注意对精确匹配查询的处理，本文提到的搜索引擎 优化算法也试图能够保证搜索引擎精确匹配查询的功能。在这里我们进行更深一 步的讨论。 2 2 1 平凡关键词( m m o nt e 珊) 平凡关键词虽然其本身没有含意，但放到查询请求中，它却能体现出一定意 义，特别是当它是某专有名词的部分，比如在“故都的秋”( 一篇散文的名字) 中，中间的“的”字，在对“故都的秋”做精确匹配查询的时候是有意义的。 而且在禁止了平凡关键词之后，意味着部分查询条件的放松，比如查询“大 海啊故乡”，如果禁止了“啊”，那么查询条件就成为了“大海故乡”。对查询的 统计说明，8 4 【5 】的查询中包含了平凡关键词，对这些查询来说，查询的精度 在一定程度上就降低了。而且他们的研究还发现了一个现象，那就是只有在约 0 4 的查询中，平凡关键词是最后个关键词，这对于我们的优化工作具有定 浙江大学硕士学位论文 第二章搜索引擎优化方法概论 的参考意义。 正是由于平凡关键词在某些查询条件下具有“非平凡”的意义，所以，现在 各个搜索引擎也逐渐取消对这些平凡关键词的禁止。 2 2 2 精确匹配查询的实现方法 2 2 2 1 - 单纯使用倒捧索引 在这种情况下，算法很清晰简单： 1 在查询条件中选取p o s i i n gl i s t 最短的两个关键词a ，b 。注意要记住a ，b 在查询条件中它们之间的距离和先后关系，这样才能进行精确匹配。 2 取这两个关键词的p o s t i n gl i s t ，记为h 1 1 和h 1 2 ，找出匹配查询条件中它 们之间的距离以及先后关系的p o s t i n 萨，放入一个列表t l l l 。 3 如果查询条件已全部处理完毕，那么退出。否则取剩余关键词中p o s t i n g l i s t 最短的关键词，将其p o s t i n gl i s t 与t h l 相比较，将匹配它与已处理关 键词位置关系的p o s t i n g s 找出，把最终结果写入t m 。重复这一步。 显然单纯依靠倒排索引，即使引入了按区压缩的算法，其对磁盘的访问量也 是非常惊人的。由于这种算法的时间复杂度，的访问量与p o s t i n gl i s t 的长度成 正比，而平凡关键词的p t i n g l i s t 非常巨大，所以为了减少索引系统的负载，平 凡关键词在处理查询请求时会遭到禁止1 。 2 2 2 2 后词索引 正是由于单纯依靠倒排索引来进行精确匹配所需的巨大开销，一些研究者提 出了后词索引的概念【8 】，其主要思想是利用某关键词后可能出现的关键词对该 关键词的p o s t i i l g l i s t 进行分组。这样倒排索引就变成了一个三级结构，下面给出 一个例子，如图3 所示。 “删- r 酹 f 0 q 刊柱，艘州 舒组时册弱狰毒嘲 w | 】i d ，靠千 醺艇t i 山秤巾 l ml 叶 一姐 +叫3 l 。l 。【1 2 p t 址3 + 【2 3 ，弘1 l l l * t 7 7 ，1 【挣p ) i 书1 l l 峨l ，【艰) l 由e +叫l s 。耻l ，ls ，【i 呻p 、蝎s ，l ，【l l 一。7 4 t f 2 ，一，m 酏，秘1 t t l o l ，2 0 ，卜一_ 1 w1 + 罐e+叫2 8 1 3 + f 2 l ，l ，i p ，“1 【，4 碍砷l 抽m 脚妇+叫，o s 尊漕、2 ，【7 1 9 孵，* 3 2 1 、 2 5 竹k ) l h +叫王f 蛾l ；l 锚p t 挣，l 。h | * ) | 图3 用后词分组的倒排索5 1 当然前面已经说过，对平凡关键词的禁止逐渐在取消 浙江大学硕士学位论文第二章搜索引擎优化方法概论 。勰警 i 瓜蒜 f a n n l a c b 踺扁诃判襄( 畦 谶盘中) a n 恤 在! 啉i i i b 曲3 1 1 1 ：墨! ：l ! 习：! ：! ：黧：2 l 3 ，el 、1 ；f 1 2 】，一”3 4 3 【2 土j 4 1 l 。，。? 7 ，1 【2 朝v l s ，t t s 。1 ，l 卜。稻，1 i ”t 。7 ，3 j 3 s 聿。辱2 ，醪。l 1 8 l 卜 2 ，( 6 ，l t 【1 】) 。9 1 8 【i ss 4 。6 2 髓1 1 4 1 8 1 2 0 球i 图4 对高频词的p o 酬n g1 s t 使用后词分组 经过他们的实验，在进行精确匹配查询时，使用这种改良的后词索引系统， 只需比纯粹的倒排索引多使用3 左右的空间，就能使执行一个查询所耗的时间 减少三分之二。 这种策略给我们带来了重要启示：对于少数高频关键词建立类似于后词索引 的结构是一种行之有效的解决精确匹配查询的方法。但该论文中仅仅解决的是精 确匹配查询这一种情况，或说虽然他们的搜索策略也提供了对基于查询的网页评 价函数的支持，但是他们所使用的基于查询的网页评价函数不够准确，他们只是 给精确匹配查询的网页给了较高分数，但是对除此以外的情况不做任何处理。 此外该论文基于的是一种并不成立的假设：如果一个关键词是高频关键词， 那么某个包含它的组合也是高频关键词组合。 对以上提到的两个不足，我们试图在本文中给出一种解决方法。 2 3 搜索引擎的基本优化方法 搜索引擎系统是一个复杂的系统，在这其中索引系统最容易成为系统瓶颈， 人们对搜索引擎的优化也主要集中在对索引系统的改进。 索引系统性能优化方法在总体上朝两个方面努力：充分挖掘硬件系统的能 力，主要是提出更为有效的分布式算法。减少工作负载，包括提出压缩比更高， 而解压时对c p u 资源消耗较低的压缩算法【9 】；使用更有效的缓冲算法；使用数 据剪裁技术。这其中，缓冲算法以及数据剪裁技术和本文的主题有较大关系，我 们会对其重点分析。 2 1 浙江大学硕士学位论文 第二章搜索引擎优化方法概论 2 3 1 搜索引擎体系优化 g o o 出ef i l es y s t e 嘶1 9 】体现了最重要的搜索引擎体系优化思想：与其使用高价 的工作站服务器，不如使用大量的p c 作为服务器( 尤其当p c 价格大幅下降后) ， 即使单个p c 性能可能较低，也容易产生故障。 设计良好的分布式算法可以充分的挖掘整个p c 服务器集群的性能，使之性 能上远优于同样总价格的工作站服务器集群。而且设计良好的冗余技术，也能使 单台服务器发生故障带来的影响降至最低。可以说p c 服务器的大量使用，是 9 0 0 e 成功的重要因素。 现在应用的搜索倒排索引的体系一般包括数台索引服务器，每台负责处理一 段网页上的查询请求【1 0 】，然后将结果汇总到一台服务器上进行排序，最后将排 序后的结果返回给用户。在分布式索引系统中，最理想的状况就是完全平均的将 查询任务分摊到各个索引服务器。 2 3 2 缓冲算法 缓冲能够有效的降低对磁盘的i ，o 访问量，也是一种重要的搜索引擎优化算 法。 缓冲问题是指：给定一个固定大小的缓冲以及对硬盘上数据的一个访问序 列，每个被访问数据项都有不同的大小和磁盘加访问代价。在要求每次对文件 数据的访问都必须通过缓冲来完成的条件下( 即无论读写，都要求先将数据移动 到缓冲区) ，如何使磁盘玳) 的开销最小。 不过注意两点： 1 缓冲区中与磁盘中数据项存在某种对应关系，但是，磁盘中和缓冲区中的数 据可以不完全一样。 2 缓冲区同样可以是磁盘。 前面通过对用户请求的分析发现：用户的查询请求具有很强的规律性，特别 是局部性，因而可以利用缓冲机制来降低对磁盘i o 访问的开销。 缓冲算法可以按照是否了解即将访问的数据分为o m i i l e 以及o n l j n e 两类， 也可以根据数据项的缓冲特征分成若干类。 2 3 2 1 o m 抽e 如果我们预先知道将要访问的数据项序列，并基于此事先在固定大小的缓冲 放入数据，在不使用换入换出操作的情况下，使访问这些数据需要最少的开 销。这就是所谓的o f l i n e 缓冲问题。 事实上我们无法知道将要访问的数据序列，但是通过对最近访问的数据项序 浙托大学硕士学位论文第二章搜索引擎优化方法概论 列的分析，我们可以对将要访问的数据序列做出预测。于是基于最近访问的数据 项序列，同样可以达到较好的效果。 不幸的是0 ：丘l i l l e 算法是n p 完全问题【1 1 】，所以我们提出了一种简单的贪心 算法用来近似实现o m i n e 缓冲算法的效果。后面在具体分析讨论我们提出的搜 索引擎优化算法时，我们会给出其算法。 2 3 2 2 0 n l i 耻 与o f f l i n e 算法相反，o n l i e 缓冲算法不根据未来的数据访问序列来决定事先 应当缓冲哪些数据。 其实我们常见的缓冲算法都可以归于o n l i n e 算法，比如u t u ，s l r u 以及2 q 【1 3 】等算法，在搜索引擎中，l a n d l o r d 【1 2 】缓冲算法获得了较为广泛的使用。我 们在实验中同样采用了l a n d l o r d 缓冲算法，后面在具体分析讨论我们提出的搜 索引擎优化算法时，我们会给出其算法。 2 3 2 3 数据项的缓冲特征 数据项的缓冲特征分为以下几类： 统一大小，统一访问代价- 这种情况又被称为页替换，操作系统中管理内存的页机制可以近似认为是这 种情况。这其实是一种理想的情况。 统一大小，不同的访问代价 不同大小，旧访问代价取决于数据大小 在有些应用中，需要缓冲某个文件里的不定长记录，就属于这种情况。 不同大小，访问代价难以预料 这是搜索引擎里最多出现的数据类型：包括结果缓冲，因为一个查询结 果集的大小和执行查询所花的代价没有直接关系。另外p o s t i i l gl i s t ，以及网 页数据也是这种类型，因为这些数据往往分散在磁盘中不同的b l o c k 存放， 因而即使是访问同样大小的数据，所消耗的磁盘时间也可能变化极大。特别 是如果数据要通过网络来传输，那么访问的代价更是多变。 在搜索引擎中的整个体系里，可能存在一种以上的数据类型，所以有必要在 不同缓冲区采取不同的缓冲算法。 2 3 2 4 搜索引擎的缓冲体系 一般说来，搜索引擎体系中最少需要两级缓冲【1 4 】，即查询结果缓冲以及命 中列表缓冲。 结果缓冲 1 在搜索引擎这个特定的应用环境下访问代价实际上并不仅仅包括l ，0 访问代价，比如在存取压缩数据的 时候，压缩懈压缩的代价也必须算在访问代价中 2 3 浙江大学硕士学位论文第二章搜索引擎优化方法概论 结果缓冲直接存放查询结果，是最接近用户的一层缓冲，所以结果缓冲 能够极大的加快查询速度，而且实现起来也比较容易。结果缓冲中存放的数 据，不但用来向随后的相同的查询请求返回结果，同时也是支持查询结果多 页面显示的必要手段。 结果缓冲的缺点在于，它只能过滤掉单关键词查询和双关键词查询( 如 果结果缓冲只对这两种查询缓冲) 。那么在真正交由后台索引服务器负责的 查询中，三个或以上关键词的查询的比重会有所上升。 命中列表缓冲 命中列表缓冲位于索引服务器中。由于倒排索引存放在文件系统里，实 际上文件系统已经对经常用到的命中列表进行了缓冲，但是有的搜索引擎公 司试图使用具有极大内存的索引服务器，他们试图将倒排索引整个放到内存 之上，自己进行缓冲管理。可以预见，这样的索引系统性能会大幅提高。 2 3 2 5 一种综合的缓冲算法 前面我们已经讨论了o f f l i n e ，o l i n c 缓冲算法，并指出索引系统缓冲中数据 的缓冲特征是不同大小，难以预料的访问代价。 在前面对用户查询请求的分析中，我们看到某些高频关键词具有在一定时间 段内稳定高频出现的特性。基于这个现象，xk m g 等研究者提出了一种综合的 缓冲算法【1 5 】，这种算法对于我们的工作具有较大的启发意义。 回忆前面对o m i n e 缓冲算法的描述，使用o m i n e 缓冲算法的缓冲区，是不会 有换进换出的操作的，这意味这这块缓冲区是只读而且稳定的。而由于某些高频 关键词在相当长的一段时间内稳定的高频出现，所以这些关键词正好可以放入使 用o m i n e 缓冲算法的缓冲区，这个缓冲区被称为静态缓冲区。 不过这里静态缓冲区并不是完全静止，搜索引擎会周期性的分析前一段时间 的数据访问序列，并依据分析结果将数据放入静态缓冲区。 当然，可能存在一些高频词只是在短时间内高频出现，所以仍需要开辟一块 采用动态缓冲算法的缓冲区，这个缓冲区采用的缓冲算法可以使用u t u ，2 0 等 等。 这种算法主要的优点在于静态缓冲区的只读特性，访问这块缓冲区能够避开 使用繁琐的同步机制。实验表明，不使用同步机制后，缓冲在多线程环境下性能 也没有明显的下降。 另外，在搜索引擎的二级缓冲体系之外，还可以加入一层中间缓冲【1 1 1 。这 层中间缓冲存放高频出现的关键词组合的p o s t i n gl i s t 交集，在前面对用户查询请 求的分析中可以看到，存在一些高频出现的关键词组合。而p o s 血gl i s t 的交集长 度往往远远小于原关键词组合的p o s t i n g l i s t ，也就是说缓冲中存放的数据一一某 两个关键词p o s 缅gl i s t 的交集不但长度不一样，对其访问的代价也不一样，这是 浙江大学硕士学位论文第二章搜索引擎优化方法概论 词的网页评价函数将h 个得分最高的网页( p o s t i n 擎) 放进f a n c yl i s t ，将剩余的 p o s t 纽窑s 放入n o 衄a ll i s t 。所有的强c yl i s t 组成一级索引，n o 咖a ll i s t 组成二级索 引。在这两级索引中，静态网页评价函数值都是排序的标准。 当进行双关键词查询时，具体的做法是：取两个关键词在一级索引中的 p o s t i n gl i s t ，进行集合与的操作，剩下的关键词放进两个列表l 1 ，l 2 。如果集合 与操作后得到的结果不够m 个，那么接着同时扫描两个关键词对应的0 m a l l i s t ， 这里用l 3 ，l 4 来代表。如果我们发现一个网页同时出现在l 3 ，l 4 或l 3 ，l 2 或l 4 ，l 1 中，那么保存下来该网页对应的p o s 血g 。直到我们找到m 个p o s t i n g s 。 对这m 个p o s 咖g s 再次应用搜索引擎采用的网页评价函数来排序，选取t o p k 。 的实验表明，无论采用以上哪种动态数据剪裁方法，只要m ，以及对f a n c y f j r s t m 算法中的缸l c yl i s t 长度选取合理，就能够在保证在返回较为准确t o p k 的 前提下，大大减少查询的工作量。 这种算法实现起来较为简单，具有较高的可行性。 2 3 - 3 2 静态数据剪裁 静态查询剪裁方法又称预计算数据剪裁方法，意思是给定一个网页评价函 数，如果可以确定一个p o s t j l l g 几乎不会出现在任何一个t o p k 中，那么就可以不 用存储这样的p o s t i n g 。这样做不但减少了对索引文件的访问量，还减少了索引 文件的大小。 d c a 瑚e l 等研究者提出了一种静态查询剪裁算法【2 1 】，他们对返回结果也做 出了定量的分析。首先，他们引入了网页评价函数f 变体的概念，即如果下面的 条件： ( 1 一) e ( d ) s ( d ) s ( 1 + ) e ( d ) 成立，那么就称网页评价函数e 是网页评价函数e 的变体。 在论文中，他们所使用的网页评价函数是 e ，q ) 一a ；爿辑，d ) 其中d 代表网页，q = f 1 ，乞，) ，是一个查询。a 为基于关键词的网页评价 函数，定义为： 删，：举 d ，为影响因子，定义为 浙江大学硕士学位论文第二章搜索引擎优化方法概论 一嚣 可咀看到，dc 锄e l 等研究者在论文中使用的网页评价函数是纯粹的动态网 页评价函数。 这篇文章的目标就是：给定s ，试图找出个门槛值f ，对每个关键词的 p o s t i n gl i s t ，删掉其中a ( t ，d ) 1 + 酗i 其中口为影响因子，一般设为5 。 就可以进入动态缓冲区。 浙江大学硕士学位论文 第四章索引系统架构的优化策略 其中，a 到l 是关键词，1 到8 是网页，“+ “代表命中，号，昱，b ，只是四台 索引服务器。 在这种架构中，单关键词查询只需要找到存储该关键词p o s t i n gl i s t 的服务器， 取p o s t i n gl i s t 中若干个最重要的p o s t i n g s 返回即可。对于多关键词查询，就需要 将查询中所有关键词的p o s t i n gl i s t 集中到一台服务器上进行集合交的运算，才_ 司 能完成查询。 很明显，全局索引架构的并行性很差。因为绝大多数查询中不会有超过3 个 的关键词，也就是说，对于绝大多数查询，不会有超过3 台索引服务器来参与执 行。 同时，采用全局索引很容易产生热点问题：如果某个关键词在一段时问内是 查询的热点，那么存储该关键词p o s t i n g l i s t 的索引服务器就会成为整个索引系统 的瓶颈。 使用全局索引必须使用网络来传输关键词的p 0 s t i gl i s t ，对网络带宽的消耗 也不容忽视。 上述是全局索引的弱点，但全局索引也有其优点： 在应用查询剪裁技术时更有优势。因为它的f a n c yl i s t 是全局意义上的f a n c y l i s t 。在4 2 节，我们还会就这个问题进行深入讨论。 使用全局索引的索引系统，返回的网页结果已经是合并的结果，不需要合并 服务器进一步的排序。而且网页结果是完全精确的一一对于搜索引擎采用的网页 评价函数，这些网页结果就是最重要的。 4 1 2 局部索引 在这种索引架构中，每个关键词的p o s t i n g l i s t 被分成若干个区间，分别存放 于不同的索引服务器，每台索引服务器包含所有关键词在某个特定区间的 p o s t i n g s 。如图7 所示： 浙江大学硕士学位论文第四章索引系统架构的优化策略 2 3 4 567b p p 2 1 p 3 j p 4 i 图7 局部索引示意图 其中，a 到l 是关键词，1 到8 是网页，“代表命中，号，县，b ，只是四台 索引服务器。 在这种索引架构下，对于任何查询，索引服务器之间都不需要有交互。每台 索引服务器独立完成自己的工作，找出在自己负责的网页区间内对查询最好的结 果集。然后交由一台合并服务器将结果合并排序并返回。 注意，如果要求整个索引系统返回完全正确1 的t o l p k ，只有让每一台索引服 务器都至少返回k 个结果，而不是k n ，这里n 是索引服务器的数量。搜索引擎 将这n + k 个结果排序后都返回给用户，最前面k 个结果是完全正确的。 局部索引架构能够获得非常好的并行性，因为完成个查询需要所有索引服 务器的共同合作，但是这并不意味着：所有的索引服务器都承担了相同的工作负 载。 这是因为p o s t i n gl i s t 在不同的网页区间内分布十分不均匀。假设s p i d e r 以追 这里指与全局索引架构下返回的协p k 完全一样 a 盐 c n 芷 f g j k l 浙江大学硕士学位论文第四章索引系统架构的优