浅谈搜索引擎基础（上）

这个系列的第六个主题，主要谈一些搜索引擎相关的常见技术。

1995年是搜索引擎商业公司发展的重要起点，《浅谈推荐系统基础》中也讲过，随着互联网上的Web站点数量越来越多，分类目录网站已经不能满足用户的需求，用户也无法依赖手工的方式来获得自己想要的信息，在这样的背景下，搜索引擎发展了起来。

有人将搜索引擎分为三个时代：

• 文本检索：采用经典的信息检索模型，如布尔模型、向量空间模型或概率模型来计算用户查询关键词和网页文本内容的相关程度。
• 链接分析：充分利用了网页之间的链接关系，认为网页链接代表了一种推荐关系，深入挖掘和利用了网页链接所代表的含义。
• 用户中心：以理解用户需求为核心，致力于解决如何能够理解用户发出的某个很短小的查询词背后所包含的真正需求。

搜索引擎的三个目标：

• 更全：索引网页更全
• 更快：查询速度更快
• 更准：搜索结果更准

让搜索结果更准的三个核心问题：

• 用户真正的需求是什么
• 哪些信息是和用户需求真正相关的
• 哪些信息是用户可以信赖的

搜索引擎整体架构

从架构层面，搜索引擎主要需要解决两方面的问题：一个是搜索引擎需要获取、存储并处理以百亿计的海量网页；另一个是快速响应用户的查询，并精确满足用户的需求。

搜索引擎通过爬虫将整个互联网的信息获取到本地，通过网页去重模块去除其中相当大比例的完全相同或近似重复的内容。

在此之后，搜索引擎对网页进行解析，抽取出网页主体内容，以及页面中包含的指向其他页面的链接。网页主体内容特别的通过倒排索引结构来保存，保存页面链接关系是为网页相关性\重要性排序做准备。

由于网页数量提多，搜索引擎不仅需要保存网页原始信息，还要存储一些中间的处理结果，使用单台或者少量的机器明显是不现实的，所以需要优秀的云存储与云计算平台，使用数以万计的PC搭建了海量信息的可靠存储与计算架构。

当搜索引擎接收到用户的查询词后，首先需要对查询词进行分析，希望能结合查询词和用户信息来正确推导用户的真正搜索意图。在此之后，优先在缓存中查找，搜索引擎的缓存系统存储了不同的查询意图对应的搜索结果。如果缓存信息无法满足用户需求，搜索引擎需要调用网页排序模块，根据用户的查询实时计算哪些网页是满足用户信息需求的，并排序输出作为搜索结果。

网页排序重要的两个参考因素分别是内容相似性和网页重要性，搜索引擎需要选择与用户查询密切相关的，质量较好或者相对重要的网页。

除了上述的子功能，搜索引擎的反作弊模块也是必不可少的，以避免网页通过各种手段将网页的搜索排名提高到与其网页质量不相称的位置。

网络爬虫

通用爬虫框架

爬虫首先从互联网页面中精心选择一部分网页，以这些网页的链接地址作为种子URL，将这些种子URL放入待抓取URL队列中，爬虫从待抓取URL队列依次读取，并将URL通过DNS解析，把链接地址转换为网站服务器对应的IP地址。然后将其和网页相对路径名称交给网页下载器，网页下载器负责页面内容的下载。

对于下载到的网页，首先将网页内容存储到页面库中，等待后续建立索引；之后将该网页的URL放入已抓取URL队列中以避免重复抓取；最后核对网页中所有包含的链接信息，与已抓取URL队列比较，如果链接还没有被抓取过，则将这个URL放入待抓取URL队列末尾。实际上也就是一种BFS广度优先搜索。

对于爬虫而言，互联网页面分为五个部分：已下载网页集合、已过期网页集合、待下载网页集合、可知网页集合和不可知网页集合。

已下载网页集合、已过期网页集合都好说，待下载网页集合指待抓取URL列表中的网页，而可知网页集合指那些通过待抓取网页的链接信息最终会被抓取到的网页。

爬虫也大致分为三种，批量型爬虫、增量型爬虫和垂直型爬虫。

批量型爬虫有比较明确的抓取范围和目标，达成目标即停止。增量型爬虫会保持持续不断的抓取，对于抓取到的网页，要定期更新。垂直型爬虫关注特定主题内容或属于特定行业的网页。

爬虫通常需要保护被抓取网站的部分私密性，并减少被抓取网站的网络负载。比如遵守网页禁抓标记，并考虑被抓取网站的负载。

爬虫质量的评价标准主要有三个：抓取网页覆盖率、抓取网页时新性及抓取网页重要性。尽可能抓取重要的页面，尽可能及时地更新其内容，在此基础上，尽可能扩大抓取范围。

