由浅到深，入门搜索原理

2022-03-06

本次带来电商搜索业务的介绍，电商搜索系列分为两篇文章：

电商搜索业务介绍
由浅到深，入门搜索原理

本文均以开源搜索引擎ES(Elasticsearch)为例，下文简称ES。

首先，本篇文章对于初次接触的同学来讲，涉及的概念会比较多，主要如下：

搜索名词概念描述

文档(Doc) ？

词条(Term) ？

倒排索引(Inverted Index) ？

关键字(Query) ？

召回(Recall) ？

词频(tf:Term Frequency) ？

逆文档率(idf:Inverse Document Frequency) ？

粗排？

精排？

本篇文章由简到繁入门搜索原理，并逐步揭开上面这些概念的面纱。本文结构如下：

搜索引擎ES的诞生
简易版搜索过程
进阶版搜索过程
- 索引过程
  - 什么是文档(Doc)
  - 什么是词条(Term)
  - 什么是倒排索引(Inverted Index)
  - 文档(Doc)分析
    - 字符过滤器
    - 分词过滤器
  - 创建倒排索引
- 查询过程
  - 关键字(Query)分析
    - 字符过滤器
    - 分词过滤器
  - 召回(Recall)
    - 什么是召回(Recall)
  - 排序
    - 什么是词频(tf:Term Frequency)
    - 什么是逆文档率(idf:Inverse Document Frequency)
    - 粗排/精排
- 搜索过程总结
搜索引擎ES进阶
- 索引(名词)的基本结构
- 搜索引擎ES的逻辑结构

搜索引擎ES的诞生

ES诞生于一个开源的JAVA库Lucene。通过Lucene官网的描述我们可以发现Lucene具备如下能力：

Lucene是一个JAVA库
Lucene实现了拼写检查
Lucene实现了命中字符高亮
Lucene实现了分析、分词功能

Lucene不具备的能力：

所以多年之前名叫Shay Banon的开发者，通过Lucene实现了一个高可用的开源分布式搜索引擎Elasticsearch。

常见的搜索功能都是基于「搜索引擎」实现的，接着我们来看看简易版搜索过程。

简易版搜索过程

简易版搜索过程如下：

第①步：索引过程，需要被搜索的源数据被索引(动词)到搜索引擎中，并建立索引(名词)。
第②步：查询过程，用户输入关键字(Query)，搜索引擎分析Query并返回查询结果。

进阶版搜索过程

什么是文档(Doc)

举个栗子，比如《电商设计手册 | SkrShop》网页内容需要被搜索到，那这页网页的全部内容就称之为一个文档Doc。

文档Doc内容如下：

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>电商设计手册 | SkrShop</title>
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
  <meta name="description" content="应该是最全、最细致、最落地的电商系统设计手册">
  <!-- 省略...... -->
  <p>秒杀是电商的一种营销手段</p>
  <!-- 省略...... -->

搜索名词概念描述

文档(doc) 需要被搜索的文本内容，可以是某个商品详细信息、某个网页信息等等文本。

什么是词条(Term)

继续以上文的文档Doc为例。为了简化对词条(Term)的理解，把上述文档Doc的内容简化为一句话秒杀是电商的一种营销手段。

词条(Term)就是文档Doc经过分词处理得到的词条结果集合。比如秒杀是电商的一种营销手段被中文分词之后得到：

秒杀 / 是 / 电商 / 的 / 一种 / 营销 / 手段

秒杀、是、电商、的、一种、营销、手段分别称之为词条(Term)，该集合称之为Terms。

搜索名词概念描述

词条(Term) 被搜索的文本Doc被分词器拆解成N个标准的语句。

什么是倒排索引(Inverted Index)

「倒排索引」是索引(动词)源数据时，创建的索引(名词)的具体实现。

我们以如下文档(Doc)为例，解释倒排索引：

文档ID 文档内容(Doc)

1 电商设计手册SkrShop

2 秒杀是电商的一种营销手段

3 购物车是电商购买流程最重要的一步

