引言

推荐教材

搜索引擎技术基础

关注搜索引擎的原因

1. 互联网上最重要的应用系统
2. 人类历史上最大规模的信息集散平台
3. 学术界重要的研发平台
4. 经济领域能够盈利的“生意”

搜索引擎发展历史（略）

搜索引擎体系结构概述

体系结构包括一组部件以及部件之间的联系。

对于搜索引擎而言，其体系结构是指为搜索引擎运行而设置的软硬件系统，以及软硬件系统之间的相互联系的总和。
为容纳万维网以爆炸式增长的数据，各大搜索引擎都使用规模浩繁的计算机集群系统对这些数据加以存储和处理。

搜索引擎简介的背后，是复杂的系统软硬件。

搜索引擎主要组成：

1. 数据抓取子系统

2. 内容索引子系统
3. 链接结构分析子系统
4. 内容检索子系统

搜索引擎系统架构示意图

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

主要功能

• 数据抓取子系统的主要功能，是及时、高效地收集数量尽可能多的有用的万维网页面，以及建立它们之间的超链接关系。它在整个搜索引擎系统中承担着与互联网数据进行交互的任务，它收集的数据是内容索引子系统索引的对象，而它所收集的数据之间的链接关系也是链接分析子系统进行分析的依据。
• 数据抓取子系统的核心任务是收集“网页”与“链接内容”。

• 数据抓取子系统的工作方式：

  
  数据抓取子系统工作的“链式原理”

具体来讲，数据抓取子系统工作的方式是一个“一传十，十传百，百传千万”的过程。首先，系统收集一部分热门程度和权威度都较高，同时具有较多超链接的网页（如网页导航类站点、门户类站点等），这部分站点被称为“种子网页集合”（Seed set,S）。随后，数据抓取子系统通过被称为“网络爬虫”（Spider,Crawler）的程序访问S中所有网页对应的超链接，抓取超链接对应的网页，构建S对应的超链接页面集合S1。进一步，爬虫访问S1中所有网页的超链接，抓取这些超链接对应的网页，构建S1对应的超链接页面集合S2，......，周而复始，抓取互联网上所有可以通过种子网页集合间接访问到的网页。其抓取原理的伪代码：

