搜索引擎简介

信息检索

我们要聊搜索引擎，那必然离不开信息检索（information retrieval）。首先我们对何为信息检索需要有一个明确的定义：通过在一个大的数据集合中找到满足信息需求（information needs）的非结构化自然形式（通常指文本语料库）的材料（一般指代文章）(Manning, 2008)。

在检索信息时，有两个指标是在讨论搜索性能时无可避免。一个是召回率（recall），另一个是准确率（percision）。有趣的是，这两个指标就像一对孪生兄弟，总是此长彼消，此消彼长，因此，如何做好其中的制衡是各个搜索算法面临的问题。本文作为搜索引擎技术的启蒙文章，主要针对文章结构与存储，操作符与查找算法这两个维度讲解一下搜索引擎的基本工作流程。

文章结构

首先我们来谈一谈搜索引擎都是如何理解它的那些文档的。在聊这个话题之前，我们要先明确一个定义，搜索引擎分为两种，网页级搜索引擎和公司级搜索引擎。无论是那种搜索引擎，它们第一件需要解决的问题就是理解语料库，之后要做的就是存储语料库。那么如何理解呢？现在让我们来看一下基本的文档的脉络机构（图2.1）。

图2.1

很多时候人们一般认为文档就可以看作一个独立的词袋。但其实不然，每个文档其实是由不同的组成部分构成的。比如一般网页的构建逻辑基本会是XML形式构成的，在大类上我们把它们分成三层，第一层是metadata，里面一般会有url，关键字，作者，日期等等，第二层是body，里面一般包含的就是像标题，主体内容这些信息。第三层是外部信息，主要有一些外部链接与内部链接跳转。分区可以帮助我们对各个区块的信息量进行一个区分，原因在于每个区块的信息熵是不一样的。简而言之，包含的信息量不一样，比如文章标题含有关键词的信息量就相对而言要大于段落中包含这个关键词所有的信息量。

与此同时，在我们得物平台，主要有两个搜索主要发力点，商品和社区，那也可以进行这样的分层，虽然具体的信息分层方式有所变化，但是具体的设计逻辑依然不变。根据香农定理里面的信息论，这些文档它们提供的信息价值是不同的，信息熵也是不同的，如果把他们混为一谈的话，我们搜索的准确度必然会有一定程度的降低。比如标题和主体，以AJ1为例。而如果将他们进行分层，那在后期我们进行算法干预的时候就可以人为的对其中的内容的权重进行调整，从而提高我们所召回内容与query符合度的准确率，更好的满足用户的搜索期望。

倒排索引

讲完了文档的结构，我们就要讨论下如何对这些文档结构用数据结构进行存储。相信大家都知道，我们在搜索引擎存储信息一般采用倒排索引，而倒排索引主要分为两种索引结构。

第一种办法我们针对的是平铺的页面布局，也就是我前面所提到的将所有页面的各个区块独立对待的方法，说白了萝卜是萝卜，坑就是坑，各个信息块之间各自独立，没有交互，而第二种结构我们采用的是垂直结构，也就是说，我们令页面中的各个布局存在层级关系。我拿主体部分举个例子，主体部分-> 区块->段落-> 句子。

首先我们来讲下第一种归并倒排索引，我们看下构建模式（图3.1），我们在推荐和博文这两个field里面都有一个词典，那我们在这儿要做的就是把各自的词典和它所对应的field合并起来。在这里我们需要注意的是，一个term将会有多个倒排索引，比如说bush这个词，在推荐这儿我们为它构建了一个倒排，在博文这儿我们也为它构建了一个倒排。在这种情况下，我们不会把不同field的信息杂糅在一起。很多次和bush一样都具有歧义性，通过建立各自独立的倒排索引，可以有效的保证信息的独立性。

图3.1

有的时候我们搜索信息时，并不需要搜索到全部的信息，可能我们只想要搜索到特定位置的特定信息。如果我们想要搜索句子里面的癌症（图3.2），在归并结构下，我们的搜索进程就会变得很是复杂，我们要先从文章再到章节再到句子，很显然，如果采用这样的结构，我们的搜索速度很受到一定的影响。

图3.2

因此，我们需要的采用一种比较精巧的独立倒排索引结构，这种结构一般面向的是那种相对比较复杂的文章结构。我们接下来看一下这个树形结构（图3.3），在这种结构下，我们会记录下文档各个词所在的位置以及它们的上下级父子关系。如果我们要搜索位于位置6和位置27的信息，我们就会先溯源到搜索脉络中所处的位置，之后用一种相对快速的方式快速检索到信息（log级别的速度）。如果要搜在章节位置的信息，那么它就会丢弃loc为6的信息，因为loc为6的信息在树结构中属于作者这个区块。这样的方式可以大大提升我们的搜索效率，而我们需要付出的只是唯不足道的一些内存而已，在这个云存储的时代，这样的操作非常具有性价比。