分词器：文档(Doc)拆解为多个独立词条(Doc -> Terms)。

开源中文分词器：

IK Analyzer
jieba

以jieba分词器在线演示为例：https://app.gumble.pw/jiebademo/

文档ID 文档内容(Doc) 中文分词结果(Terms)

1 电商设计手册SkrShop 电商 / 设计 / 手册 / SkrShop

2 秒杀是电商的一种营销手段秒杀 / 是 / 电商 / 的 / 一种 / 营销 / 手段

3 购物车是电商购买流程最重要的一步购物车 / 是 / 电商 / 购买 / 流程 / 最 / 重要 / 的 / 一步

每个词条对应的文档ID如下：

词条文档IDs

电商 1、2、3

设计 1

手册 1

SkrShop 1

秒杀 2

是 2、3

的 2、3

一种 2

营销 2

手段 2

购物车 3

购买 3

流程 3

最 3

重要 3

一步 3

以上就是建立倒排索引的基本过程。

完成倒排索引建立之后，模拟搜索过程，假设：

搜索电商，能快速找到文档1、2、3
搜索营销，能快速找到文档2

(这个过程叫做「召回」)

以上就是「倒排索引」的概念。

搜索名词概念描述

倒排索引(Inverted Index) 索引(动词)源数据时，创建的索引(名词)的具体实现。

文档(Doc)分析

分析就是标准化文档(Doc)文本的过程，以及把文档(Doc)转换成标准化词条(Term)的过程。搜索引擎ES分析过程的实现依赖于分析器。

分析器基本组成：

字符过滤器
分词过滤器

字符过滤器

一个分析器对应一个字符过滤器。

格式化为标准文本(text -> standard text)，例如去掉文本中的html标签。

比如<p>电商设计手册SkrShop</p>—>电商设计手册SkrShop

一个分析器对应一个分词器。

文档(Doc)拆解为多个独立词条(doc -> terms)的过程。举个例子：
比如电商设计手册SkrShop—>电商 / 设计 / 手册 / SkrShop

这里还需要提到的是自定义词库：原始词库不具备的词汇，比如最近新产生的网络词汇。

分词过滤器

一个分析器对应N个分词过滤器。

统一转小写
近义词转换

分词过滤器示例

统一转小写适用于英文等。比如统一把英文字母转换为小写，例Word -> word

近义词转换适用于各语言。例宽敞 -> 宽阔

停用词适用于各语言。去除含义宽泛不具备代表性的词语和其他人工指定停用的词语，例的、是。中文停用词库：https://github.com/goto456/stopwords

提取词干适用于英文等。例words -> word

纠错适用于各语言。例宽肠 -> 宽敞

自动补全适用于各语言。

索引过程总结

搜索名词概念描述

关键字(Query) 发起搜索是用户输入的关键字

关键字(Query)分析

关键字(Query)同样需要经过分析器，且和文档索引过程是相同的分析器。

相同分析器：

相同字符过滤器
相同分词器
相同分词过滤器

关键字(Query) 中文分词结果(Terms)

秒杀系统的设计秒杀 / 系统 / 的 / 设计

词条(Terms)

秒杀

系统

的

设计

分词过滤器：

此处以停用词分词过滤器为例讲解分词过滤器的过程，本文使用的停用词库示例：https://github.com/goto456/stopwords/blob/master/cn_stopwords.txt

得到去除了停用词的之后的词条(Terms)集合：

词条(Terms)

秒杀

系统

设计

召回(Recall)

什么是召回(Recall)

使用上文的文档内容以及文档分词结果：

文档ID 文档内容(Doc) 中文分词结果(Terms)

1 电商设计手册SkrShop 电商 / 设计 / 手册 / SkrShop

2 秒杀是电商的一种营销手段秒杀 / 是 / 电商 / 的 / 一种 / 营销 / 手段

3 购物车是电商购买流程最重要的一步购物车 / 是 / 电商 / 购买 / 流程 / 最 / 重要 / 的 / 一步