Spider(S)
{
  Get(S);
  S' = Resolve(S);
  Spider(S');
}

• 根据国外学者的研究结果，万维网任意两个页面间的平均距离是19个链接，呈现出明显的“小世界”现象[^Small-world experiment]的特征，这使得通过这种抓取方式获取互联网上的页面信息成为可能。
  [^Small-world experiment]:若网络中任意两点间的平均距离L 随网络格点数N 的增加呈对数增长，即 L ~ l n N ， 且网络的局部结构上仍具有较明显的集团化特征，则称该网络具有小世界效应，这里的平均距离具有广泛的含义，例如在上述信件传递实验中，平均距离就是平均传递次数 6。

性能需求

1. 及时性

及时性方面的要求，是指数据抓取子系统需要通过对互联网数据的获取和更新，保证搜索引擎索引与网络数据的同步。

网页抓取的工作无时无刻不在进行，通过这种方式，才能保证数据抓取子系统能够及时地抓取到更新的内容，进而使搜索引擎索引到的内容与互联网内容一致。搜索引擎往往采取不同抓取更新频率的方法，保证数据集合总体的“新鲜度”维持在一个较高的水平。

• 为了与这种对不同网页采取不同抓取更新频率的网页抓取方式相适应，数据抓取子系统通常在索引建立和更新的阶段采取两种不同的抓取策略。
  索引建立阶段，通常使用的是积累式抓取的方式，对互联网上的网页进行依照链接结构关系进行全面的抓取；
  索引更新阶段，则往往采用的是增量式抓取的方式，既可以一句网页链接结构进行抓取，也可以根据搜索引擎判断的网页更新频率进行定向抓取，以保证搜索引擎索引内容与网络页面内容尽可能一致。

2. 全面性

除了及时性方面的需求之外，数据抓取子系统在保证页面索引数量方面也有较高的性能需求。

随着越来越多的互联网数据资源以网络数据库的形式存在，当前数据抓取子系统在保证页面索引数量方面的主要需求转化为抓取互联网动态网页，或称为“暗网”（The Hidden Web,The Deep Web）。

3. 高效性

系统运行效率是数据抓取子系统需要关注的另一个主要性能指标。如何利用有限的带宽资源（受到预算开支限制）抓取数据、满足用户使用搜索引擎的信息需求是数据抓取子系统的性能需求之一。

• 假设一定时间T内，满足搜索引擎用户所有信息需求的网络资源总量为S，则理想情况下，数据抓取子系统为满足用户需求需要的带宽B应该满足：
  
  事实上，由于我们无法预知哪些网络资源能够满足用户的信息需求，因此抓取到的网络资源中通常会包括相当多不被用户需要的部分，为了尽量满足用户需求，所需抓取的网络资源总量S‘一般要大于S。假设抓取到的网络资源中真正被用户所需要的部分所占的比例为R，则在不考虑带宽浪费的前提下系统需要的网络带宽B'为：
  
  此外，由于系统实现的原因，数据抓取子系统能够利用的带宽往往低于网络实际可以提供的带宽，假设这段时间T内，带宽的利用率平均为U，则数据抓取子系统实际所需的带宽B''应当满足:B'=B'' * U
  因此有
  
  通过上式我们可以看出，提升数据抓取子系统的效率（即减少系统为满足用户信息需求所需的带宽），在S与T相对固定的情况下，关键在于提升抓取到的万维网数据中有用数据的比例R以及网络带宽的利用率U。
  1.提升抓取到的万维网数据中有用数据的比例R。

识别各类抓取陷阱（黑洞，鲁棒性）。

2.提升网络带宽的利用率U。
改进算法、使用并行抓取策略、改善网络速度减少抓取等待时间、充分合理利用被抓取网站的服务器和带宽资源（礼貌性）。
实际应用中，由于搜索引擎很难很难获得完整的被抓取网站的相关服务信息，因此搜索引擎与网页内容提供者之间往往通过“robots.txt”的抓取协议来协商抓取策略。
对于绝大多数搜索引擎的数据抓取系统而言，robots.txt是它们访问某网站的时候要查看的第一个文件。robots.txt文件告诉抓取子系统在服务器上什么文件是可以被抓取的，应该用什么样的方式才算是“礼貌”地抓取。
当抓取子系统访问一个站点时，它会首先检查该站点根目录下是否存在robots.txt,如果存在，抓取子系统就会按照该文件中的内容来确定访问的范围和访问方式；如果该文件不存在，则抓取子系统将不受限制地访问网站上所有没有被口令保护的页面。
常用的一些robots.txt协议语句：

User-agent://以下规则对哪些搜索引擎适用，“*”表示所有搜索引擎
Disallow://不允许访问的目录名，通常为私密内容、程序脚本、样式表等内容
Sitemap://指定可用于搜索引擎访问的内容
Crawl-delay://抓取时间间隔限制，按秒计算
对于网站所有者而言，如果合理利用robots.txt文件，可以既保证自己的网页内容被搜索引擎收录，又不会造成服务器负担过重。

内容索引子系统的主要功能与性能需求

主要功能

• 内容检索子系统的主要功能，是将数据抓取子系统收集到的网络数据进行保存、整理，并以便捷高效的方式提供给内容检索子系统使用。它在整个搜索引擎系统的数据流中担负着承上启下的作用，它索引的数据由数据抓取子系统提供，而它所索引的数据则进一步供内容检索子系统进行结果筛选、排序使用。与大脑建立长期记忆的机制类似，搜索引擎内容索引子系统也是通过对网络数据进行重新组合整理的方式来实现后续的高效访问的。

倒排索引结构

词项：词项是逻辑学中的基本概念之一，指逻辑分析的基本单元，英文为Term。搜索引擎与信息检索研究中的词项是指具有一定概念的构成文档的基本单元。

• 倒排索引基本结构
  与倒排索引相对的索引形式是正排索引，倒排索引与正排索引的根本区别在于索引项的构成不同：倒排索引的索引项是词项，而正排索引的索引项是文档。倒排索引之所以被称为“倒排”，主要是说其与传统文献组织方式（如图书馆中的文献组织方式）中以文档为中心的“正排”的组织方式不同。
  词项（Term）是信息组织的核心，通过访问词项，我们可以获得该词项出现的各个文档（记录在Doc X中），以及这些文档中该词项出现的位置（记录在pos X中）。

  
  倒排索引结构
  正排索引结构
  

  由于倒排序索引是以词项为中心组织信息，因此内容检索子系统将数据抓取子系统收集来的网络内容加以索引，首先要完成的就是从文档到词项的转化过程，即将文档通过词项切分操作变成词项集合的过程。

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

对于搜索引擎而言，内容索引子系统的性能需求可以概括为：充分利用系统资源和高效完成索引服务。

• 在提高系统资源的利用率方面，在内容索引子系统设计中重点考虑如何在保存尽量多有用信息的基础上减少系统所需的磁盘存储资源。索引建立、更新过程中重点需要进行的是磁盘读写操作，而索引查询过程中重点需要进行的是磁盘读操作。索引建立、更新的时间效率只需要与数据抓取子系统的运行效率相适应即可，由于网络带宽低于硬盘访问速度，因此这方面的时间效率要求相对较低。由于用户查询是在线实时进行，而内容检索子系统的运算大都在内存中完成，因此索引查询的时间效率要求较高，而大规模磁盘读写也往往成为搜索引擎提供高校在线服务的主要瓶颈。同时，由于搜索引擎需要的存储系统规模异常庞大，涉及的存储介质同样种类繁杂、数量庞大，这些介质在面临大规模读写时难免会出现硬件问题。
  为了提高搜索引擎系统的运行效率，同时减少存储系统的硬件损耗和故障率，内容检索子系统需要在设计时尽量减少索引占用的磁盘空间，借以降低磁盘读写次数。
  1.首先，当前绝大部分搜索引擎（包括大部分文本信息检索系统）所采用的倒排索引结构都采用了一定程度的压缩算法以减少索引存储空间。由于网络资源数目繁多，为精确匹配用户查询，搜索引擎往往需要记录文档中各个词项出现的位置信息。记录位置信息需要耗费大量的存储空间，而在文档长度不长、词项与词项之间的相对位置偏移不大的情况下，存储空间的浪费也是十分惊人的。为此，搜索引擎通常采用行程编码或常用压缩工具包如gzip、bzip等对记录了位置信息的索引进行压缩，以有效利用存储空间。
  2.其次，搜索引擎系统在记录索引位置信息时一般都会设置记录长度的上限。网页文档长度差异巨大，如果索引结构需要能够保证记录所有文档的所有词项出现的精确位置，则索引结构需要预留与所有文档中最长的文档长度相一致的字节数用于记录位置信息，由于绝大多数文档的长度要远远短语这个最长长度，因此对于这绝大多数的网页而言，预留的信息其实并不必要。因此，搜索引擎在记录索引位置信息时往往只用N比特记录词项位置（N一般为10~16）,词项所处的位置大于2^{N的，一概记录为2}N。尽管这样会造成部分较长文档中位置信息的缺失，但是对于整个搜索系统的构成而言，是效率较高的选择。
• 在提高索引服务效率方面，内容索引子系统重点考虑如何从搜索用户的行为习惯出发，在保证服务质量的基础上提高服务效率。搜索引擎所收集的网络数据规模庞大，涵盖了人类历史上大部分的知识与信息财富，然而，考虑到用户的实际需求情况，这些网络数据中真正能够为绝大多数用户所利用的只是相当少一部分。
  这一现象是与用户查询需求的“二八定律”（查询量最大的一部分查询覆盖了用户查询需求的绝大多数）密切相关的，既然少数查询量最大的查询就能够代表大多数的用户需求，那绝大多数用户所利用的网络数据，也必然是与这少部分查询相关的资源。
  为了在保证最大范围用户群体查询需求可以得到满足的前提下，尽量把优先的资源集中到少数高质量网页索引上，以提高索引系统的整体服务效果，提出了基于层次结构的索引模块设计方案。
  第1级索引由网页中的权威站点首页组成，权威站点一般是指各种网页目录和目录是搜索引擎倾向于收录的站点，其在中文网页中的总体数量按照各网页目录站点估计，约由十几万到几十万个页面组成。第2级索引由网页中的高质量页面组成，由约几千万至几亿网页组成。第3级索引则是原有的网页索引，即包括所有网页内容的索引。
  三级索引之间具有近似的内容蕴含关系，即第2级索引基本包括第1级索引所收录的页面，而第3级索引完全包括了第1级和第2级索引收录的页面。从页面数量上来讲，第3级索引收录的网页远远大于前两级索引，因此其倒排索引条目的数目，以及每个索引条目所对应的的存储规模也要远远多于第1级和第2级索引。
  检索系统处理用户查询需求时，查询需求首先递交低级别索引，只有当低级索引没有对应的索引条目，或返回的索引条目规模不足（由经验值确定）时，系统方进行高级别索引的访问。由于大部分用户需求可以被第1级和第2级索引所满足，因此较少有机会访问第3级索引。由于访问索引时需要耗费大量的内存空间载入索引条目列表等内容，因此在绝大部分运行时间中，第3及索引可以不保存在内存空间中，这就大大减少了系统运行的空间代价，从而能够提升整体的索引性能。

内容检索子系统的主要功能与性能需求

主要功能

内容检索子系统的主要功能，是利用内容索引子系统提供的索引数据和链接结构分析子系统提供分析结果，按照用户的查询信息需求返回以相关度进行排序的结果列表，以便用户的进一步浏览和利用。

内容检索子系统与文本信息检索系统

搜索引擎与文本信息检索系统的重要差别：
1、搜索引擎对“相关性”的标准是与文本信息检索系统不同的，即两者的“标准答案”标注规则其实不同。
2、搜索引擎用户的信息需求往往是无法从查询关键词中直接推知的，而TREC评测标准中使用的查询关键词都带有详细的信息需求描述。
3、搜索引擎系统对内容检索系统的效率要求较高，文本信息检索系统采用的不少文本处理方法事实上无法满足实际服务的效率需求。

性能需求

1.相关性需求

搜索引擎结果的相关性：带有信息需求（Information Need,IN）的用户在使用搜索引擎时，某结果Ri的相关性是指该结果满足IN的程度。
内容检索子系统在相关性排序方面需要考虑的因素要远远多于传统的文本信息检索系统。为了能够使结果序列最大程度地满足用户的信息需求，内容检索子系统需要引入比传统文本信息检索系统多得多的排序因素。这些因素包括：结果页面本身的质量（结果页面来源网站的质量、是否高质量页面、是否垃圾页面）、结果页面的组织形式（用户是否能够很快地通过阅读页面内容获得必要的信息）、结果页面受欢迎的程度（有多少用户先前访问过该页面）、结果页面内容新颖的程度（页面更新周期，是否包含过期信息）等。

2.查询理解需求

内容检索子系统需要完成的另一项重要任务，是通过查询关键词理解查询背后的信息需求。
1、查询内容的歧义性问题
针对查询内容的歧义，面向结果页面集合的文本聚类技术经常被应用，以保证各类查询对应的歧义内容都能够在结果列表中出现。
2、查询对应的信息需求的歧义性
即使使用内容不包含歧义的关键词进行查询，搜索引擎用户的信息需求也可能是完全不同的。搜索引擎为确保各类信息需求都可以得到满足，必须分析用户的各种查询意图并尽量在结果中加以体现。
3、理解查询背后的信息需求的歧义
即使查询内容以及查询对应的信息需求类别都没有歧义，理解查询背后的信息需求也很困难。在“关键词查询+选择性浏览”的交互方式下，搜索引擎面对的查询是十分简单的字词组合。即使这些查询并不具有内容和信息需求层面的歧义，也会造成了不少查询信息需求表述不清的现象。

3.效率需求

• 海量规模的线上查询需求导致任何一个用于内容检索子系统算法的计算复杂度不能很高。在信息检索领域得到广泛应用的部分算法如查询扩展、相关反馈与伪相关反馈等，往往由于需要大量的在线运算量而被内容检索子系统舍弃。
• 在摒弃部分高运算复杂度算法的同时，内容检索子系统也往往使用适当的缓存算法提高系统运行效率。少数查询量最大的查询就能够代表绝大多数的用户需求。所以，只要把查询量较大的查询对应的结果加以缓存，则有限的系统运算资源就只需要集中对少数不包含在缓存中的查询进行处理即可，这样就大大提升了系统的运行效率，甚至可以将查询量最大的查询对应的检索结果页面作为静态页面加以保存，就可以更快地处理这些常见的用户查询。当然，缓存本身也需要经历更新的过程，以保证结果与互联网的数据更新保持同步。

链接结构分析子系统的主要功能与性能需求

与传统数据相比，互联网数据最大的特点就是其以超文本的形式进行组织，超文本除了包含用于规范文字显示格式的标签文字信息之外，更为重要的特性是其包含可以链接到其他字段或者文档的超文本链接，这使得超文本系统允许从当前阅读位置直接切换到超文本链接所指向的文字。这种链接蕴含的信息是传统数据中所不具有的，也是搜索引擎用以评价网络数据质量、扩展网络文档描述的重要依靠，这两方面的功能主要是由链接结构分析子系统完成。

基于链接结构分析评价数据质量

互联网时代，每个用户的注意力都是宝贵的资源，理想状态下，各个网页都希望能够链接到有高质量内容的其他网页，以便提升自身的链接质量，更好地为用户获取信息服务。这样，真正具有高质量内容的网页自然会得到越来越多其他网页的链接；而真正以更好地为用户服务为己任的网页也会越来越多地链接到其他高质量网页。良性循环下去，就形成了高质量网页在链接结构关系中的特殊地位，而链接结构分析算法，就是通过这种特殊的地位区分网络数据的质量。

PageRank算法

基于链接结构分析扩展文档描述

基于链接结构分析扩展文档描述的方法，事实上是将不同原网页作者对同一目标网页的描述文字加以整合，这样，对于目标页面描述的“一家之言”（目标网页作者的描述）就变成了“百家争鸣”（目标网页作者以及多个源网页作者的描述）。
基于网页链接文本（anchor text）提高检索系统性能的尝试被多方面的研究成果证明是十分有效的 ，该方法也因此被广泛应用于搜索引擎的技术实践中。

链接结构分析子系统的效率需求

搜索引擎链接结构分析子系统所实现的两大主要功能（数据质量评估和扩展文档描述）都无需在线完成，因此链接结构分析子系统的实时性和效率要求相对其他几个子系统要略低一些。与之相对应的，数据质量评估方面的几种常用算法（如PageRank、HITS、TrustRank等）都采用迭代计算的方式，计算复杂度较大；而扩展文档描述时也需要进行链接描述文字从源网页到目的网页的重整过程，同样需要耗费较高的运算资源。

搜索引擎体系结构设计理念

• 首先，是用户需求驱动的设计理念。我们需要根据用户需求确定网页抓取、更新的频率；需要根据用户需求确定网页层次索引结构的组成；需要根据用户需求确定结果的相关性；也需要根据用户需求设计链接结构分析算法，确定网页质量评估的方式。符合用户需求是搜索引擎体系结构设计首先需要遵循的原则，这是搜索引擎出现伊始就能吸引大量用户，至今也为海量规模用户所利用的核心原因。
• 其次，是有损优化的设计理念。搜索引擎是资源（存储资源、带宽资源、运算资源等）极端密集的网络产品，把有限的资源用在合理的方向，是节约成本赢取更大盈利的关键。数据抓取子系统中，有限的带宽只能优先供部分需要实时更新的网页进行抓取更新；内容索引子系统中，词项在网页内容中的位置记录会被设定上限，超出上限长度的网页位置信息记录的会不准确；层次索引结构中，高水平的硬件只应用在高质量网页对应的索引上。有损优化的设计理念尽管达不到所谓“全面最优”的检索效果，但却可以使检索性能在整体上最大化，更好地满足最大多数用户的最大多数查询需求。
• 最后，是重视效率的设计理念。面向大规模的数据和用户群体，搜索引擎必须时刻把效率需求摆在重要的位置。内容索引子系统设计中必须为节约存储结构中的每一个比特而努力；内容检索子系统必须舍弃复杂度过高的算法；链接结构分析子系统必须把运算强度降到可接受的最低水平；各个子系统都必须设置大量的缓存系统以充分利用“二八定律”提高系统效率。