抓取策略

比较有代表性的抓取策略有广度优先遍历策略、非完全PageRank策略、OPIC策略以及大站优先策略。

广度优先遍历策略

上面说的『将新下载网页包含的链接追加到待抓取URL队列末尾』就是广度优先遍历的思想。

非完全PageRank策略

PageRank是种著名的链接分析算法，用来衡量网页的重要性，我们希望利用PageRank的思想来对URL优先级进行排序，但是PageRank是个全局性算法，如果我们特别的只在已下载的网页和待下载网页形成的网页集合进行PageRank计算，这就是非完全的PageRank策略的思想，当计算完成后，将待下载，也即待抓取URL队列里的网页按照PageRank值由高到低排序。

有几点需要注意，一个是如果每次新抓取到一个网页，就将所有已经下载的网页重新计算非完全PageRank值，这样效率太低。折中的办法是，每当新下载的网页攒够K个，然后重新计算非完全PageRank值。第二个是，既然PageRank计算不是即时的，如果从新下载的网页中抽取的链接重要性非常高，我们通过汇总这个网页所有入链的PageRank值，给它一个临时PageRank值，如果这个值高于队列中网页的PageRank值，那么优先下载这个URL。

OPIC策略（Online Page Importance Computation）

我们可以将OPIC看做一种改进的PageRank算法，我们为每个页面都给予相同的权重，每当下载了某个页面P后，P将自己拥有的权重平均分给页面中所包含的链接页面。对于待抓取URL队列中的网页，则根据权重值排序，优先下载最高权重的网页。

OPIC的思路与PageRank基本一致，区别在于OPIC不需要迭代计算直到收敛，所以计算速度远远快于PageRank，适合实时计算使用。OPIC效果略优于广度优先遍历。

大站优先策略

以网站为单位来衡量网页重要性，对于待抓取URL队列中的网页，根据所属网站归类，如果哪个网站等待下载的页面最多，则优先下载这些链接，也即倾向于优先下载大型网站。

网页更新策略

爬虫需要保证本地下载的网页和原网页的一致性，网页更新策略的任务是要决定合适重新抓取之前已经下载过的网页，以尽可能使本地下载网页和互联网原始页面内容保持一致。

通常采用的方法有：历史参考策略、用户体验策略和聚类抽样策略。

历史参考策略

倾向于认为，过去频繁更新的网页将来也会频繁更新，通过参考其历史，利用泊松过程来对网页变化进行建模，根据每个网页过去的变动情况，预测将来核实内容会再次发生变化。

用户体验策略

一般来讲，对于搜索结果，用户往往只查看前三页，所以对于影响越厉害的网页，我们应该优先调度重新抓取。

聚类抽样策略

聚类抽样策略给出了在网页没有历史信息的情况下，网页更新的策略。聚类抽样策略认为，网页具有一些属性，根据这些属性可以预测其更新周期，具有相似性的网页，其更新周期也是类似的。

所以我们对网页进行聚类，以同一类别内采样网页的更新频率作为类别内所有其他网页的更新周期。

暗网抓取

所谓暗网，就是目前搜索引擎爬虫按照常规方式很难抓取到的互联网页面，即很难有显式的链接指向。比如数据库内的记录，往往是服务器提供查询页面，只有用户按照需求输入查询之后，才可能获得相关数据。

查询组合问题

比如垂直搜索网站往往会给用户提供多个查询输入框，用于输入各种属性来筛选结果。对于暗网爬虫，一个简单粗暴的方式就将所有可能的输入值排列组合。但是很多组合是无效的，也会对被访问网站造成巨大的流量压力。

Google提出了富含信息查询模板（Informative Query Templates）技术，其基本思路是，对于某个固定的查询模板来说，如果给模板内每个属性都赋值，形成不同的查询组合，观察返回结果，如果相互之间内容差异较大，则这个查询模板就是富含信息的查询模板。

这样做是为了防止多次查询的返回结果重复内容太多，导致效率低下。

Google的技术方案采用了ISIT算法，ISIT算法与《浅谈机器学习基础》中讲过的Apriori算法相似：首先从一维模板开始，对一维查询模板逐个考察，去掉不富含信息的查询模板，然后将剩下的一维模板扩展到二维，再依次考察对应的二维模板，如此类推。

这样就可以找到绝大多数富含信息的查询模板，同时也尽可能减少了提交的查询总数。

文本框填写问题

我们往往需要人工提供一些提示，爬虫根据初始种子词表，向垂直搜索引擎提交查询，并下载返回的结果页面，然后从返回结果页面里自动挖掘出相关的关键词，并形成一个新的查询列表，如此循环往复。

分布式爬虫

面对海量待抓取网页，只有采取分布式架构，才有可能在较短时间内完成一轮抓取工作。

大型分布式爬虫分为三个层级：分布式数据中心，分布式抓取服务器和分布式爬虫程序。整个爬虫系统由全球多个分布式数据中心共同构成，每个数据中心又由多台高速网络连接的抓取服务器构成，每台服务器又可以部署多个爬虫程序。

对于同一数据中心的多台抓取服务器，又主要存在两种不同架构，主从式分布爬虫和对等式分布爬虫。

主从式分布爬虫是有一台专门的服务器提供URL分发服务，其他机器则进行实际的网页下载。这种架构中，URL服务器容易成为整个系统的瓶颈。

而在对等式分布爬虫体系中，服务器之间不存在分工差异，每台服务器承担相同的功能。我们对网址的主域名进行哈希计算，之后按服务器个数取模，来给对应的服务器分配任务。但是这样如果部分服务器宕机，或是要添加新的服务器，致使服务器的个数发生了变化，这样就会导致几乎所有的任务都需要进行重新分配，导致资源极大的浪费。

为了解决这个问题，我们放弃哈希取模方式，转而采用一致性哈希方法来确定服务器的分工。

一致性哈希方法将网页的主域名进行哈希，映射为一个范围在0到2^23之间的某个数值，并认为0和最大值重合，将其看做有序的环状序列。每个服务器负责这个环状序列的一个片段，并且，如果某台服务器除了问题，那么本该由这台服务器负责的URL由顺时针的下一台服务器接管，并不会对其它服务器的任务造成影响。

搜索引擎索引

索引是搜素引擎最重要的核心技术之一，搜索引擎的索引其实就是实现单词-文档矩阵的具体数据结构表示，可以采用不同的方式来表示单词与文档之间的包含关系，比如倒排索引、签名文件、后缀树等方式，但倒排索引经实验证明是最佳的映射关系实现方式。

倒排列表

我们首先利用分词系统将文档自动切分成单词序列，这样每个文档就转换为由单词序列组成的数据流。然后我们为每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，如此处理结束后，我们可以得到最简单的倒排列表。

这只是最简单的倒排列表，只是记录了哪些文档包含了这个单词，除此之外，还可以记录单词在对应文档内的词频信息、出现位置和文档频率。词频就是TF-IDF中的TF，而文档频率就是TF-IDF中的DF，也即多少个文档包含某个单词。

在实际的搜索引擎系统中，也并不存储倒排索引项中的实际文档编号，而是代之以文档编号差值（D-Gap），文档编号差值是倒排表中相邻的两个倒排索引项文档编号的差值，一般这些编号差值都是大于0的整数。

单词词典

单词词典是倒排索引中非常重要的组成部分，它用来维护文档中出现过的所有单词的相关信息，并记载某个单词对应的倒排列表在倒排文件中的位置信息。

哈希加链表

哈希加链表词典结构

这种词典结构主要由哈希表和冲突链表组成，冲突链表的存在是因为单词的哈希值可能会有冲突。我们根据函数的哈希值找到单词在哈希表中的位置，表中会给出冲突表的指针，在冲突表中单词的对应位置可以读出其对应的倒排列表。

树形结构

B+树是另外一种高效查找结构，它需要词典项能够按照大小排序（数字或字符序）。B+树形成了层级查找结构，中间节点不保存内容，只用于指出一定顺序范围内的词典项目存储在哪个子树中，起到依据词典项比较大小进行导航的作用。最底层的叶子节点存储内容信息。

建立索引

两遍文档遍历法

这种方法完全在内存里完成索引的创建过程。

第一遍文档遍历的时候，并不立即开始建立索引，而是收集一些全局的统计信息。比如文档集合中包含的文档个数，文档集合所包含的不同单词个数，每个单词在多少个文档中出现过。将所有单词对应的文档频率（DF）值全部相加，就可以知道建立最终索引所需的内存大小是多少，于是在内存中分配足够大的空间用于存储倒排索引内容。第一遍文档遍历主要做些资源准备工作。

第二遍扫描的时候，开始真正建立每个单词的倒排表信息，第二遍扫描结束的时候，分配的内存空间正好被填充满。

两遍扫描完成后，即可将内存的倒排列表和词典信息写入磁盘。因为其需要两遍扫描，所以速度上不占优势，而且对内存占用过大，实际系统中这种方法并不常见。

排序法

排序法对两遍文档遍历法的内存占用做了优化，该方法始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果。当分配的空间被耗光的时候，把中间结果写入磁盘，清空内存里中间结果所占的空间，以便存储下一轮的中间结果。

