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

第4章 搜索引擎体系结构概述本章内容： 搜索引擎体系结构； 数据抓取、内容索引子、链接结构分析、内容检索子系统的主要功能、性能要求、子系统间的配合方式。4.1 数据抓取子系统的主要功能与性能需求功能： 从万维网收集网页、网页间的超链接关系；收集的网页供内容索引子系统进行索引，收集的链接关系供链接分析子系统进行分析。工作方式1、收集“种子网页集合” (Seed Set , S )。2、“网络爬虫”(Crawler)访问S中超链接，抓取超链接对应的网页。3、构建S对应的出链接页面集合S1，访问 S1中所有超链接，抓取超链接对应的网页，构建S1对应的出链接页面集合S2 ；4、周而复始，抓取互联网上所有可以通过种子网页集合间接访问到的网页。抓取原理的伪代码如下：Spider ( S ) /输入种子集合S对应的URLGet( S)； /抓取S中的所有页面S/ = Resolve(S )；/提取S中各个页面包含的超链接URLSpider ( S ) ; ； /以S/为种子继续进行抓取 万维网任意两个网页间的平均距离是19个链接，呈现出“小世界”特征； 通过这种抓取方式获取互联网上的网页信息是可能的。性能需求：1、及时性及时性是指通过互联网数据的获取、更新，保证搜索引擎索引与网络数据的同步。网页更新频率：(1) 文学作品、文化知识介绍等类型的网页更新频率相对较低，内容较为稳定。(2) 博客、组织机构的主页等类型的网页更新频率相对较高，内容更新之间的间隔时间从几小时到几天、十几天不等。更新频率总体上而言是可以估计的。(3) 新闻、天气情况、股票指数、外汇牌价等类型的网页更新频率很高，更新间隔时间以分钟甚至秒来计算。搜索引擎抓取频率如何才能与互联网上的数据更新频率保持同步？解决办法： 数据抓取子系统的网页抓取的工作不停地运行； 对不同网页采取不同的抓取更新频率。 采取不同的抓取策略。 索引建立阶段：使用累积式抓取方式，对互联网上的网页进行依照链接结构关系进行全面的抓取； 索引更新阶段：采用增量式抓取的方式，既可以依据网页链接结构进行抓取，也可以根据搜索引擎判断的网页更新频率进行定向抓取。2、全面性搜索引擎对互联网上有用资源的覆盖率。抓取到的数据的质量、数量都应高，但更应该关注数据的质量。3、高效性带宽利用在有限的带宽资源下抓取数据、满足用户的信息需求。设，T：抓取时间内，S：满足用户信息需求的网络资源总量，B：带宽，则有一般，所需抓取的网络资源总量S/大于S。设抓取到的网络资源为用户所需要部分的比例为R ，不考虑带宽浪费的前提下，系统需要的网络带宽B/应当满足：由于实现的原因，数据抓取子系统能够利用的带宽往往低于网络实际可以提供的带宽。假设时间T内，带宽的利用率平均为U，则数据抓取子系统实际所需的带宽 B/应当满足：B/ = B/ / U= S/(T*U*R)减少系统所需带宽，在S、T 相对固定的情况下，关键在于提升所抓取到的万维网数据中有用数据的比例R、网络带宽的利用率 U 。提高R：避免互联网抓取中的“黑洞”。如下图所示的 “博客日历”，点击日期可阅读该日所写内容。每个日期都是一个超链接，“日期超链接”的数目无穷无尽。数据抓取子系统如果按链接分析方法进行抓取，会收集大量没有实际意义的无内容页面。 按黑洞类型，分别处理； 识别页面主体部分内容，以便抓取子系统忽略非主体内容中的“黑洞”链接。提升U ：提高带宽利用率的方法： 改进算法； 使用并行抓取策略； 合理利用被抓取网站服务器、带宽资源。 保证被抓取网站的正常访问与使用，又保证该网站内容及时抓取与更新。 频繁大规模抓取会产生与“拒绝访问攻击类似的效果； 抓取子系统效率会受影响，带宽资源消耗在无意义抓取、等待服务器反馈。robots抓取协议： robots.txt 文件存放在站点根目录下； 告诉抓取子系统，什么文件可以被抓取； 抓取子系统访问一个站点时，首先检查robots.txt； 如果存在，则根据文件内容确定访问的范围、方式，不存在，则不受限制地访问网站上所有没有被口令保护的页面。常用的robots .txt协议语句如下：/robots.txtUser-agent: BaiduspiderDisallow: /baiduUser-agent: *Disallow: /shifen/Disallow: /homepage/Disallow: /cpro/robots.txt# robots.txt for /User-agent: *Disallow: Disallow: /cgi-bin/Disallow: /home/Disallow: /phoenixtv/4.2 内容索引子系统的主要功能与性能需求主要功能：对数据抓取子系统收集到的网络数据进行索引，所索引的数据供内容检索子系统实现高效访问。 4.2.1 内容索引子系统的主要功能为什么要对网络数据内容进行索引，能不能把收集来的数据存储好，由内容检索子系统进行“全文检索”？如采用“从头至尾扫描”的检索方式，不需对数据进行事先组织整理，但每次检索都需遍历所有内容进行匹配，搜索引擎的效率不会高。所以搜索引擎需要内容索引子系统对数据进行组织整理。4.2.2 倒排索引结构定义：词项（Term）是具有一定概念的构成文档的基本单元，通常情况下与英文单词或中文“词”涵盖的意义类似。倒排索引：索引项是词项。下图中，通过访问词项，可以获得该词项出现的各个文档（记录在 DocX 中），以及这些文档中该词项出现的位置。 从文档到词项的转变过程：将文档通过词项切分操作转变成为词项集合。 搜索引擎只需读取倒排索引结构中与查询关键词（词项）对应的索引记录，即可获得出现关键词（词项）的文档列表，进而进行后续的文档相关度计算等操作。正排索引：索引项是文档。正排索引结构常用于记录文档对应信息(如网页质量、网页更新时间)、内容摘要等。4.2.3 内容索引子系统的性能需求内容索引子系统的性能需求： 充分利用系统资源 搜索引擎系统的索引规模应足够大，但大则耗费硬件资源多。 设计中重点考虑，保存尽可能多的“有用信息”，减少磁盘存储资源。 介质在面临大规模读写时也难免会出现硬件问题。 在倒排索引结构采用压缩算法以减少索引存储空间。 高效完成索引服务。 所建索引应支持快速响应用户查询。 从搜索用户的行为习惯出发，在保证服务质量的基础上提高服务效率。 少数查询量最大的查询就能够代表绝大多数的用户需求。 那绝大多数用户用到的网络数据，必然是与这少部分查询相关的资源。 5的索引数据即可以满足92的用户需求。 搜索引擎收集到的百亿计的网页中相当一部分对于绝大部分查询用户的信息获取没有帮助。摒弃这些部分页面，减少索引规模？第一级索引由网页中的权威站点首页织成，约有十几万到几十万个页；第二级索引由网页中的高质量页面组成，这部分网页约占中文网页总数的 5%左右，即由约几千万至几亿网页；第三级索引则是原有的网页索引，即包括所有网页内容的索引。4.3 内容检索子系统的主要功能与性能需求主要功能：输入：查询信息需求应用内容索引子系统提供的索引数据、链接结构分析子系统提供的分析结果，进行内容相关性计算 输出：以相关度进行排序的结果列表。“以相关度进行排序的结果列表” 为什么？4.3,1 内容检索子系统与文本信息检索系统 信息检索系统协助信息的潜在用户将信息需求转换为一张文献来源信息列表，而这些文献包含有对其有用的信息。 搜索引擎一种特殊的信息检索系统。相同点： 对用户查询进行检索服务，返回结果列表。检索算法 输入：倒排文档索引，查询词 输出：结果文档列表 对结果按照相关性进行排序。差别： 语料库集合搜索引擎处理的语料库是规模大、内容杂、动态变化的万维网； 用户群体搜索引擎的用户是兴趣爱好、知识背景、年龄结构差异巨大的网民。信息检索系统的用户是特定类型的用户。这两个差别造成了搜索引擎的内容检索子系统与文本信息检索系统的本质差异。 2000 年TREC评测 用同一数据集评价u 文本信息检索系统u 搜索引擎 一定程度上比较了搜索引擎内容检索子系统和文本信息检索系统相对性能 这种评价方式存在的问题u 索引数据规模：搜索引擎文本信息检索系统，u 标准答案集合：只限制在文本信息检索系统索引到的文档中，只被搜索引擎返回的正确结果并不被认为是标准答案 搜索引擎Google , NorthernLight , Fast , Lycos的内容检索子系统的性能优于文本信息检索系统 部分文本信息检索系统，如 OkaPi 系统，与部分搜索引擎性能相近 Okapi 等文本检索系统检索性能优于元搜索引擎MetaCrawle、目录式搜索引擎DMOZ 评测结论在索引数据相同或相似的情况下，搜索引擎内容检索子系统与文本信息检索系统的纯文本检索性能是类似的。存在问题 搜索引擎对“相关性”的标准是与文本信息检索系统不同的 搜索引擎用户信息需求无法从查询关键词中直接推知，而评测中使用的查询关键词都带有详细的信息需求描述 搜索引擎系统对内容检索系统的效率要求较高谷歌公司Jeff Dean评述：Right design at X may be very wrong at 10X or 100X4.3.2 内容检索子系统的相关性需求搜索引擎结果的相关性：带有信息需求（ Information Need , IN ）的用户在使用搜索引擎时，某结果Ri的相关性是指该结果满足 IN 的程度。结果Ri的相关性的大小只与其满足信息需求 IN 的程度有关，而与用户实际所采用的查询Q无关。文本信息检索系统：检索用户查询内容相似的文档，用户是否能够将信息需求用查询的形式表述清楚，系统不关注。搜索引擎：关注用户查询背后的真实信息需求，并以是否能够满足信息需求作为其结果是否“相关”的评价标准。两个中文搜索引擎关于“顾祝同将军简介”的结果列表 用户查询-信息需求：蒋介石嫡系将领顾祝同相关情况介绍 评价结果相关性不把结果内容是否包括顾祝同作为评价标准； 以满足“了解顾祝同生平情况”的信息需求作为评价相关的标准。内容检索子系统的排序因素。 结果页面本身的质量：结果页面来源网站的质量、是否高质量页面、是否垃圾页面 结果页面的组织形式：用户是否能够很快地通过阅读页面内容获得必要的信息 结果页面受欢迎的程度：有多少用户先前访问过该页面 结果页面内容新颖程度：页面更新周期，是否包含过期信息4.3.3 内容检索子系统的查询理解需求搜索引擎用户输人查询关键词内容检索子系统：通过查询关键词理解查询背后的信息需求。几个难点： 查询内容歧义性。“苹果”：电脑、音乐播放器、水果、电影名。“猎豹”：动物，汽车品牌。用搜索引擎搜索“苹果”，查询结果页面；l 苹果公司主页、l 苹果牌数码产品报价、l 水果苹果的百科知识、l 电影苹果的剧情介绍、l 香港苹果日报主页等有各种可能的歧义内容对应的结果，以满足用户针对不同歧义内容的查询需要。 应用文本聚类技术对查询结果进行聚类，每个类别提取出具有代表性的关键词作为“类别标签”。 // 信息需求歧义性“魔兽争霸” 有的用户是希望访问“魔兽争霸”游戏的官方站点； 有的是为了进行游戏下载； 有的则是为了阅读游戏的最新资讯。l 使用内容不包含歧义的关键词进行查询，用户的信息需求也可能完全不同；l 搜索引擎为确保各类信息需求都可以得到满足，必须分析用户的各种查询意图并尽量在结果中加以体现。查询内容、信息需求都无歧义，理解查询背后的信息需求也很困难。 搜索引擎面对的查询是十分简单的字词组合， 作者调查，查询所包含的平均词数为 3.11个用“清华大学”查询，查询内容清晰，信息需求类别也明确（导航类信息需求）， 信息需求也有差异l 访问清华大学主页l 访问清华招生网主页l 查看清华大学录取情况4.3.4 内容检索子系统的效率需求2003年，谷歌搜索引擎每日的用户查询次数就达到了2.5亿次，平均每秒钟近 3000 次 内容检索子系统算法的复杂性不能高l 不用：查询扩展、相关反馈、伪相关反馈等 内容检索子系统使用缓存算法提高系统效率l 少数查询量最大的查询就能够代表绝大多数的用户需求。l 把查询量较大的查询对应的结果加以缓存l 将查询量最大的查询对应的检索结果页面作为静态页面加以保存 保持同步？查询扩展(Query Expansion , QE)：是指为原始查询添加部分关键词，以组成一个能够获得更佳的检索效果的查询的过程。相关反馈(relevance feedback)：按照最初的查询条件，查询系统返回给用户查询结果，用户可以人为介入（或者自动）来选择几个最符合他查询意图的返回结果（正反馈），也可以选择最不符合他查询意图的几个返回结果（负反馈）。这些反馈信息被送入系统用来更新查询条件，重新进行查询。从而让随后的搜索更符合查询者的真实意图。伪相关反馈( Pseudo relevance feedback)：指无法获得用户直接的反馈信息，而只能将某些结果认为是用户反馈过的正反馈或负反馈结果的检索方法。4.4 链接结构分析子系统的主要功能与性能需求 互联网数据以超文本的形式组织；l 超文本含规范文字显示格式的标签；l 超文本包含链接到其他文档的超文本链接。 从当前阅读位置直接切换到超文本链接所指向的文字。 由链接结构分析子系统应用超链接，评价网络数据质量、扩展网络文档描述。4.4.1 基于链接结构分析评价数据质量链接结构分析 PageRank算法：”Page”+”Rank”，对网页(Web Page)进行排序(Rank)的算法? PageRank 取名自拉里.佩奇( Larry Page)。 PageRank衡量页面之间的相对质量关系，与用户查询无关的数值，采用离线方式计算，谷歌用于搜索结果排序的上百个因素中一个较重要的因素。为什么可用链接结构对网络数据质量进行评价？口碑的作用 Web中网页链接到高质量网页，以便提升自身的链接质量； 高质量网页会得到越来越多其他网页的链接； 链接结构分析算法，通过这种特殊的地位，区分网络数据的质量； 链接结构分析最早用在文献、情报科学领域，分析文献间的引用关系。4.4.2 基于链接结构分析扩展文档描述搜索引擎用户查询时常使用口语化、非正式的查询词。例如：查询“清华大学美术学院”相当一部分用户会使用“清华美院”进行查询。/上图是百度指数 ( http:/ ）统计的“清华美院”与“清华大学美术学院”两个查询词的查询量相互比较情况。两者之间的查询量差异很小，说明使用口语化、非正式的描述方式进行查询的用户有相当规模。但页面（尤其是权威网站、组织机构网站等包含的页面）的行文仍然保持着书面正式语言的特点。清华大学美术学院主页上没有出现任何一个“清华美院”的字样，而均用“美术学院”、“清华大学美术学院”来指代。用户和网页作者对同一查询对象的描述大相径庭的。网页作者个体对某个可能的查询对象的描述文字要与数以千万计的搜索用户的描述一一匹配，是非常困难乃至不可能完成的任务。造成用户查询无法与其目标页面的描述文字匹配的问题。如何能够保证不同用户提交的查询都能够定位到其查询目标呢？进行链接结构分析扩展文档描述超链接：两个网页间的一种指向关系，源网页是指包含超链接的网页，目的网页是被超链接所引用的网页。“链接文本”：用户在源网页中可以看见的描述链接的内容，如“清华大学美院”。链接文本：颜色、下划线。链接文本是由源网页的作者撰写的，该文本可以被认为是网页作者对目的网页内容的概括性描述。因此就可以使用链接文本扩展目的网页的描述文字，达到基于链接结构分析扩展文档描述的目的。南京艺术学院