关于算法:得物技术浅谈搜索引擎技术简介

导读

搜索引擎是一种联合自然语言解决，信息检索，网页架构，分布式数据处理为一体的帮忙用户精确解释信息获取信息的一种技术。

目前业界在网页端与手机端的支流门户搜寻份额根本被各类巨头 (图 1.1)(SEO, 2020) 所宰割。当然，随着时代的倒退，搜寻越来越向以细分业务为主导的精细化门户搜寻的方向倒退。比方你会抉择在知乎搜寻专栏常识，在得物搜寻潮流爆品，在美团点评搜寻吃喝玩乐等等。

THE NO.1

信息检索

搜索引擎

咱们要聊搜索引擎，那必然离不开信息检索（information retrieval）。

首先咱们对何为信息检索须要有一个明确的定义：通过在一个大的数据汇合中找到满足信息需要（information needs）的非结构化天然模式（通常指文本语料库）的资料（个别指代文章）(Manning, 2008)。

在检索信息时，有两个指标是在探讨搜寻性能时无可避免。一个是 召回率（recall），另一个是 准确率（percision）。乏味的是，这两个指标就像一对孪生兄弟，总是此长彼消，此消彼长，因而，如何做好其中的制衡是各个搜索算法面临的问题。

本文作为搜索引擎技术的启蒙文章，次要针对文章构造、倒排索引、操作符与查找算法这四个维度来解说一下搜索引擎的根本工作流程。

THE NO.2

文章构造

文档

首先咱们来谈一谈搜索引擎都是如何了解它的那些文档的。在聊这个话题之前，咱们要先明确一个定义，搜索引擎分为两种，网页级搜索引擎和公司级搜索引擎。

无论是那种搜索引擎，它们第一件须要解决的问题就是了解语料库，之后要做的就是存储语料库。

那么如何了解呢？当初让咱们来看一下根本的文档的脉络机构。

很多时候人们个别认为文档就能够看作一个独立的词袋。但其实不然，每个文档其实是由不同的组成部分形成的。

比方个别网页的构建逻辑根本会是 XML 模式形成的，在大类上咱们把它们分成三层，第一层是 metadata，外面个别会有_url、关键字、作者、日期_等等，第二层是body，外面个别蕴含的就是像_题目、主体内容_这些信息。第三层是 内部信息，次要有一些_内部链接与外部链接_跳转。

分区能够帮忙咱们对各个区块的信息量进行一个辨别，起因在于每个区块的信息熵是不一样的。

简而言之，蕴含的信息量不一样，比方文章题目含有关键词的信息量就相对而言要大于段落中蕴含这个关键词所有的信息量。

得物搜寻

在咱们得物平台，次要有两个搜寻次要发力点：商品和社区。那也能够进行这样的分层，尽管具体的信息分层形式有所变动，然而具体的设计逻辑仍然不变。

依据香农定理外面的信息论，这些文档它们提供的信息价值是不同的，信息熵也是不同的，如果把他们一概而论的话，咱们搜寻的准确度必然会有肯定水平的升高。

一般而言，文档题目蕴含的信息量要略高于文档主体的信息量，通过将内部结构分层的操作，咱们在前期进行算法干涉的时候就能够人为的对其中的内容的权重进行调整，从而进步咱们所召回内容与用户输出 query 合乎度的精确水平，更好的满足用户的搜寻冀望。

THE NO.3

倒排索引

存储

讲完了文档的构造，咱们就要探讨下如何对这些文档构造用数据结构进行存储。置信大家都晓得，咱们在搜索引擎存储信息个别采纳 倒排索引，而倒排索引次要分为两种索引构造。

第一种方法咱们针对的是 平铺的页面布局，也就是我后面所提到的将所有页面的各个区块独立看待的办法。说白了萝卜是萝卜，坑就是坑，各个信息块之间各自独立，没有交互。

而第二种构造咱们采纳的是 垂直构造，也就是说，咱们令页面中的各个布局存在层级关系。

我拿主体局部举个例子，主体局部 -> 区块 -> 段落 -> 句子。