所谓的中间结果在这里是（单词ID、文档ID、单词频率）的三元组，在清空写入磁盘之前，三元组需要依次按照单词ID、文档ID、单词频率进行排序，我们将排好序的三元组写入磁盘。

对于排序法而言，词典是一直存储在内存中的，耗光了分配的内存空间，也只是将中间结果写入磁盘。所以，越往后，可用来存储三元组的空间是越来越小了。

之所以要对中间结果进行排序，是为了方便最后的合并。合并完成后，就形成了最终的索引文件。

归并法

排序法中，词典信息一直在内存中进行维护，就会导致后期中间结果可用的内存越来越少。归并法对此做了修改，即每次包括词典在内的所有中间结果信息都被写入磁盘。

在最终合并的时候，排序法是对同一单词的三元组依次进行合并，而归并法的临时文件则是每个单词对应的部分倒排列表进行合并，形成这个单词的最终倒排表，归并法在合并的过程中形成最终的词典信息。

动态索引

真实环境中，在索引建立好之后，后续仍不断有新文档进入系统，同时原先的文档集合有些被删除或者修改。所以我们需要动态索引来将文档变化在非常短的时间内体现出来。

动态索引往往有三个关键的索引结构：倒排索引、临时索引和已删除文档列表。

当有新文档进入系统时，将其追加在临时索引结构中，当有文档被删除，则由已删除文档列表以ID的形式保存，文档的内容更改可被认为是先删除后添加。

如果用户输入查询请求，则搜索引擎同时从倒排索引和临时索引中读取用户查询单词的倒排列表，找到包含用户查询的文档集合，并对两个结果进行合并，之后利用已删除文档列表进行过滤。

索引更新策略

常用的索引更新策略有4种：完全重建策略、再合并策略、原地更新策略以及混合策略。

完全重建策略是当新增文档到达一定数目的时候，将新增文档和老文档进行合并，然后对所有文档重新建立索引。这是目前主流搜索引擎采用的方法。

再合并策略是达到一定条件后，将临时索引和老文档的倒排索引进行合并，以生成新的索引。

原地更新策略的基本出发点是为了改进再合并策略的缺点，即在索引更新过程中，如果老索引的倒排列表没有变化，那就可以不需要读取这些信息，只在其末尾进行追加。

但是这样会破坏了单词索引的连续性，因为不可能预留无限大的空间使其可以一直往后追加，所以就必须做数据迁移，这样导致了进行索引合并时不能顺序读取，反而降低了磁盘读取速度，而且还需要大量的内存来记录位置的对应关系。

混合策略是针对不同类别的单词，对其索引采取不同的索引更新策略。比如，倒排列表较长的单词用原地更新策略，短倒排列表单词则采取再合并策略。

查询处理

为搜索引擎建立索引，其目的是能更快速地提取与用户查询相关的文档信息。目前有两种常见的查询处理机制，一种被称作一次一文档方式，另外一种被称为一次一单词方式。

一次一文档

搜索引擎接收到用户的查询后，首先将两个单词的倒排列表从磁盘读入内存，以倒排表中包含的文档为单位，每次将其中某个文档与查询的最终相似性计算完毕，然后开始计算另外一个文档的最终得分，知道所有的文档都计算完毕为止。

在计算过程中始终保留得分最高的K个文档即可。

一次一单词

一次一单词方式首先将某个单词对应的倒排列表中的每个文档ID都计算一个部分相似性得分，待计算下个单词的倒排列表时，对于每个文档，在原先得分基础上进行累加。当所有单词都处理完毕后，每个文档的最终相似性得分计算结束，之后输出得分最高的K个文档作为搜索结果。

跳跃指针

如果用户输入的查询包含多个单词，那搜索引擎一般是采用与逻辑来判别文档是否满足要求，也即需要同时包含所有查询词。

对于这种应用场景，一次一文档的查询方式是更合适的，因为一次一单词的查询方式会浪费大量计算资源在根本不满足条件的文档上。

如果倒排列表直接存储包含查询词的文档的ID，那么计算交集是十分简单和直观的，但是前面也说过，我们的文档ID是以文档编号差值（D-Gap）形式存储的，另外这个差值我们还要进行压缩的。为了求交集，我们得先将若干个倒排表全部解压缩，然后再将其由D-Gap恢复为文档ID，再求交集。

跳跃指针的引入可加快列表求交集这一计算过程。

跳跃指针

跳跃指针的基本思想是将一个倒排列表数据化整为零，切分成若干个固定大小的数据块，对于每个数据块，增加元信息来记录关于这个块的一些信息，这样可以快速找到相应文档所在的数据块，也不再需要对整个倒排列表进行解压。根据元信息，可以确定数据块所对应的文档的范围，找到所需查询的文档所对应的数据块之后，也只需要对该数据块进行解压，解压出来的D-Gap值与元信息结合，就能恢复原本的文档ID。