图3.3

除此之外，我们也可以用完全倒排的方法来构建倒排索引-即独立倒排形式。我们可以把field的边界阈值存放在倒排索引里面，另外构建一个term的倒排索引，通过把这两个进行归并，即可构建独立倒排（图3.4）。比如说在这儿我们假设这是一个句子的倒排索引，开始和起始为止标注在那儿了，extentFreq表示这是第几个field。当我们确立好loc的具体值时，我们只需要到旁边的[begin,end]判断是否在区域范围内，就可以快速确定这个loc包含的信息是否是我们需要的信息。另外右侧的部分是tfidf的含义解读，tfidf主要用来描绘出词汇在文章中的信息量。tf表示文章中包含该词的个数，df表示含有这个词的文章的个数，idf表示倒排文章频率，用来描绘文本稀缺度。N表示总库存的文章数。通过tfidf，我们可以对文章的信息度进行一个相对粗略的判断，可以说tfidf是信息检索的鼻祖算法，之后的一系列其他的算法都是对tfidf的补充及优化。

图3.4

Query操作符

操作符一般来说可以分为三类，一类用来构建新的倒排索引，其中有#SYN，#NEAR，#WINDOW；一类用来生成分数列表，它的操作符是#SCORE；一类用来合并生成好的分数列表，其中有#AND，#OR，#WSUM。我们之前已经讲完了倒排索引，我们自然可以构建nike ，aj，阿迪等等的倒排索引，但是光这些基础结构很难满足我们的需求。因此，我们还需要一些其他结构的倒排索引，比如说布莱克奥巴马，比如说aj1。这样的query其实是由两个或者多个词合并而出的短语，为了保证其中的次序性能够被正确识别，我们在这个时候就需要使用NEAR或者WINDOW操作符来进行词汇链接。而另外比如syn操作符可以用来构建一些概念性质的倒排。比如各类颜色的集合。这些操作符可以用来帮助我们在不同的情境下构建一些复杂的query。Score操作符比较容易理解，我们通过我们构建的一些记分算法来讲一个倒排索引构建成一份分数列表。#AND和#OR这些操作符则是用来合并已经构建好的分数列表（图4.1）(Callan, 2020)。

图4.1

下图左侧及右侧就是从倒排索引转化为分数列表的过程（图4.2），无论我们使用的算法是什么，结构都会大同小异，唯一有区别的就是得到的记分结果。这边是一个例子，表达了这个倒排索引到计分模式的具体过程。每一个docid和其对应的分数都代表了这个文章与这个query的关联程度。一般来说在进行排序的过程里，我们基本遵循分数高的文章排名就高的原则，而排名越高，你在搜索引擎内的展示位置也就会越高。但值得注意的是，从倒排索引到分数列表的转化过程是不可逆的，我们可以根据倒排获得分数列表，反之则不行。因为在这个过程中，我们在是丢失了一定信息的，比如说这个字符所处的位置，它tf值等等，所以计分的过程往往是在整个流程的最后一步，具体流程可见上图（图4.1）。

图4.2

搜索算法

讲完了文章结构与操作符，搜索引擎的冰山一角已经被我们剖析了出来。如果把搜索引擎比做修炼，那我们基础已经打完了，接下来我们进入硬核部分-搜索算法，了解完了搜索算法，那你基本可以开始尝试构建自己的小型搜索引擎了。首先，我们讨论一下从倒排索引到分数列表过程中可能会使用到的一些粗排算法。搜索引擎查找信息的过程其实是我们在用各种各样的方法来解释我们的信息，通过算法一步一步的压缩召回池的数量，最后通过排序来获得我们想要的信息（即排序好的文章）。

最简单的粗排算法就是UnRankedBoolean和RankedBoolean两种，它们都是精确查找的过程。在过去人们认为文档就是一个词袋的集合，那么只要进行精确查找就行了。第一种unrankbooolean顾名思义得到的信息是无序的。这种方法简单直接，得分匹配就是1，不匹配就是0在90年代前一直都是主宰级的办法，但是现在已经基本被淘汰了，因为人们开始逐渐发现人们很难确保query本身是准确的。RankedBoolean就是给予文章得分，办法也很简单，单纯依据tf得分。

那我们讲完了基本被淘汰的exact match，我们来聊一聊best match，best match有以下几种：

1.Vector space retrieval model (VSM)