平铺的页面布局

首先咱们来讲下第一种归并倒排索引，咱们看下构建模式。

咱们在举荐和博文这两个 field 外面都有一个词典，那咱们在这儿要做的就是把各自的词典和它所对应的 field 合并起来。

在这里咱们须要留神的是，一个 term 将会有多个倒排索引，比如说 bush 这个词，在举荐这儿咱们为它构建了一个倒排，在博文这儿咱们也为它构建了一个倒排。

在这种状况下，咱们不会把不同 field 的信息杂糅在一起。很屡次和 bush 一样都具备歧义性，通过建设各自独立的倒排索引，能够无效的保障信息的独立性。

垂直构造

有的时候咱们搜寻信息时，并不需要搜寻到全副的信息，可能咱们只想要搜寻到特定地位的特定信息。

如果咱们想要搜寻句子外面的癌症，在归并构造下，咱们的搜寻过程就会变得很是简单，咱们要先从文章再到章节再到句子，很显然，如果采纳这样的构造，咱们的搜寻速度很受到肯定的影响。

因而，咱们须要的采纳一种比拟精美的独立倒排索引构造，这种构造个别面向的是那种绝对比较复杂的文章构造。

咱们接下来看一下这个树形构造，在这种构造下，咱们会记录下文档各个词所在的地位以及它们的上下级父子关系。

如果咱们要搜寻位于地位 6 和地位 27 的信息，咱们就会先溯源到搜寻脉络中所处的地位，之后用一种绝对疾速的形式疾速检索到信息（log 级别的速度）。

如果要搜在章节地位的信息，那么它就会抛弃 loc 为 6 的信息，因为 loc 为 6 的信息在树结构中属于作者这个区块。

这样的形式能够大大晋升咱们的搜寻效率，而咱们须要付出的只是唯不足道的一些内存而已，在这个云存储的时代，这样的操作十分具备性价比。

齐全倒排

除此之外，咱们也能够用齐全倒排的办法来构建倒排索引 - 即独立倒排模式。

咱们能够把 field 的边界阈值寄存在倒排索引外面，另外构建一个 term 的倒排索引，通过把这两个进行归并，即可构建独立倒排。

比如说在这儿咱们假如这是一个句子的倒排索引，开始和起始为止标注在那儿了，extentFreq 示意这是第几个 field。

当咱们确立好 loc 的具体值时，咱们只须要到旁边的 [begin,end] 判断是否在区域范畴内，就能够疾速确定这个 loc 蕴含的信息是否是咱们须要的信息。

另外右侧的局部是 tfidf 的含意解读：

tfidf 次要用来描绘出词汇在文章中的信息量；tf 示意文章中蕴含该词的个数；df 示意含有这个词的文章的个数；idf 示意倒排文章频率，用来描述文本稀缺度 N 示意总库存的文章数。

通过 tfidf，咱们能够对文章的信息度进行一个绝对粗略的判断，能够说 tfidf 是信息检索的鼻祖算法，之后的一系列其余的算法都是对 tfidf 的补充及优化。

THE NO.4

Query 操作符

操作符分类

操作符一般来说能够分为三类，一类用来 构建新的倒排索引 ，其中有_#SYN，#NEAR，#WINDOW_；一类用来 生成分数列表 ，它的操作符是_#SCORE_；一类用来 合并生成好的分数列表，其中有_#AND，#OR，#WSUM_。

Callan, 2020*

分场景利用

这些操作符能够用来帮忙咱们在不同的情境下构建一些简单的 query。

NEAR 或者 WINDOW 操作符

咱们之前曾经讲完了倒排索引，咱们天然能够构建 Nike，AJ，阿迪等等的倒排索引，然而光这些根底构造很难满足咱们的需要。因而，咱们还须要一些其余构造的倒排索引，比如说布莱克奥巴马和 AJ1。

这样的 query 其实是 由两个或者多个词合并而出的短语，为了保障其中的秩序性可能被正确辨认，咱们在这个时候就须要应用 NEAR 或者 WINDOW 操作符来进行词汇链接。

