当前位置:首页 >> 互联网 >>

第4章 搜索引擎体系结构概述


第 4 章 搜索引擎体系结构概述
本章内容:

? 搜索引擎体系结构; ? 数据抓取、内容索引子、链接结构分析、内容检索子系统的主要功能、性能
要求、子系统间的配合方式。

4.1 数据抓取子系统的主要功能与性能需求
功能:

? 从万维网收集网页、网页间的超链接关系;
收集的网页供内容索引子系统进行索引, 收集的链接关系供链接分析子系统 进行分析。

1

工作方式 1、收集“种子网页集合” (Seed Set , S )。 2、 “网络爬虫”(Crawler)访问 S 中超链接,抓取超链接对应的网页。 3、构建 S 对应的出链接页面集合 S1,访问 S1 中所有超链接,抓取超链接对应 的网页,构建 S1 对应的出链接页面集合 S2 ; 4、周而复始,抓取互联网上所有可以通过种子网页集合间接访问到的网页。

抓取原理的伪代码如下: Spider ( S ) { Get( S); //抓取 S 中的所有页面 //输入种子集合 S 对应的 URL

S/ = Resolve(S );//提取 S 中各个页面包含的超链接 URL Spider ( S ' ) ; }; //以 S/为种子继续进行抓取 }

? 万维网任意两个网页间的平均距离是 19 个链接,呈现出“小世界”特征; ? 通过这种抓取方式获取互联网上的网页信息是可能的。
性能需求: 1、及时性 及时性是指通过互联网数据的获取、更新,保证搜索引擎索引与网络数据的 同步。 网页更新频率: (1) 文学作品、文化知识介绍等类型的网页 更新频率相对较低,内容较为稳定。

2

(2) 博客、组织机构的主页等类型的网页 更新频率相对较高, 内容更新之间的间隔时间从几小时到几天、 十几天不等。 更新频率总体上而言是可以估计的。 (3) 新闻、天气情况、股票指数、外汇牌价等类型的网页 更新频率很高,更新间隔时间以分钟甚至秒来计算。

搜索引擎抓取频率如何才能与互联网上的数据更新频率保持同步?

解决办法:

? 数据抓取子系统的网页抓取的工作不停地运行; ? 对不同网页采取不同的抓取更新频率。 ? 采取不同的抓取策略。 ? 索引建立阶段:使用累积式抓取方式,对互联网上的网页进行依照链接结
构关系进行全面的抓取;

? 索引更新阶段:采用增量式抓取的方式,既可以依据网页链接结构进行抓
取,也可以根据搜索引擎判断的网页更新频率进行定向抓取。 2、全面性 搜索引擎对互联网上有用资源的覆盖率。 抓取到的数据的质量、数量都应高,但更应该关注数据的质量。

3、高效性 带宽利用 在有限的带宽资源下抓取数据、满足用户的信息需求。 设,T:抓取时间内,S:满足用户信息需求的网络资源总量,B:带宽,则有

B?

S T

一般,所需抓取的网络资源总量 S/大于 S。 设抓取到的网络资源为用户所需要部分的比例为 R , 不考虑带宽浪费的前提下,系统需要的网络带宽 B/应当满足:
3

B??

S? S /R S ? ? T T T ?R

由于实现的原因, 数据抓取子系统能够利用的带宽往往低于网络实际可以提供的 带宽。 假设时间 T 内,带宽的利用率平均为 U,则数据抓取子系统实际所需的带宽 B// 应当满足: B// = B/ / U= S/(T*U*R)

减少系统所需带宽,在 S、T 相对固定的情况下,关键在于提升所抓取到的万维 网数据中有用数据的比例 R、网络带宽的利用率 U 。

提高 R:避免互联网抓取中的“黑洞” 。 如下图所示的 “博客日历” ,点击日期可阅读该日所写内容。每个日期都是 一个超链接, “日期超链接”的数目无穷无尽。

数据抓取子系统如果按链接分析方法进行抓取, 会收集大量没有实际意义的 无内容页面。

? 按黑洞类型,分别处理; ? 识别页面主体部分内容,以便抓取子系统忽略非主体内容中的“黑洞”
链接。

4

提升 U : 提高带宽利用率的方法:

? 改进算法; ? 使用并行抓取策略; ? 合理利用被抓取网站服务器、带宽资源。 ? 保证被抓取网站的正常访问与使用,又保证该网站内容及时抓取与更新。 ? 频繁大规模抓取会产生与“拒绝访问攻击类似的效果; ? 抓取子系统效率会受影响, 带宽资源消耗在无意义抓取、 等待服务器反馈。
robots 抓取协议:

? robots.txt 文件存放在站点根目录下; ? 告诉抓取子系统,什么文件可以被抓取; ? 抓取子系统访问一个站点时,首先检查 robots.txt; ? 如果存在,则根据文件内容确定访问的范围、方式,不存在,则不受限制地
访问网站上所有没有被口令保护的页面。

常用的 robots .txt 协议语句如下:

http://www.baidu.com/robots.txt User-agent: Baiduspider Disallow: /baidu User-agent: * Disallow: /shifen/ Disallow: /homepage/ Disallow: /cpro

5

http://www.ifeng.com/robots.txt # robots.txt for http://www.ifeng.com/ User-agent: * Disallow: Disallow: /cgi-bin/ Disallow: /home/ Disallow: /phoenixtv/

4.2 内容索引子系统的主要功能与性能需求
主要功能: 对数据抓取子系统收集到的网络数据进行索引, 所索引的数据供内容检索子 系统实现高效访问。

4.2.1 内容索引子系统的主要功能
为什么要对网络数据内容进行索引,能不能把收集来的数据存储好,由内容 检索子系统进行“全文检索”? 如采用“从头至尾扫描”的检索方式,不需对数据进行事先组织整理,但每 次检索都需遍历所有内容进行匹配,搜索引擎的效率不会高。 所以搜索引擎需要内容索引子系统对数据进行组织整理。

4.2.2 倒排索引结构
定义:词项(Term)是具有一定概念的构成文档的基本单元,通常情况下与 英文单词或中文“词”涵盖的意义类似。 倒排索引: 索引项是词项。 下图中, 通过访问词项, 可以获得该词项出现的各个文档 (记 录在 DocX 中) ,以及这些文档中该词项出现的位置。

6

? 从文档到词项的转变过程:将文档通过词项切分操作转变成为词项集
合。

? 搜索引擎只需读取倒排索引结构中与查询关键词(词项)对应的索引记
录,即可获得出现关键词(词项)的文档列表,进而进行后续的文档相 关度计算等操作。

正排索引: 索引项是文档。

正排索引结构常用于记录文档对应信息(如网页质量、网页更新时间)、内容 摘要等。

4.2.3 内容索引子系统的性能需求
内容索引子系统的性能需求:

? 充分利用系统资源 ? 搜索引擎系统的索引规模应足够大,但大则耗费硬件资源多。 ? 设计中重点考虑,保存尽可能多的“有用信息” ,减少磁盘存储资源。 ? 介质在面临大规模读写时也难免会出现硬件问题。
7

? 在倒排索引结构采用压缩算法以减少索引存储空间。 ? 高效完成索引服务。 ? 所建索引应支持快速响应用户查询。 ? 从搜索用户的行为习惯出发,在保证服务质量的基础上提高服务效率。 ? 少数查询量最大的查询就能够代表绝大多数的用户需求。 ? 那绝大多数用户用到的网络数据,必然是与这少部分查询相关的资源。 ? 5%的索引数据即可以满足 92%的用户需求。 ? 搜索引擎收集到的百亿计的网页中相当一部分对于绝大部分查询用户的
信息获取没有帮助。

摒弃这些部分页面,减少索引规模?

第一级索引由网页中的权威站点首页织成,约有十几万到几十万个页; 第二级索引由网页中的高质量页面组成, 这部分网页约占中文网页总数的 5%左 右,即由约几千万至几亿网页; 第三级索引则是原有的网页索引,即包括所有网页内容的索引。

8

4.3 内容检索子系统的主要功能与性能需求
主要功能: 输入:查询信息需求 应用内容索引子系统提供的索引数据、链接结构分析子系统提供的分析结 果,进行内容相关性计算 输出:以相关度进行排序的结果列表。 “以相关度进行排序的结果列表” 为什么?

4.3,1 内容检索子系统与文本信息检索系统
? 信息检索系统 协助信息的潜在用户将信息需求转换为一张文献来源信息列表, 而这些文献 包含有对其有用的信息。 ? 搜索引擎 一种特殊的信息检索系统。

9

相同点: ? 对用户查询进行检索服务,返回结果列表。 检索算法 输入:倒排文档索引,查询词 输出:结果文档列表

? 对结果按照相关性进行排序。

差别: ? 语料库集合 搜索引擎处理的语料库是规模大、内容杂、动态变化的万维网; ? 用户群体 搜索引擎的用户是兴趣爱好、知识背景、年龄结构差异巨大的网民。 信息检索系统的用户是特定类型的用户。 这两个差别造成了搜索引擎的内容检索子系统与文本信息检索系统的本质 差异。

10

? 2000 年 TREC 评测 ? 用同一数据集评价 ? 文本信息检索系统 ? 搜索引擎 ? 一定程度上比较了搜索引擎内容检索子系统和文本信息检索系统相对性能

? 这种评价方式存在的问题 ? 索引数据规模:搜索引擎>>文本信息检索系统, ? 标准答案集合: 只限制在文本信息检索系统索引到的文档中,只被搜索引 擎返回的正确结果并不被认为是标准答案

? 搜索引擎 Google , NorthernLight , Fast , Lycos 的内容检索子系统的性能优于 文本信息检索系统 ? 部分文本信息检索系统,如 OkaPi 系统,与部分搜索引擎性能相近 ? Okapi 等文本检索系统检索性能优于元搜索引擎 MetaCrawle、 目录式搜索引 擎 DMOZ

11

评测结论 在索引数据相同或相似的情况下, 搜索引擎内容检索子系统与文本信息检索 系统的纯文本检索性能是类似的。

存在问题 ? 搜索引擎对“相关性”的标准是与文本信息检索系统不同的 ? 搜索引擎用户信息需求无法从查询关键词中直接推知,而评测中使用的查询 关键词都带有详细的信息需求描述 ? 搜索引擎系统对内容检索系统的效率要求较高

谷歌公司 Jeff Dean 评述:Right design at X may be very wrong at 10X or 100X

4.3.2 内容检索子系统的相关性需求
搜索引擎结果的相关性: 带有信息需求( Information Need , IN )的用户在使用搜索引擎时,某结果 Ri 的相关性是指该结果满足 IN 的程度。

结果 Ri 的相关性的大小只与其满足信息需求 IN 的程度有关,而与用户实 际所采用的查询 Q 无关。

文本信息检索系统: 检索用户查询内容相似的文档, 用户是否能够将信息需求用查询的形式表述 清楚,系统不关注。 搜索引擎: 关注用户查询背后的真实信息需求, 并以是否能够满足信息需求作为其结果 是否“相关”的评价标准。

12

两个中文搜索引擎关于“顾祝同将军简介”的结果列表 ? 用户查询---->信息需求:蒋介石嫡系将领顾祝同相关情况介绍 ? 评价结果相关性不把结果内容是否包括顾祝同作为评价标准; ? 以满足“了解顾祝同生平情况”的信息需求作为评价相关的标准。

13

内容检索子系统的排序因素。 ? 结果页面本身的质量: 结果页面来源网站的质量、是否高质量页面、是否垃圾页面 ? 结果页面的组织形式: 用户是否能够很快地通过阅读页面内容获得必要的信息 ? 结果页面受欢迎的程度: 有多少用户先前访问过该页面 ? 结果页面内容新颖程度: 页面更新周期,是否包含过期信息

14

4.3.3 内容检索子系统的查询理解需求
搜索引擎用户输人查询关键词

内容检索子系统:通过查询关键词理解查询背后的信息需求。

几个难点: ? 查询内容歧义性。 “苹果” :电脑、音乐播放器、水果、电影名。 “猎豹” :动物,汽车品牌。

用搜索引擎搜索“苹果” ,查询结果页面; 苹果公司主页、 苹果牌数码产品报价、 水果苹果的百科知识、 电影苹果的剧情介绍、 香港苹果日报主页等 有各种可能的歧义内容对应的结果,以满足用户针对不同歧义内容的查询需要。

15

? 应用文本聚类技术 对查询结果进行聚类,每个类别提取出具有代表性的关键词作为“类别标签” 。 http://clusty.com/ http://search.yippy.com/

? 信息需求歧义性 “魔兽争霸” ? 有的用户是希望访问“魔兽争霸”游戏的官方站点; ? 有的是为了进行游戏下载; ? 有的则是为了阅读游戏的最新资讯。

使用内容不包含歧义的关键词进行查询,用户的信息需求也可能完全不同; 搜索引擎为确保各类信息需求都可以得到满足,必须分析用户的各种查询意 图并尽量在结果中加以体现。

16

查询内容、信息需求都无歧义,理解查询背后的信息需求也很困难。 ? 搜索引擎面对的查询是十分简单的字词组合, ? 作者调查,查询所包含的平均词数为 3.11 个

用“清华大学”查询,查询内容清晰,信息需求类别也明确(导航类信息需求) , ? 信息需求也有差异 访问清华大学主页 访问清华招生网主页 查看清华大学录取情况

4.3.4 内容检索子系统的效率需求

2003 年,谷歌搜索引擎 每日的用户查询次数就达到了 2.5 亿次, 平均每秒钟近 3000 次

? 内容检索子系统算法的复杂性不能高 不用:查询扩展、相关反馈、伪相关反馈等

17

? 内容检索子系统使用缓存算法提高系统效率 少数查询量最大的查询就能够代表绝大多数的用户需求。 把查询量较大的查询对应的结果加以缓存 将查询量最大的查询对应的检索结果页面作为静态页面加以保存 ? 保持同步?

查询扩展(Query Expansion , QE): 是指为原始查询添加部分关键词, 以组成一个能够获得更佳的检索效果的查 询的过程。

相关反馈(relevance feedback): 按照最初的查询条件, 查询系统返回给用户查询结果, 用户可以人为介入 (或 者自动)来选择几个最符合他查询意图的返回结果(正反馈) ,也可以选择最不 符合他查询意图的几个返回结果(负反馈) 。这些反馈信息被送入系统用来更新 查询条件,重新进行查询。从而让随后的搜索更符合查询者的真实意图。

伪相关反馈( Pseudo relevance feedback): 指无法获得用户直接的反馈信息, 而只能将某些结果认为是用户反馈过的正 反馈或负反馈结果的检索方法。

18

4.4 链接结构分析子系统的主要功能与性能需求
? 互联网数据以超文本的形式组织; 超文本含规范文字显示格式的标签; 超文本包含链接到其他文档的超文本链接。 ? 从当前阅读位置直接切换到超文本链接所指向的文字。

? 由链接结构分析子系统 应用超链接,评价网络数据质量、扩展网络文档描述。

4.4.1 基于链接结构分析评价数据质量
链接结构分析 ? PageRank 算法:”Page”+”Rank”,对网页(Web Page)进行排序(Rank)的算法? PageRank 取名自拉里.佩奇( Larry Page)。 ? PageRank 衡量页面之间的相对质量关系, 与用户查询无关的数值, 采用离线 方式计算,谷歌用于搜索结果排序的上百个因素中一个较重要的因素。

为什么可用链接结构对网络数据质量进行评价? 口碑的作用 ? Web 中网页链接到高质量网页,以便提升自身的链接质量; ? 高质量网页会得到越来越多其他网页的链接; ? 链接结构分析算法,通过这种特殊的地位,区分网络数据的质量; ? 链接结构分析最早用在文献、情报科学领域,分析文献间的引用关系。

4.4.2 基于链接结构分析扩展文档描述
搜索引擎用户查询时常使用口语化、非正式的查询词。 例如:查询“清华大学美术学院” 相当一部分用户会使用“清华美院”进行查询。

19

http://index.baidu.com/

上图是百度指数 ( http:// index.baidu.com )统计的“清华美院”与“清华大学美 术学院”两个查询词的查询量相互比较情况。

两者之间的查询量差异很小, 说明使用口语化、非正式的描述方式进行查询的用 户有相当规模。

但页面(尤其是权威网站、组织机构网站等包含的页面)的行文仍然保持着书面 正式语言的特点。

清华大学美术学院主页上没有出现任何一个“清华美院”的字样,而均用“美术 学院” 、 “清华大学美术学院”来指代。

用户和网页作者对同一查询对象的描述大相径庭的。

网页作者个体对某个可能的查询对象的描述文字要与数以千万计的搜索用户的 描述一一匹配,是非常困难乃至不可能完成的任务。

造成用户查询无法与其目标页面的描述文字匹配的问题。

20

如何能够保证不同用户提交的查询都能够定位到其查询目标呢?

进行链接结构分析扩展文档描述

超链接:两个网页间的一种指向关系,源网页是指包含超链接的网页,目的网页 是被超链接所引用的网页。

“链接文本” : 用户在源网页中可以看见的描述链接的内容, 如 “清华大学美院” 。

链接文本:颜色、下划线。

链接文本是由源网页的作者撰写的, 该文本可以被认为是网页作者对目的网页内 容的概括性描述。

因此就可以使用链接文本扩展目的网页的描述文字, 达到基于链接结构分析扩展 文档描述的目的。

南京艺术学院工业设计学院 http://idc.njarti.edu.cn/ 网站中加人了链接,链接文本为:清华大学美院。

用链接文本扩展目的网页描述时,可以把“清华大学美院”加入到目的网页 (http://www.tsinghua.edu.cn/publish/ad/)的描述文字中.

这样,描述文字中既出现“清华” ,又出现“美院” ,用户使用“清华美院”进行 查询时,就可以匹配到其要查找的目标网页。

21

基于链接结构分析扩展文档描述的方法: ? 对不同源网页作者对同一目标网页的描述文字进行整合; ? 对目标页面描述的“一家之言” (目标网页作者的描述)就变成了“百家争 鸣” (目标网页作者以及多个源网页作者的描述) 。

4.4.3 链接结构分析子系统的效率需求
数据质量评估、扩展文档描述无需在线完成; 链接结构分析子系统的实时性和效率要求相对要略低一些。 链接结构分析子系统在设计时也不能忽视运行效率;

4.5 搜索引擎体系结构设计理念
? 用户需求驱动 根据用户需求确定网页抓取、更新的频率; 根据用户需求确定网页层次索引结构的组成; 根据用户需求确定结果的相关性; 要根据用户需求设计链接结构分析算法,确定网页质量评估的方式。

? 有损优化 搜索引擎: 资源极端密集; 有限的资源应用在合理地方。 数据抓取子系统:带宽优先供给抓取需要实时更新的网页; 内容索引子系统:词项在网页内容中的位置记录会被设定上限,超出上限长 度的网页位置信息记录的会不准确;层次索引结构中,高水平的硬件部件只 应用在高质量网页对应的索引上。 ? 重视效率 搜索引擎的数据规模、用户规模大,必须重视效率。 内容索引子系统:节约存储; 内容检索子:舍弃复杂度过高的算法;
22

链接结构分析子系统:把运算强度降到可接受的最低水平;

23


相关文章:
更多相关标签: