1.搜索系统的框架
1.1基本框架
搜索系统通常由信息收集、信息存储、信息扩展及搜索计算4部分组成。搜索系统的具体结构上图所示。
（1）信息收集
该部分包括但不限于爬虫和线下导入。对于网络爬虫部分，该组件的主要功能是收集全网实时/延时数据（这取决于搜索引擎的应用场景），并对收集的数据进行简单处理，如去重、停用敏感信息、过滤垃圾信息以及生成信息存储部分可以接收的数据，以便存储。线下导入的信息有时是作为爬虫信息的补充，如作为对缺乏规范描述的定义、定理等进行补充的备检信息；有时是作为推理或关系信息的主要依据，如作为对网络爬虫收集的信息进行关系处理的依据。
（2）信息存储
该部分包括但不限于文件信息保存及索引保存等。信息存储的主要功能是提供高效的、泛化的、文档间可联动的搜索内容。所以在文件信息保存上，有时会因为场景的原因，将所有文件内容放置在内存中，所以会建立庞大的倒排索引和并发集群以提高搜索的响应效率。对于推理性搜索，为了提高搜索的响应效率，存储组件需要对应用于推理的节点（关键词、字段或者短语描述等）进行特殊处理。
（3）信息扩展
除响应效率外，为了提高搜索的准确性，有时我们需要对搜索系统召回的内容进行相应扩展。扩展的目的是尽量避免无结果的搜索。在信息扩展部分，我们可以在爬虫程序中定义文档间关系，甚至定义推理逻辑实现，在信息存储部分可以屏蔽停用词、定义同义词，并在建立索引的时候就支持泛化能力。
（4）搜索计算
为了理解搜索输入（通常称为Query）和召回排序，我们需要对Query进行生成和解析并提供召回的评分策略，以便对结果进行排序。
生成Query：搜索系统的输入通常是人类自然语言的输入，其表达形式包括但不限于关键词、短语、句子、文章段落，甚至图片等。所以，在生成Query时，通常会加入意图理解模块，以尽可能理解用户当前检索内容的真实意图。同时，受制于人类语言表达的缺陷，在自然语境下所表述的内容被计算机理解时可能会产生歧义，这也是意图理解模块试图解决的问题。通过意图理解模块，我们通常会得到当前搜索内容的主题或者检索要素。对于检索要素，可能需要进行拓展，这部分拓展主要依赖当前用户的行为和近期全网热度等。最后将整理的全部检索要素生成计算组件可理解的Query并输入计算模块。
解析Query：计算模块将搜索信息从信息存储组件中按照既定的评分标准排序召回。首先，搜索系统需要将Query导入信息延展组件进行拓展。信息拓展的主要目的是加大召回的覆盖率和提高召回的准确度。这里常用的手段与NLP技术相关，除了可以对最基本的同义词、近义词进行打分，还可以对所有相关检索要素的重要程度进行打分，比如检索要素是Java工程师，显然Java的重要程度远远大于工程师，此时就需要对这两个不同的检索要素赋予不同的权重。
信息存储组件负责实时或延时地将搜集到的数据存储起来。对于数据的时效性，我们需要考虑搜索系统的性能及应用场景，而最终选择采取哪种方式进行数据存储，则是由读者实际工作决定。在存储信息时，为了保证信息的高效存储，通用的存储方式有内存存储与索引存储，具体的构建方式会在相关章节详细介绍。在接收到Query之后，信息存储组件会将结果返回到信息延展组件。返回的信息包括但不限于：单个召回结果中检索要素命中的位置信息、单个召回结果中检索要素命中的频次信息、整体召回结果的统计与分布等。这里之所以需要返回大量的信息，是因为我们在考虑搜索系统整体准确度的时候，还需要对结果进行排序。而排序阶段的特征数据或者评分数据主要由信息存储组件提供。所以，有时候信息存储组件返回的数据量可能过大。在结构上，一些搜索系统倾向于将部分信息延展组件与信息存储组件甚至计算组件整合到一起，从而在返回结果的同时结束部分计算结果的统计。部分情况下，信息存储组件也会将部分结果返回至信息延展组件，主要是考虑到更为精确、细粒度的搜索结果可能导致召回不足。这就需要在信息延展组件中，对可能发生的召回不足的情况制定补救措施，重复进行搜索、收集搜索结果的流程，直至召回满足或无法召回为止。最后将搜索结果返回至计算组件，进行最终的排序并将结果展示给用户。
1.2搜索引擎的工作方式
搜索引擎分为4部分，搜索器、索引器、检索器及用户接口，如下图所示。
搜索器。搜索器的功能是日夜不停地在互联网中漫游，搜集信息。它要尽可能多、尽可能快地搜集各种类型的新信息，还要定期更新已经搜集的旧信息，以免出现死链。搜索器有两种搜集信息的策略：第一种策略是从一个起始URL集合开始，顺着这些URL中的超链接（Hyperlink），以宽度优先、深度优先或启发式循环地在互联网中搜集信息。它会沿着任何一个网页中的URL集合“爬”到其他网页，重复这个过程，并把搜集到的所有网页存储起来。第二种策略是按照域名、IP地址划分Web空间，每个搜索器负责一个子空间的穷尽搜索。
索引器。索引器的功能是理解搜索器所搜索的信息，通过分析索引程序对收集的网页进行分析，提取相关网页信息（包括网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其他网页的链接关系等），根据相关度算法进行大量复杂计算，得到每一个页面的页面内容及超链接中每一个关键词与页面内容的相关度（或重要性），然后用这些相关信息建立网页索引数据库。
- 检索器。检索器的功能是根据用户查询在索引库中快速检出文档，对文档内容与查询的相关度进行评估，并对将要输出的结果进行排序，实现某种用户相关性反馈机制。检索主要过程如下：检索器对用户接口提出的查询要求进行递归分析，在用户接口中一般采用基本语法来设置检索条件。
- 用户接口。用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。其主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用了人机交互的理论和方法，以充分适应人类的思维习惯。用户输入接口可以分为简单接口和复杂接口两种。
2.数据收集及预处理
2.1爬虫
网络爬虫是搜索系统中很关键也很基础的组件，负责数据收集。通用的爬虫框架如下图所示。其工作原理是首先从互联网网页中选出一部分质量较高的网页的链接作为种子URL，把这些种子URL放到待抓取URL队列中，由爬虫从待抓取URL队列中依次读取，并通过DNS解析URL，把链接地址转化为网站服务器对应的IP地址。然后将IP地址和网页相对路径名称交给网页下载器，由网页下载器把网页内容下载到本地。这样做一方面可以将页面内容存储到网页库中，等待索引建立等后续处理；另一方面将下载页面的URL放到已经抓取的URL队列中，对已经爬取的页面进行记录，可以防止重复爬取。对于刚下载的网页，抽取其中的URL链接，并检查已抓取的URL队列，将没有抓取过的URL放入待抓取URL队列中，不断循环上述步骤直至待抓取的URL队列为空，即爬虫系统完成一轮完整的爬取流程。
该框架适用于绝大多数的爬虫系统，但不能代表全部。根据应用场景的不同，网络爬虫大概分为以下4种：1）通用型网络爬虫，负责爬取全网的资源，一般适用于大型搜索引擎；2）批量型网络爬虫，按照预先设置好的抓取目标和范围爬取资源，当爬虫完成目标后，就停止爬取；3）增量型网络爬虫，针对互联网中有变化的网页，比如新增、修改或者删除的网页，及时响应更新到本地网页库中；4）垂直型网络爬虫，关注特定主题或者特定行业的网页，难点是如何识别网页内容是否为特定主题或行业。
优秀的爬虫应该具备的特性主要有3点。1）高性能。此处的性能主要是指网页的下载速度，常用的评估爬虫性能的方式是以爬虫每秒能够下载的网页数量为指标，单位时间内下载的网页数量越多，爬虫的性能越高。2）健壮性。爬虫在遇到突发情况时，要能够做出正确的处理。当服务器宕机时，健壮的爬虫应该能够在服务器重启后，恢复之前抓取的内容和数据结构。3）友好性。友好性主要包括两个方面：一方面是保护网站私密性；另一方面是减少被抓取网站的网络负载。对于部分网站所有者不想被爬取的网页，网站所有者需要设置协议告诉爬虫哪些内容不能够抓取。常用的方法有：设置爬虫禁抓协议和网页禁抓标记。爬虫禁抓协议是指由网站所有者生成一个文件robot.txt，将其放在网站服务器根目录下，这个文件指明了哪些目录下的文件不允许抓取。友好的爬虫在抓取该网站的内容之前，应该先读取robot.txt文件并遵守协议。如果是某个网站不想被抓取，可以使用网页禁抓标记，即在网页的HTML代码里加入meta name=“robots”标记，其中content字段指出允许或者不允许爬虫做哪些行为，主要分为两种情形：一种是告诉爬虫不要索引该网页内容，以noindex标记；另一种是告诉爬虫不要抓取网页包含的链接，以nofollow标记。
评估爬虫的质量标准一般有三个：抓取网页的覆盖率、抓取网页的时效性和抓取网页的重要性。1）覆盖率，是指抓取网页的数量占互联网内网页总数量的比例，比例越高，覆盖率越高。2）时效性，是指爬虫对修改、删除的网页的反应速度，尤其是针对已经过期的网页，及时更新网页库。3）重要性直接影响搜索的准确率。
上图中待抓取的URL序列在爬虫系统中是关键部分。那么，URL序列顺序是如何确定的呢？将新下载页面中包含的链接直接追加到队列末尾，即宽度优先遍历策略，这是一种常见方式，但并不是唯一方式，还有非完全Pagerank策略以及大站优先策略。1）宽度优先遍历策略虽然没有明显地考虑网页重要性，但实验表明该方法效果很好，对很多链入的网页较为友好，并且链入的网页质量也较高。2）非完全Pagerank策略。Pagerank是一种著名的链接分析方法，最早应用于网页重要度排序，因此可以利用其对URL进行排序。由于其是一个全局算法，而爬虫下载的网页只是部分，所以由其计算的得分不一定可靠，但我们仍然可以借鉴它的思想：将已经下载的网页和待抓取的URL集中起来形成网页集合，在该集合内计算Pagerank，计算完成后，按照结果对待抓取的URL排序，然后依次抓取。3）大站优先策略。以网站为单位衡量网页的重要性，我们认为大站往往是知名企业，其网站质量一般比较高，所以一般优先搜索大站。
上文讲了如何对待抓取的URL排序，我们还需要考虑如何对已抓取的内容快速更新。常见的策略有：历史参考策略、用户体验策略和聚类抽样策略。1）历史参考策略。假设过去更新频繁的网页以后更新也会频繁，所以可以通过其历史更新情况，预估网页何时更新。2）用户体验策略。由于用户一般只对排名靠前的网页感兴趣，所以即使网页过期，如果不影响用户体验，那么晚些更新也是可以的。所以，判断一个网页什么时候更新，取决于网页的内容变化给排序结果带来的影响。3）聚类抽样策略。前两种策略都比较依赖网页历史信息，但在现实中，保存历史信息会增加搜索引擎负担，同时首次抓取的网页并不存在历史信息，因此以上两种方法都有缺陷。聚类抽样策略认为：网页具有一些属性，如网页内容、链接深度以及Pagerank值等，根据这些属性可以预测更新周期，而且，具有相似属性的网页也具有相似的更新周期，因此可以根据这些属性进行网页归类。同一类别的网页具有相同的更新频率。
2.2数据清洗
爬虫在下载了网页之后，需要对这些数据进行清洗，其中最关键的部分就是对网页的去重处理（据统计，完全相同的页面大约占全部页面的20%）。处理相似网页的好处：1）可以节省存储空间，留出充足的空间存储有效网页；2）通过对以往数据的分析可以预先发现重复网页，在之后的网页收集中避开这些网页，提高网页收集效率；3）如果用户点击了死链接，可以将用户引导到一个内容相同的页面，进而有效提高用户体验。
在实际工作中，网页相似检验一般是在爬虫阶段完成的，具体流程如下图所示。
通用的网页去重流程如下图所示。对于给定的文档，首先通过一定的特征抽取方法，从文档中抽取一系列表示文档主旨的特征集合，之后通过算法直接查找相似文档。对于搜索引擎中数以万计的文档，算法的执行速度是需要重点关注的，因此很多高效的算法会在特征集合的基础上，对信息进一步压缩，如采用信息指纹相关算法将特征集合压缩成新的数据集合。（新的数据集合包含的元素数量远小于特征集合的数量，但同时也造成了信息丢失，所以需要衡量压缩率和准确度之间的平衡。）把文档压缩成信息指纹后，就可以进行相似度计算了。
经实验证明，SimHash算法是应用最广泛且表现最好的去重算法之一，是一种局部敏感哈希框架的实现特例。该算法流行的原因是：两个文档越相似，其对应的两个哈希值也就越接近，且哈希值的计算明显比文本计算快很多，同时也节省空间。
SimHash算法步骤如下。
- 对需要判断的文本分词形成该文本的特征单词，然后生成去掉噪声词的单词序列，并为每个词加上权重。
- 通过哈希函数将每个特征单词映射成固定长度的二进制表示。
- 利用权重改写特征的二进制向量，将权重融入向量中，形成一个实数向量。假设某个特征单词的权重是5，对二进制向量进行改写：若比特位数值是1，则改写成5；若是0，则改写成–5。改写完的特征累加后获得一个表示文档整体的实数向量。
- 再次将实数向量转换成二进制向量，规则如下：如果对应位置的数值大于0，设成1；如果小于等于0，则设置成0。
得到两个文档的二进制数值后，利用海明距离来计算文档的相似度。
具体例子可以看下图。
2.3存储空间及分布设计
搜索系统中最重要的数据结构是索引结构，索引结构越合理意味着查询越快捷。设想如果我们直接对一篇篇文本进行扫描，费时费力。如果我们建一个前向索引，依然是依次扫描每一个文档，对于多次出现的字符串不一一扫描，对于同一文档内的字符串查找采用二分查找的方式，这样可加快匹配速度，但这远远不够，还需要一个倒排索引的数据结构，让查询面向词和文档集，使搜索任务更快捷和简单。对于单个查询词，搜索就是字典查找的过程，不需要扫描所有文档。倒排索引的过程如下图所示。
这里说明一下排序过程。排序就是扫描每篇文档产生的文档号、单词号、出现位置这个三元组。按照单词号重新排序，单词号相同则按照文档号排序，单词号和文档号都相同则按照出现位置排序。
Trie树，又称单词查找树或键树，是一种树形结构，也是哈希树的变种形式。其典型应用是统计和排序大量的字符串，但不限于字符串。Trie树的核心思想是用空间换时间，利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的。其包含三个特性：1）根节点不包含字符，除根节点以外，每一个节点都只包含一个字符；2）从根节点到某一个节点，路径上经过的字符连接起来为该节点对应的字符串；3）每个节点的所有子节点包含的字符都不相同。字符串and，as，bee，bus，cn，com构建的Trie树如下图所示。
在上图所示的Trie树中，root表示根节点，不代表任何字符，从第二层开始，白色表示分支节点，灰色表示叶子节点。从根节点到叶子节点，把路径上经过的字符连接起来，会构成一个词。而叶子节点内的数字代表该词在字典中所处的链路（字典中有多少个词就有多少条链路），具有共同前缀的链路称为串。树中的词只可共用前缀，不能共用词的其他部分。树中的任何一个完整词，一定是从根节点开始到叶子节点结束。所以，检索是从根节点开始到叶子节点结束，这种检索方式由于公共前缀的词都在同一个串中，能够大幅度缩小查询词汇的范围，同时从一个字符到下一个字符比对，不需要遍历该节点下所有子节点。因此，Trie树的时间复杂度仅和检索词的长度m有关：O(m)。综上可知，Trie树主要利用词的公共前缀缩小查词范围，通过状态间的映射关系避免所有字符的遍历，从而达到高效检索的目的。这种优势同样是需要付出代价的：1）由于结构需要记录更多的信息，因此Trie树的实现稍显复杂；2）Trie树词典不仅需要记录词，还需要记录字符之间、词之间的相关信息，因此在构建字典时必须对每个词和字逐一进行处理，而这无疑会减慢词典的构建速度；3）公共前缀虽然可以减少一定的存储空间，但Trie树相比普通字典还需表达词、字之间的各种关系，实现更加复杂，因此实际空间消耗相对更大。