进一步使用分词过滤器过滤分词结果，以相同的停用词分词过滤器为例。本文使用的停用词库示例：https://github.com/goto456/stopwords/blob/master/cn_stopwords.txt

比如命中了停用词是：

经过停用词分词过滤器之后的结果：

文档ID 文档内容(Doc) 中文分词结果(Terms)

1 电商设计手册SkrShop 电商 / 设计 / 手册 / SkrShop

2 秒杀是电商的一种营销手段秒杀 / 电商 / 一种 / 营销 / 手段

3 购物车是电商购买流程最重要的一步购物车 / 电商 / 购买 / 流程 / 重要 / 一步

进一步得到倒排索引结构：

词条文档IDs

电商 1、2、3

设计 1

手册 1

SkrShop 1

秒杀 2

一种 2

营销 2

手段 2

购物车 3

购买 3

流程 3

重要 3

一步 3

接着模拟搜索过程，假设用户搜索秒杀系统的设计：

关键字(Query) 中文分词结果(Terms)

秒杀系统的设计秒杀 / 系统 / 的 / 设计

词条(Terms)

秒杀

系统

的

设计

分词过滤器，使用同上过程的停用词分词过滤器为例，得到去除了停用词的之后的词条(Terms)集合，称之为关键字(Query)的词条集合：

词条(Terms)

秒杀

系统

设计

关键字(Query)的词条秒杀，通过上述倒排索引可以很容易找到文档2
关键字(Query)的词条系统，通过上述倒排索引没有找到任何文档
关键字(Query)的词条设计，通过上述倒排索引可以很容易找到文档1

这样用户搜索秒杀系统的设计就找到了如下文档：

文档2：秒杀是电商的一种营销手段
文档1：电商设计手册SkrShop

以上过程就是召回。

搜索名词概念描述

召回(Recall) 搜索引擎利用倒排索引，通过词条获取相关文档的过程。

上述召回过程，用户通过搜索秒杀系统的设计找到了文档1、2。

补充：以上基于倒排索引的文本召回方式。除此之外还有基于相同类目、其他相似属性的召回方式，以及基于深度学习的向量召回。

接着问题来了：

召回的文档1、2，谁在前，谁在后的顺序怎么决定呢？

接着下文来讲搜索引擎排序的实现。

引入上面的问题：

文档1、2，谁在前，谁在后的顺序怎么决定呢？

答：文档的相关性决定的，搜索引擎会给文档的相关性进行打分score。通常决定这个分数score主要是两个指标：

文档率：tf(Term Frequency)
逆文档率：idf(Inverse Document Frequency)

可以简单理解为相关性score = 文档率 * 逆文档率，相关性score的值越高排序越靠前，接着，我们分别看看相关概念的含义。

什么是词频(tf:Term Frequency)

还是使用上面的文档：

文档ID 文档内容(Doc) 中文分词结果(Terms)

1 电商设计手册SkrShop 电商 / 设计 / 手册 / SkrShop

2 秒杀是电商的一种营销手段秒杀 / 电商 / 一种 / 营销 / 手段

3 购物车是电商购买流程最重要的一步购物车 / 电商 / 购买 / 流程 / 重要 / 一步

这里我们以词条：电商/秒杀为例。

词频的简单算法：词频 = 词条在单个文档出现的次数/文档总词条数，词频的值越大越相关，反之越不相关。

比如，秒杀一词在文档1中出现的频率，以单个文档的全部词条为维度，我们简单的到了秒杀一词在各文档的词频：

文档ID 文档内容(Doc) 中文分词结果(Terms) 词条在单个文档出现的次数词频(秒杀)

1 电商设计手册SkrShop 电商 / 设计 / 手册 / SkrShop 0 0/4=0

2 秒杀是电商的一种营销手段秒杀 / 电商 / 一种 / 营销 / 手段 1 1/5=0.2

3 购物车是电商购买流程最重要的一步购物车 / 电商 / 购买 / 流程 / 重要 / 一步 0 0/6=0

同理，我们简单的到了电商一词在各文档的词频：