2.Probabilistic retrieval model (BM25)

3.Statistical Language Model (query likelihood)

4.Inference networks (Indri)

由于vector space已经基本被业界弃用了，所以我们这边不对它进行展开。我们先主要聊一聊BM25。BM25的展开公式如下图所示（图5.1）：

图5.1

BM25算法由Steve Robertson创建。BM25刚开始叫BM10，BM15，随着一系列的实验和调参最后成了现在这样。第一部分叫RSJ weight，叫这个是因为Roberson开发了这个算法，Karen Spark Jones是他的mentor，辅助他开发了这个算法，所以联合命名为RSJ weight。它其实很像idf，主要在idf上做了进一步的优化。这边的tf weight主要是对文本的长度做了一个标准化（normalization）。因为一个词汇在如果在一篇20字的文本中出现了一次和在一篇2000字的文章中出现了一次，所代表的置信度应该是不一样的，通过标准化处理，我们可以在一定程度上消除长文章的不正当竞争优势。另一块是user weight，主要用来调节用户的权重，这一部分我们可以相对忽略，业务在实际调参中，user weight的值一般为1。在这三个可调节参数中，K1调节的是这个调节幅度的强度，B用来调节的是文本长度normalization的程度，K3用来调节的是用户权重的程度（图5.2）。

图5.2

BM25到这儿基本结束，接下来我们讲下Two-Stage Smoothing算法。要估计一个词汇在文档中出现的估计，很多人首相想到的可能是最大似然估计（Maximum Likelihood Estimation）。但是在搜索中他是有缺陷的，比如说我们要搜镭射粉aj夏款，那么可能镭射粉aj是有的，但是夏款没有。那么夏款这个词的MLE score就是0，而我们最后是要把镭射粉aj的分数和夏款的分数相乘的，那么最后结果就是无结果，什么都搜索不到。这个时候smoothing function就派上用场了，首先我们需要处理一些很少见的term，其次我们要平滑一些很短的文章。首先我们先介绍下这个jelinek-mercer smoothing function。也叫混合模型。这个模型下我们会有两个最大似然估计，一个是query term基于文档的，一个是query term基于库的。Lambda用来控制平滑的程度，一般来说当lambda趋向于0的时候，平滑程度趋向于0。那么如何选取lambda呢，我们的实验建议是小的lambda适用于短的query，是大的lambda适用于长的query。另一个平滑方法是狄利克雷特先验平滑算法，这个算法它的目的是为了调节稀有词和高频词在词库中的出现频次。一般来说mu的值在1000到10000中为比较合适的范畴。上述各个平滑算法及MLE算法的公式如下所示（图5.3）

图5.3

讲完了BM25和平滑算法，我们来讲一下indri（图5.4），Indri是用统计语言模型和贝叶斯干扰网络构成的。听起来可能很吓人，但是仔细总结一下，他的关键在于以下几点。1.它是一个概率型检索模型。2query是结构化的，3.文档由多样的形式进行表现。这个看起来很复杂，但其实并不复杂，具体表现形式如下(Callan, 2020)：

图5.4

首先我们有一个网页，每个网页有着它所属的网络结构，比如说标题，主题，URL等等。那么很自然，我们可以将文章拆解为不同的区块。与此同时，我们在前文提到过平滑模型，我们通过将平滑模型中的两个参数与文章结构相结合我们就可以得到一个文本语言模型，即在这个区块中的贝叶斯概率值。另外，每一个文档区块都可以拆分成不同的子节点表现形式，比如单字，短语等等，它们也有着各自所对应的贝叶斯概率。这样的话，在文档层面我们就完成了语言模型到贝叶斯概率的转变。

然后我们往下看，I表示某个人的信息需求，这个信息需求一般由一个query来表示，而这个query又由许多子query来构建，我们现在可以思考一下and，or ，Near等操作符。对于每一个query，我们都可以先用nlp拆词拆分成小的单字，再通过操作符进行组合构建，这样每一个query概念就也包含了各自的贝叶斯概率。这就构建了一个query网络。之后，我们就可以将query网络和我们的文档网络建立连接。通过对query网络和文章网络对似然度进行匹配，我们就可以尽可能准确的找到准确度较高的文章，这就是我们整个indri网络的体系流程。

到目前为止，搜索引擎的文档架构，query处理以及粗排算法我们已经基本讲解完毕，后续我会继续跟进搜索算法中伪相关反馈，LetoR，个性化多样化排序等相关的内容。各位的关注就是我更新的动力～。