多字段索引

在很多实际的搜索应用领域，搜索引擎要处理的文档是有一定结构的，即文档包含多种类型的字段，比如邮件的『发件人』、『收件人』、『标题』、『正文』等，我们希望能够按类型进行搜索。为了满足这样的需求，搜索引擎需要能够对多字段进行索引，常用的的方法有：多索引方式、倒排列表方式和扩展列表方式。

多索引方式也即分别建立多种类别的索引，但是如果用户没有指定特定字段，那就要综合所有字段的索引给出结果，所以效率会较低。

倒排列表方式是在每个文档索引项信息的末尾追加字段信息（比如标识位），以此来进行过滤。

扩展列表方式是实际中应用得比较多的支持多字段索引的方法。这个方法为每个字段建立一个列表，这个列表记载了每个文档这个字段对应的出现位置信息。

短语查询

有些短语，顺序颠倒就会产生完全不同的含义，前面讲的索引查询方法只能找到交集，并无法支持特定顺序。

位置信息索引

前面我们讲的倒排列表往往存储文档ID、单词频率和单词位置信息。依照单词位置信息就可以帮我们完成短语查询，比如发现根据单词位置信息发现两个单词是相邻并具有特定顺序关系。但是存储单词位置信息实际上会对单词倒排列表的长度产生影响，并且计算代价相当高。

双词索引

一般而言，二词短语在短语中所占比例最大，我们可以建立双词索引来满足二词短语的查询需求：

双词索引

首词词典指向下词词典的某个位置，下词词典存储了紧跟在首词后面的第二个词，下词的词典指针用来指向包含这个短语的倒排列表。比如用户输入『我的父亲』，先将其拆成两个短语『我的』和『的父亲』，分别查找词典信息，发现『我的』这个短语出现在文档5和文档7，而包含『的父亲』的文档中又包含文档5，看起对应的出现位置，可以发现其满足需求。

双词索引同样使得索引急剧增大，所以一般只用双词索引处理包含『我』、『的』等停用词的短语。

短语索引

我们也可以直接在索引中加入短语索引，这样的缺点在于并不可能实现将所有的短语都建好索引，通用的做法是挖掘出热门短语，为这些短语专门建立索引。

混合索引

混合索引

分布式索引

当搜索引擎需要处理的文档集合数量非常庞大时，单机往往难以承担维护整个索引的任务。所以需要分布式的解决方案。

有两种经典的划分方式，一种是按文档划分，也即将整个文档集合切割成若干子集合，每台机器负责对某个文档子集建立索引，并相应查询请求；另一种是按单词划分，每个索引服务器负责词典中部分单词的倒排索引列表的建立和维护。

按文档划分的方式在多种条件下基本都优于按单词划分的方式。举个例子，比如某台索引服务器宕机，如果采用按文档划分的方式，部分单词的搜索结果中会少掉一部分文档，这部分文档还不一定是排在前面的文档，影响不会很大。但是如果采用的是按单词划分的方式，那这些单词的搜索结果会完全丢失，用户无法使用这些关键词进行查询，对用户体验的影响要大的多。

索引压缩

词典压缩

词典信息

如果我们按照上图的方式存储倒词典，那存储单词的空间必然要按照最长单词的长度来分配，这样就会造成大量的空间浪费。

在词典压缩这种技术方案里，可以将单词连续存储在某个内存区域，原先存储单词内容的部分由指向这个存储区对应单词起始位置的指针代替，单词结尾可以用词典中下一个单词的指针所指向的位置来做判断。如此就可以将原先浪费的存储空间利用起来。

在上面的基础上，我们还可以继续做出改进，我们可以将连续词典进行分块，在实际开发时，动态调整分块大小，而且原先每个词典项需要保留一个指向连续词典区的指针，分块之后，同一块的词典项可以共享同一个指针，每节省一个指针，就节省了4字节长的空间，此外，因为同一块内有多个单词，所以我们需要标识出单词的长度以便于区分。

经过上述优化的词典比不做优化的词典占用内存数量减少了60%。

倒排列表压缩

倒排列表往往记载三类信息：文档编号、词频信息及单词位置序列信息，因为文档编号及单词位置序列都是依次递增的，所以通常的做法是存储其差值，而非原始数据。这样文档编号和单词位置信息往往会被转换成大量的小整数，使得数字分布严重不均衡。

评价索引压缩算法的指标通常由三个：压缩率、压缩速度和解压速度。其中解压速度在3个指标中是最重要的。