文档ID 文档内容(Doc) 中文分词结果(Terms) 词条在单个文档出现的次数词频(电商)

1 电商设计手册SkrShop 电商 / 设计 / 手册 / SkrShop 1 1/4=0.25

2 秒杀是电商的一种营销手段秒杀 / 电商 / 一种 / 营销 / 手段 1 1/5=0.2

3 购物车是电商购买流程最重要的一步购物车 / 电商 / 购买 / 流程 / 重要 / 一步 1 1/6=0.167

搜索名词概念描述

词频(tf:Term Frequency) 词条在单个文档出现的次数/文档总词条数

什么是逆文档率(idf:Inverse Document Frequency)

对于单个文档而言，词频越的值越相关，这个对于单个文档的维度。

思考个问题，如果某个词条在所有文档都出现，相关性越好还是越不好？

答：不好，对吧。

这个就是文档率：文档率 = 包含某个词条的文档数 / 所有文档数，文档率值越大越不相关，反之相关。

因为词频的值越大越相关，反之越不相关。为了保证和词频的逻辑一致，以及最终相关得分越高越相关，调整了文档率的算法，调换了分子分母：所有文档数 / (包含某个词条的文档数 + 1)加1保证分母不为零，这个就是逆文档率。

逆文档率 = 所有文档数 / (包含某个词条的文档数 + 1)。

但是呢，因为文档数往往特别大，上面的到的逆文档率的值会巨大无比，所以调整下公式，引入对数，降低值的大小，且让值变得平滑：

逆文档率 = log(所有文档数 / (包含某个词条的文档数 + 1))

词条(Term) 逆文档率

电商 log(3/(3+1))

秒杀 log(3/(1+1))

最终就计算出每个文档分别对应每个Query词条的相关性score(tf/idf)：相关性score = 文档率 * 逆文档率。

粗排/精排

上面利用tf/idf分数(相关性score = 文档率 * 逆文档率)排序的结果只是对召回文档的初步排序，称之为粗排。得到粗排的结果后，通常还会把文档按照实际业务的要求进行更精确的排序，比如通过人工干预增加一些文档的权重，使之排序更靠前，这个过程就是精排。

搜索名词概念描述

粗排利用tf/idf分数排序召回文档的过程

精排把粗排结果，按照实际业务的要求更加精确的排序等等

搜索过程总结

索引过程：文档(Doc) -> 分析 -> 倒排索引。

查询过程：关键字(Query) -> 分析 -> 召回 -> 粗排 -> 精排。

搜索引擎ES进阶

索引(名词)的基本结构

索引index
- 类型type：区分不同的文档数据结构类型
  - 映射mapping：管理索引的属性，比如使用的分析器等等
  - 文档doc：需要被搜索的具体文档

进一步完善搜索过程：加入更详细的索引(名词)结构

由浅到深，入门搜索原理

由浅到深，入门搜索原理

搜索引擎ES的诞生

简易版搜索过程

进阶版搜索过程

什么是文档(Doc)

什么是词条(Term)

什么是倒排索引(Inverted Index)

文档(Doc)分析

字符过滤器

分词过滤器

索引过程总结

关键字(Query)分析

召回(Recall)

什么是召回(Recall)

什么是词频(tf:Term Frequency)

什么是逆文档率(idf:Inverse Document Frequency)

粗排/精排

搜索过程总结

搜索引擎ES进阶

索引(名词)的基本结构

搜索引擎ES的逻辑结构

Recommend

智能 3D 草图尺寸标注

Nginx 添加SSL证书

Download Progress With Awaited Network Tasks

熊林卸任北京自如生活企业管理公司董事长,周艺君接任

# yyds干货盘点 # Python解析库lxml与xpath用法总结

The Sun is Spectacular Today in H-Alpha (Shallow Thoughts)

MySQL误删数据怎么恢复（1）delete误删恢复

配置使用SSL加密的vsftpd服务

游戏开发新手入门教程7:谁来帮我做记录

How to make a transparent navigation bar in iOS

About Joyk