[0]1=margin: 0px; padding: 0px; min-height: 24px;|[0]2=margin: 0px; padding: 0px; min-height: 24px;|[0]3=margin: 0px; padding: 0px; min-height: 24px;|[0]4=margin: 0px; padding: 0px; min-height: 24px;|[0]5=margin: 0px; padding: 0px; min-height: 24px;|[0]6=margin: 0px; padding: 0px; min-height: 24px;|[0]7=margin: 0px; padding: 0px; min-height: 24px;|[0]8=margin: 0px; padding: 0px; min-height: 24px;|[0]9=margin: 0px; padding: 0px; min-height: 24px;|[0]10=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]11=margin: 0px; padding: 0px; min-height: 24px;|[0]12=margin: 0px; padding: 0px; min-height: 24px;|[0]13=margin: 0px; padding: 0px; min-height: 24px;|[0]14=margin: 0px; padding: 0px; min-height: 24px;|[0]15=margin: 0px; padding: 0px; min-height: 24px;|[0]16=margin: 0px; padding: 0px; min-height: 24px;|[0]17=margin: 0px; padding: 0px; min-height: 24px;|[0]18=margin: 0px; padding: 0px; min-height: 24px;|[0]19=margin: 0px; padding: 0px; min-height: 24px;|[0]20=margin: 0px; padding: 0px; min-height: 24px;|[0]21=margin: 0px; padding: 0px; min-height: 24px;|[0]22=margin: 0px; padding: 0px; min-height: 24px;|[0]23=margin: 0px; padding: 0px; min-height: 24px;|[0]24=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]25=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]26=margin: 0px; padding: 0px; min-height: 24px;|[0]27=margin: 0px; padding: 0px; min-height: 24px;|[0]28=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]29=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]30=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]31=margin: 0px; padding: 0px; min-height: 24px;|[0]32=margin: 0px; padding: 0px; min-height: 24px;|[0]33=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]34=margin: 0px; padding: 0px; min-height: 24px;|[0]35=margin: 0px; padding: 0px; min-height: 24px;|[0]36=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]37=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]38=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]39=margin: 0px; padding: 0px; min-height: 24px;|[0]40=margin: 0px; padding: 0px; min-height: 24px;|[0]41=margin: 0px; padding: 0px; min-height: 24px;|[0]42=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]43=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]44=margin: 0px; padding: 0px; min-height: 24px;|[0]45=margin: 0px; padding: 0px; min-height: 24px;|[0]46=margin: 0px; padding: 0px; min-height: 24px;|[0]47=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]48=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]49=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]50=margin: 0px; padding: 0px; min-height: 24px;|[0]51=margin: 0px; padding: 0px; min-height: 24px;|[0]52=margin: 0px; padding: 0px; min-height: 24px;|[0]53=margin: 0px; padding: 0px; min-height: 24px;|[0]54=margin: 0px; padding: 0px; min-height: 24px;|[0]55=margin: 0px; padding: 0px; min-height: 24px;|[0]56=margin: 0px; padding: 0px; min-height: 24px;|[0]57=margin: 0px; padding: 0px; min-height: 24px;|[0]58=margin: 0px; padding: 0px; min-height: 24px;|[0]59=margin: 0px; padding: 0px; min-height: 24px;|[0]60=margin: 0px; padding: 0px; min-height: 24px;|[0]61=margin: 0px; padding: 0px; min-height: 24px;|[0]62=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]63=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]64=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]65=margin: 0px; padding: 0px; min-height: 24px;|[0]66=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]67=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]68=margin: 0px; padding: 0px; min-height: 24px;|[0]69=margin: 0px; padding: 0px; min-height: 24px;|[0]70=margin: 0px; padding: 0px; min-height: 24px;|[0]71=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]72=margin: 0px; padding: 0px; min-height: 24px;|[0]73=margin: 0px; padding: 0px; min-height: 24px;|[0]74=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]75=margin: 0px; padding: 0px; min-height: 24px; text-align: center;|[0]76=margin: 0px; padding: 0px; min-height: 24px;|[0]77=margin: 0px; padding: 0px; min-height: 24px;|[0]78=margin: 0px; padding: 0px; min-height: 24px;|[0]79=margin: 0px; padding: 0px; min-height: 24px;|[0]80=margin: 0px; padding: 0px; min-height: 24px;|[0]81=margin: 0px; padding: 0px; min-height: 24px;|[0]0,0,0=font-size: 22px;|[0]2,1=font-size: 13px;|[0]6,0,0=font-size: 22px;|[0]16,0,0=font-size: 22px;|[0]39,0,0=font-size: 22px;|[0]41,1=font-size: 13px;|[0]50,0,0=font-size: 22px;|[0]73,1=font-size: 13px;