syn 操作符

syn 操作符能够用来 构建一些概念性质的倒排，比方各类色彩的汇合。

Score 操作符

Score 操作符比拟容易了解，咱们通过咱们构建的一些 记分算法 来讲一个倒排索引构建成一份分数列表。

AND 和 #OR

#AND 和 #OR 这些操作符则是用来合并曾经构建好的分数列表。

THE NO.5

搜索算法

讲完了文章构造与操作符，搜索引擎的冰山一角曾经被咱们分析了进去。

如果把搜索引擎比做修炼，那咱们根底曾经打完了，接下来咱们进入硬核局部 – 搜索算法，理解完了搜索算法，那你根本能够开始尝试构建本人的小型搜索引擎了。

首先，咱们讨论一下从倒排索引到分数列表过程中可能会应用到的一些粗排算法。

搜索引擎查找信息的过程其实是咱们在用各种各样的办法来解释咱们的信息，通过算法一步一步的压缩召回池的数量，最初通过排序来取得咱们想要的信息（即排序好的文章）。

粗排

最简略的粗排算法就是 UnRankedBoolean 和 RankedBoolean 两种，它们都是准确查找的过程。在过来人们认为文档就是一个词袋的汇合，那么只有进行准确查找就行了。

Unrankbooolean

Unrankbooolean 顾名思义失去的信息是无序的。这种办法简略间接，得分匹配就是 1，不匹配就是 0。

在 90 年代前始终都是主宰级的方法，然而当初曾经根本被淘汰了，因为人们开始逐步发现人们很难确保 query 自身是精确的。

RankedBoolean

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。

BM25 的开展公式如下图所示。

BM25 算法由 Steve Robertson 创立。M25 刚开始叫 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用来调节的是用户权重的水平。

BM25 到这儿根本完结，接下来咱们讲下 Two-Stage Smoothing 算法。

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 算法的公式如下所示：

Indri

讲完了 BM25 和平滑算法，咱们来讲一下 Indri。

Indri 是用 统计语言模型和贝叶斯烦扰网络 形成的。

听起来可能很吓人，然而认真总结一下，他的关键在于以下几点：

1. 它是一个概率型检索模型
2. query 是结构化的
3. 文档由多样的模式进行体现

这个看起来很简单，但其实并不简单，具体表现形式如下：

Callan, 2020*

首先咱们有一个网页，每个网页有着它所属的网络结构，比如说题目、主题、URL 等等。那么很天然，咱们能够将文章拆解为不同的区块。

与此同时，咱们在前文提到过平滑模型，咱们通过将平滑模型中的两个参数与文章构造相结合咱们就能够失去一个文本语言模型，即在这个区块中的贝叶斯概率值。

另外，每一个文档区块都能够拆分成不同的子节点表现形式，比方单字、短语等等，它们也有着各自所对应的贝叶斯概率。这样的话，在文档层面咱们就实现了语言模型到贝叶斯概率的转变。

而后咱们往下看，I 示意某个人的信息需要，这个信息需要个别由一个 query 来示意，而这个 query 又由许多子 query 来构建，咱们当初能够思考一下 and/or/Near 等操作符。

对于每一个 query，咱们都能够先用 nlp 拆词拆分成小的单字，再通过操作符进行组合构建，这样每一个 query 概念就也蕴含了各自的贝叶斯概率。这就构建了一个 query 网络。

之后，咱们就能够将 query 网络和咱们的文档网络建设连贯。通过对 query 网络和文章网络对似然度进行匹配，咱们就能够尽可能精确的找到准确度较高的文章，这就是咱们整个 Indri 网络的体系流程。

引文阐明

SEO, 2020. SEO Search Engine – SEO Rank Services. [online] SEO Rank Services. Available at: https://seorankservices.com/search-engines-optimize-site/seo-search-engine/ [Accessed 3 February 2020].

Manning, C., 2008. Introduction To Information Retrieval. 1st ed.

Callan, J., 2020. Search Engine 11642 – Carnegie Mellon University.

文|Ray

关注得物技术