产品经理需要了解的搜索算法：搜索引擎之倒排索引

浪子无知

注：互联网时代，信息纷繁海量，人们通过搜索引擎直达“心中所想”已是常态。那么搜索引擎到底是如何高效查找目标内容呢？本文主要介绍搜索引擎里一个比较重要的结构——倒排索引。

一、倒排索引简介

倒排索引（英文：Inverted Index），是一种索引方法，常被用于全文检索系统中的一种单词文档映射结构。
现代搜索引擎绝大多数的索引都是基于倒排索引来进行构建的，这源于在实际应用当中，用户在使用搜索引擎查找信息时往往只输入信息中的某个属性关键字，如一些用户不记得歌名，会输入歌词来查找歌名；输入某个节目内容片段来查找该节目等等。
面对海量的信息数据，为满足用户需求，顺应信息时代快速获取信息的趋势，聪明的开发者们在进行搜索引擎开发时对这些信息数据进行逆向运算，研发了“关键词——文档”形式的一种映射结构，实现了通过了物品属性信息对物品进行映射，可以帮助用户快速定位到目标信息，极大地降低了信息获取难度。倒排索引又叫反向索引，它是一种逆向思维运算，是现代信息检索领域里面最有效的一种索引结构。
二、倒排索引&FAQ

从用户请求到结果返回，许多朋友会对倒排索引在检索系统中的工作过程产生好奇，本小节就倒排索引的一些常规认识，有如下问题：
Q1：何为索引？倒排索引又是什么？
索引，是为了加快信息查找过程，基于目标信息内容预先创建的一种储存结构。例如：一本书，没有目录，理论上也是可读的，只是当你合上当前在读的内容时，下次再翻开书本去查找，就比较耗费时间了。如果增加几页目录，我们可以快速地了解书本的大体内容分布，以及每一个章节页面位置的分布情况，这样我们查询内容的效率自然就会提高。书的目录，就是书本内容一种简单索引。
倒排索引，是索引技术中的一种，它是基于信息主体的关键属性值进行构建的。如下图1：

图1 倒排索引概念示例图

假设检索系统中只有一个商品——衣服A，基于该商品构建其倒排索引结构之后，会产生上图右表中的索引结构，这样用户可以通过搜“AAA”，“蓝色”，“M码”，“猴子”，均可找到该商品，加快了检索速度，扩大了检索范围。
Q2：当接受到用户查询请求时，倒排索引中发生了什么？
一般地，当接受到用户查询请求时，进入到倒排索引进行检索时，在返回结果的过程中，主要有以下几个步骤：

• Step1：在分词系统对用户请求等原始Query进行分析，产生对应的terms；
  
• Step2：terms在倒排索引中的词项列表中查找对应的terms的结果列表；
  
• Step3：对结果列表数据进行微运算，如：计算文档静态分，文档相关性等；
  
• Step4：基于上述运算得分对文档进行综合排序，最后返回结果给用户。
  

上述该过程是较为简洁的一个检索过程。事实上，在生产环境中因为业务环境的繁杂，会使得索引的设计模式变得复杂且繁多。前文主要通过概念图来介绍倒排索引的架构体系，一个成熟的检索系统往往拥有一套较为稳定的算法体系，用于处理生产环境中的每一处细节技术需求。上述步骤中涉及了大量相关的数据储存技术、查找算法、排序算法、文本处理技术甚至I/O技术等等。
3 倒排索引技术剖析
构建倒排索引是搜索引擎里面至关重要的一个步骤，从技术层面去分析，对于构造一个倒排索引，主要分为两部分：

• Doc2term词项构造；
  
• 倒排记录表的构建。
  

3.1 term词项构造
词项构造是在构建索引过程中必不可或缺的一个步骤，词项构造效果的好坏往往会直接影响到用户的搜索体验，以及搜索结果的召回。该过程主要是利用分词系统将文档中的各项属性的文本信息拆分成一些表意较强且重要的词汇，便于用户查找，如下图2：

图2 词项构造概念图

在词项构造的过程中，利用分词系统对文本进行处理时往往涉及到很多方面的问题，而且对于不同语种，会有不同的处理机制。下面主要介绍在处理文本时涉及到的几个问题：
（1）文本词条化
一段文本信息，它本身是一个由语言组成的字符串系列，本项技术点的主要任务是将一段连续的文本序列信息拆分成多个子序列。它与语言本身相关，面对不同的语言，处理文本的方式往往会不一样。对于中文，由于其语言多歧义且表意紧凑的特性，在实际应用中，一般需要借助NLP的相关技术对内容进行特征抽取，甚至人工标注等，生成对应的词典，随后再基于词典利用分词器进行分词，才能看到较好的文本词条效果。
而对于英文，普遍的英文句子，段落内容，它会以空格符作为单词之间的分隔符，所以一般情况下，以空格符对英文内容进行拆分，已经可以取得比较好的效果，不过英文中也会存在一些特殊模式，如带上撇号的格式——“Teacher’soffice”，连字符格式——“English-speaking”,也需要进行对应的处理，把单词提取出来。