一元编码和二进制编码是所有倒排列表压缩算法的基本构成元素，一元编码是，使用x-1个二进制数字1和末尾一个数字0来表示这个整数。比如5编码为11110。

二进制编码方式就是利用二进制进行编码。

Elias Gamma 算法与 Elias Delta 算法

Elias Gamma采用的分解函数是：x=(2^e)+d

对因子e+1用一元编码来表示，对于因子d采用比特宽度为e的二进制编码来表示。比如9编码为1110:001

Elias Delta是在Elias Gamma基础上的改进，它对因子e+1利用Elias Gamma再次进行压缩。比如9编码110:00:001，从左到右，110是3，110:00是4（2^{2），110:00:000是8（2}3），110:00:001是9。

Golomb 算法与 Rice 算法

Golomb算法与Rice算法与上述两个算法相似，只是分解函数不同，就不详述了。

变长字节算法

实际上就是128进制：

变长字节压缩示例

SimpleX 系列算法

SimpleX系列算法最常见的是Simple9，Simple9是一种字对齐算法，字对齐也就是我们通常使用的表示数字的方式，比如128是一百二十八。Simple9最常用的是利用32个比特位，来作为压缩单位，给定固定大小的压缩单位后，每个压缩单位试图存储多个待压缩的数字：

前四位是指示位，用于表明B是多少，即数据存储区基本构成单元比特宽度是多少。如果数字均为0或1，那用B=1就可以存储，可以同时存储28位数字；如果B=2，可以存储14个范围在0至3的数字，以此类推。

这个算法可以同时压缩/解压多个数字。

PForDelta 算法

PForDelta 算法是目前解压速度最快的一种倒排文件压缩算法。

前面讲的SimpleX算法，实际上，一次压缩多个数值面临困难，因为连续的数值序列有大有小，如果每个数值按照序列中最大的数值来决定比特宽度，很明显对小数值来说会存在空间浪费的情形。

PForDelta希望能在压缩率和压缩解压速度方面找到一个平衡点，对于待编码的连续K个数值（一般K取128，即一次性压缩解压128个数值），先去除其中10%比例的大数，根据剩下90%的数值决定该采取的比特宽度，而10%的大数当做异常数据单独存储：

我们将大数放在异常数据存储区，但也要记载这些数在原始序列中的位置信息，这样解压的时候能够快速恢复原始数据。

文档编号重排序

我们前面提到了D-Gap，我们用D-Gap来存储文档ID，经过前面的PForDelta，我们也知道，数字越小越容易压缩，所以我们希望对文档编号重排序，使得同一个单词倒排列表中的文档编号都尽可能尽可能相近，所得到的D-Gap值也就小了。

为了达到这个目的，我们希望内容越相似的网页，在编排文档编号时，其文档编号越相邻。计算相似性的方法很多，比如TF-IDF。

静态索引裁剪

前面讲的压缩方法都是无损压缩，这个方法是有损压缩，通过主动抛弃一部分不重要的信息来达到更好的数据压缩效果。

因为对于用户查询来说，搜索系统往往只需要返回相关性最高的K个网页，不需要将相关网页都呈现给用户。所以可以将那些不重要的索引项聪哥倒排索引中清除掉，只保留重要的索引项。

大体有两种不同的思路，一种被称为以单词为中心的索引裁剪，一种被称为以文档为中心的索引裁剪。

以单词为中心的裁剪，其裁剪对象是单词对应倒排列表中的文档。设定一个阈值α，一个折扣因子，相似度低于阈值与折扣因子乘积的文档被剪除掉，当然要至少保留K个索引项。

以文档为中心的裁剪，是在建立索引之前，只建立重要单词-文档的倒排列表，可以说是一种建立索引之前的预处理措施。而以单词为中心的裁剪，是在建好的倒排索引基础上对索引项进行删除。

检索模型与搜索排序

搜索结果排序是搜索引擎最核心的构成部分。

搜索结果排序是说，搜索引擎判断哪些文档是和用户需求相关的，并按照相关程度排序输出，而检索模型就是用来计算内容相关度的理论基础及核心部件。

前面所描述的利用索引的查询方法讲述了如何利用索引找到包含查询词的文档，但并没有说如何计算文档与用户查询的相似度，毕竟包含查询词与相关性是两个独立的维度：

文档划分的4个象限

其实我们需要的是相关文档，与是否包含查询词并无必然联系，但是搜索引擎所能做到的只是从包含查询词的文档中找出相关文档，也即只能处理第一三象限的内容，而对于第二四象限，搜索引擎就无能为力了，需要推荐系统来解决这种用户无法精确描述自己需求的场景，在《浅谈推荐系统基础》中也提到了，比如LDA，就可以发现两篇完全没有重复词汇的文档的相似性。

这里我们只考虑通过检索模型来找到在包含查询词的文档之中，与用户需求相关的部分。

布尔模型

布尔模型是检索模型中最简单的一种，其数学基础是集合论。布尔模型一般使用逻辑表达式，即『与/或/非』这些逻辑连接词将用户的查询词串联。对于布尔模型来说，满足用户逻辑表达式的文档就算是相关的。

布尔模型输出的结果是二元的，要么相关要么不相关，至于文档在多大程度上和用户查询相关，能否按照相似度排序输出搜索结果，这些布尔模型都无能为力。

向量空间模型

向量空间模型是目前已经非常成熟和基础的检索模型，前面反复提到的余弦相似度、TF-IDF，都与向量空间模型有密切联系。

不严谨的讲，向量空间模型就是将文档看做t维特征组成的向量，每个维度的权重采用TF-IDF计算，然后通过余弦相似度计算不同文档（或与用户查询语句）所对应的特征向量之间的相似度。

在搜索引擎的场景里，向量空间模型这一检索模型利用用户查询语句与文档之间的相似度代替了查询语句与文档之间的相关度。

虽然前面已经多次提过余弦相似度和TF-IDF，这里还是简单说一下，余弦相似度公式是计算两个向量之间夹角余弦值的公式，通过余弦值可以得到两个向量之间的夹角，我们可以近似的认为，两篇文档特征向量之间的夹角越小，这两篇文档的相似性就越高。

TF-IDF分为两部分理解，首先是TF（Term Frequency，词频），也即认为一篇文档中常出现的词要比不常出现的词更能反映该文档的主题，然后是IDF（Inverse Document Frequency，逆文档频率），也即认为在所有文档中都出现的词倾向于不能反映一篇文档的主题。我们结合这两条思路计算每个特征维度的TF-IDF权重值，也即TF值*IDF值，也即在一篇文档中常出现（TF高），却几乎不出现在其他文档中的词（IDF高），最能反映这篇文档的主题。

概率检索模型

概率检索模型是目前效果最好的模型之一。BM25这一经典概率模型计算公式已经在商业搜索引擎的网页排序中广泛使用。

概率检索模型的思想是：给定一个用户查询，如果搜索引擎能够在搜索结果排序时按照文档和用户查询的相关性由高到低排序，那么这个搜索系统的准确度是最高的。

从表述来看，概率检索模型直接对用户查询与文档的相关性进行建模，而前面的向量空间模型以用户查询与文档的相似性代替了相关性。

也即我们需要估算给定一个文档，与用户查询相关的概率P(R|D)，和不相关的概率P(NR|D)。

这是不是和区分垃圾邮件有点像，区分垃圾邮件用的什么？朴素贝叶斯算法，在《浅谈机器学习基础》中有对朴素贝叶斯算法的详细讲解。

这里的二元独立模型（BIM）与朴素贝叶斯算法基本相同，BIM的二元假设就是词集模型，以0/1表示单词出现与否。BIM的词汇独立性假设就是朴素贝叶斯假设，或者说是《浅谈自然语言处理基础》中讲过的一元文法模型。

在朴素贝叶斯算法中，根据贝叶斯决策理论，只要计算出P(R|D)和P(NR|D)，判断其大小关系即可，但是在BIM中，因为我们还需要对相关性大小进行归类，所以我们还要计算出P(R|D)/P(NR|D)。

经过化简取对数等操作后，我们得到如下公式：

其代表的含义是：对于同时出现在用户查询Q和文档D中的单词，累加每个单词的相关性估值，其和就是文档D和查询的相关性估值。（这里插一句，朴素贝叶斯那里不是连乘吗，为什么这里是加？因为P(R|D)/P(NR|D)在化简的时候取了对数）

还有一点，朴素贝叶斯算法是监督学习算法，通过带标签的训练语料得到先验概率的估计值，但是这里我们没有带标签的训练语料怎么办？我们只能把所有文档都看做是不相似文档，这样我们辛辛苦苦计算出来的P(R|D)/P(NR|D)就等价于所有单词的IDF之和了。

各种实验表明，BIM计算的相关性实际效果并不好，但这个模型是非常成功的概率模型方法BM25的基础。

BIM采用词集模型，只考虑是否在文档中出现，而没有考虑单词的权值。BM25模型在BIM模型的基础上，考虑了单词在查询中的权值以及单词在文档中的权值，拟合出综合上述考虑因素的公式，并引入一些经验参数。BM25模型是目前最成功的内容排序模型：

BM25计算公式

BM25模型计算公式其实融合了4个考虑因素：IDF因子、文档长度因子、文档词频和查询词频，并利用3个自由调节因子（k1、k2和b）对各种因子的权值进行调整组合。

对于二元独立模型，我们假设相关文档个数R和包含查询词的相关文档个数r设定为0，这样第一个计算因子就化成类似IDF的形式。

N代表文档总数，n代表出现对应单词的文档个数，f指文档中出现对应单词的词频，qf是查询语句中对应单词的词频，dl是文档长度。

BM25F模型是BM25的改进算法，它提出了域的概念，它将一篇文档划分为若干域，对于不同的域，在计算中给予不同的权值。

语言模型方法

假如利用朴素贝叶斯算法对相关/不相关文档进行分类，那是要分别计算文档由相关文档集生成的概率P(R|D)和由不相关文档集生成的概率P(NR|D)，然后比较其大小。

BIM是因为没有相关/不相关的标签，所以将所有训练文档都认为是不相关文档，对于一个测试文档计算P(R|D)/P(NR|D)。

语言模型方法和上述两种看起来很相似，但实际上思路不同，语言模型方法尝试去计算查询语句由测试文档生成的概率，概率越大则认为相关性越高。所采用的，就是朴素贝叶斯中计算测试文档由相关/不相关训练文档集生成的概率。（就是假如朴素贝叶斯算法判别时不用贝叶斯决策理论，就只按照测试文档由相关训练文档集生成的概率作为相似度的标准，那么把这种思路的朴素贝叶斯算法中的测试文档换成查询语句，相关训练文档集换成测试文档，那就得到了语言模型方法）

既然是语言模型方法，自然要考虑到是以一元、二元还是多元的文法模型为基础来计算生成概率。除此之外，还必然要考虑到数据平滑问题，这在《浅谈自然语言处理基础》中详细讲过，比如Good-Turing估计法、Katz、Kneser-Ney。

机器学习排序

机器学习排序方法我们简单介绍一下，过程主要分为四步：人工标注训练数据、文档特征抽取、学习分类函数、采用模型进行分类。

通过人工标注大量训练数据显然不现实，不过我们可以利用用户的点击数据。

机器学习排序方法最大的好处在于，前面的普通检索模型方法主要考虑了词频、逆文档频率和文档长度这几个因子来拟合排序公式，因为考虑的因素不多，所以人工拟合的方式可行，但是随着搜索引擎的发展，对于某个网页进行排序所考虑的因素越来越多，比如网页的PageRank值、查询和文档匹配的单词个数、网页URL链接地址长度都会对网页排名产生影响，那使用人工拟合的方法就很难行得通了。

先简述一下机器学习排序的思路，我们先将一篇篇文档转换成特征向量，比较常用的特征包括：

• 查询词在文档中的词频信息
• 查询词的IDF信息
• 文档长度
• 网页的入链数量
• 网页的出链数量
• 网页的PageRank值
• 查询词的Proximity值，即在文档中多大的窗口内可以出现所有的查询词

有了文档的特征向量之后，接下来的处理方式可以分为三种思路：单文档方法、文档对方法和文档列表方法。

单文档方法

单文档方法就是最先想到的机器学习方法，我们有了文档的特征向量，我们也有了文档的标注结果：相关/不相关。那我们就可以训练出一个模型出来判断文档的相关性，比如用SVM或者LR都可以。如果可以给出得分，那么得分大于某个阈值为相关，小于则为不相关。LR给出得分很简单，SVM其实也应该可以根据函数距离的大小来给出相应的可信度得分。

文档对方法

文档对方法的核心思想是，给定一个查询和文档对<Doc1,Doc2>，我们需要判断这种顺序关系是否合理，也即Doc1排在Doc2前面合不合理。

文档列表方法

单文档方法将训练集里每一个文档当做一个训练实例，文档对方法将同一个查询的搜索结果里任意两个文档作为一个训练实例，而文档列表方法是将每一个查询结果对应的所有搜索结果列表整体作为一个训练实例。

文档列表方法的目的是尽量使得机器学习模型对搜索结果的打分顺序和人工打分顺序尽可能相同，也即模型预测的搜索结果的排列顺序与人工标注的排列顺序尽可能相同。

结果表明，基于文档列表方法的机器学习排序效果要好于前述两种方法。

检索质量评价标准

准确率和召回率，这两个就不说了，除此之外还有P@10和MAP。

P@10就是看前10个文档当中，有多少个文档是相关文档，有多少个相关文档，P@10就是十分之几。

MAP指标稍微复杂一点，MAP是衡量多个查询的平均检索质量的，而AP是衡量单个查询的检索质量的。假设用户搜索结果中有3个文档是相关的，它们应该排在第1、2、3位，那(Σ(理论位置/实际位置))/相关文档个数，就是这次查询的AP值。

对多次查询的AP值取平均，就得到了MAP值。