搜查引擎之倒排索引解读

互联网时代，信息纷纷海量，人们经过搜查引擎中转“心中所想”已是常态。那么搜查引擎究竟是如何高效查找目的内容呢?本文关键引见搜查引擎里一个比拟关键的结构——倒排索引。

1 倒排索引简介

倒排索引(英文：InvertedIndex)，是一种索引方法，常被用于全文检索系统中的一种单词文档映射结构。现代搜查引擎绝大少数的索引都是基于倒排索引来启动构建的，这源于在实践运行当中，用户在经常使用搜查引擎查找信息时往往只输入信息中的某个属性关键字，如一些用户不记得歌名，会输入歌词来查找歌名;输入某个节目内容片段来查找该节目等等。面对海量的信息数据，为满足用户需求，顺应信息时代极速失掉信息的趋向，痴呆的开发者们在启动搜查引擎开发时对这些信息数据启动逆向运算，研发了“关键词——文档”方式的一种映射结构，成功了经过了东西属性信息对东西启动映射，可以协助用户极速定位到目的信息，极大地降落了信息失掉难度。倒排索引又叫反向索引，它是一种逆向思想运算，是现代信息检索畛域外面最有效的一种索引结构。(达观数据冯仁杰)

2 倒排索引&FAQ

从用户恳求到结果前往，许多好友会对倒排索引在检索系统中的上班环节发生猎奇，本小节就倒排索引的一些惯例看法，有如下疑问：

Q1 何为索引?倒排索引又是什么?

索引，是为了放慢信息查找环节，基于目的信息内容预先创立的一种贮存结构。例如：一本书，没有目录，通常上也是可读的，只是当你合上当前在读的内容时，下次再打开书本去查找，就比拟消耗期间了。假设参与几页目录，咱们可以极速地了解书本的大体内容散布，以及每一个章节页面位置的散布状况，这样咱们查问内容的效率人造就会提高。书的目录，就是书本内容一种方便索引。

倒排索引，是索引技术中的一种，它是基于信息主体的关键属性值启动构建的。如下图1：

图1 倒排索引概念示例图

假定检索系统中只要一个商品——衣服A，基于该商品构建其倒排索引结构之后，会发生上图右表中的索引结构，这样用户可以经过搜“AAA”，“蓝色”，“M码”，“猴子”，均可找到该商品，放慢了检索速度，扩展了检索范围。

Q2 当接遭到用户查问恳求时，倒排索引中出现了什么?

普通地，当接遭到用户查问恳求时，进入到倒排索引启动检索时，在前往结果的环节中，关键有以下几个步骤：

Step1：在分词系统对用户恳求等原始Query启动剖析，发生对应的terms;

Step2：terms在倒排索引中的词项列表中查找对应的terms的结果列表;

Step3：对结果列表数据启动微运算，如：计算文档静态分，文档相关性等;

Step4：基于上述运算得分对文档启动综合排序，***前往结果给用户;

上述该环节是较为繁复的一个检索环节。理想上，在消费环境中由于业务环境的冗杂，会使得索引的设计形式变得复杂且单一。前文关键经过概念图来引见倒排索引的架构体系，一个成熟的检索系统往往领有一套较为稳固的算法体系，用于处置消费环境中的每一处细节技术需求。上述步骤中触及了少量相关的数据贮存技术、查找算法、排序算法、文本处置技术甚至I/O技术等等。

3 倒排索引技术剖析

构建倒排索引是搜查引擎外面至关关键的一个步骤，从技术层面去剖析，关于结构一个倒排索引，关键分为两局部：1)Doc2term词项结构;2)倒排记载表的构建。(达观数据冯仁杰)

3.1 term词项结构

词项结构是在构建索引环节中必无法或缺的一个步骤，词项结构效果的好坏往往会间接影响到用户的搜查体验，以及搜查结果的召回。该环节关键是应用分词系统将文档中的各项属性的文本信息拆分红一些表意较强且关键的词汇，便于用户查找，如下图2：

图2 词项结构概念图

在词项结构的环节中，应用分词系统对文本启动处置时往往触及到很多方面的疑问，而且关于不同语种，会有不同的处置机制。上方关键引见在处置文本时触及到的几个疑问：

(1)文本词条化

一段文本信息，它自身是一个由言语组成的字符串系列，本项技术点的关键义务是将一段延续的文本序列信息拆分红多个子序列。它与言语自身相关，面对不同的言语，处置文本的方式往往会不一样。关于中文，由于其言语多歧义且表意紧凑的个性，在实践运行中，普通须要借助NLP的相关技术对内容启动特色抽取，甚至人工标注等，生成对应的词典，随后再基于词典应用分词器启动分词，能力看到较好的文本词条效果。而关于英文，广泛的英文句子，段落内容，它会以空格符作为单词之间的分隔符，所以普通状况下，以空格符对英文内容启动拆分，曾经可以取得比拟好的效果，不过英文中也会存在一些不凡形式，如带上撇号的格局——“Teacher’soffice”，连字符格局——“English-speaking”,也须要启动对应的处置，把单词提取进去。(达观数据 冯仁杰)

(2)停用词过滤

停用词是指在文档列表中出现的频数较高且价值不大的词。以英文为例，在英文文档中出现次数较多的停用词如：”is”、”the”、”I”、“and”、”me”等等;这一类词语在往往出如今一切文档中，若以此类词语为term启动索引构建，则会发生多个全量文档索引列表。停用词过滤的经常使用往往依赖于实践经常使用场景，关键字查问经常使用得较为频繁的场景如某一个电商品牌的垂直型搜查引擎，一个适合的停用词表显得尤为关键;而关于Web搜查引擎如百度、Google等，该类型的搜查引擎面向的查问场景较多，通用性较强，往往不须要停用词过滤。

(3)词条归一化

基于上述两点，将文档内容转换成一个或多个term后，在查问时，最理想的状况是用户输入的关键字刚好与term齐全婚配，实践上，很多时刻用户输入的query与词条之间往往不会齐全婚配，而用户们还是宿愿query能与词条启动婚配，比如用户在查问“color”时，用户必需也宿愿能看到关于“colour”的前往结果。词条归一化的义务就是将一些看起来不齐全分歧的词条划分为一个等价类，比如英式单词colour和美式单词color归为一类、Air-conditioner和airconditioner归为一类等等;这样，用户在查问时，只需平等价类中的恣意单词启动搜查，都会前往蕴含等价类中的恣意一个单词的文档。

(4)词干提取、词形恢复

这是词条规范化的两种关键方式，用于扩展检索范围。词干提取的关键思想是“缩减”，将词条转化为词干，如：将“beaches”处置成“beach”,将“bananas”处置成“banana”等;词形恢复的关键思想是“转换”，如：将“doing”、“done”、“did”转化成原型“do”，将“given”、“gave”转化成原型“give”等;词干提取的成功方法普通是基于规定对词条后缀启动缩减，至于词形恢复，其成功方法须要词典来启动词形变动的映射;基于在此联合词条归一化技术，对扩展检索范围会发生必定的正向作用。

3.2 倒排记载表的构建

倒排记载表的构建环节面向的是海量的文档数据汇合，在大小规模上它比词项汇合要大得多，无法齐全寄存在内存当中，须要写入磁盘。因此，在构建倒排记载表时咱们有必要为内存的经常使用作思考。

图3 倒排索引概念图

在无法全内存的状况下，倒排记载表的关键构建思想是“宰割”，亦即基于必定的处置逻辑对全量文档汇合启动等份的批量处置。关于不同的业务需求，构建倒排记载表的方法往往会不一样。基本的构建方法如下：

S1: 经过一系列的处置将文档汇合转化为“词项ID—文档ID”对;

S2: 对词项ID、文档ID启动排序，将具备相反词项对文档ID归并到该词项所对应的倒排记载表中，效果如图3所示;

S3: 将上述步骤发生的倒排索引写入磁盘，生成两边文件;

S4: 将上述一切的两边文件兼并成最终的倒排索引;

从业务运行场景的角度登程，倒排记载表的构建方法关键有：单遍扫描和多遍扫描;从工程角度登程，倒排记载表的构建方法关键有：散布式构建和灵活构建;

3.2.1 单遍扫描构建

望文生义，单遍扫描指的是仅对文档汇合启动一次性遍历，即可成功倒排索引的构建。由于内存开支疑问，会将全量文档集启动宰割，转换成几个内存大小相反的文档汇合，而后依次口头前文中提及到的构建方法。该方法能极速构建一个方便可行的倒排索引，协助用户经过关键字婚配极速找到目的文档。

3.2.2 多遍扫描构建

多遍扫描关键用于构建索引时失掉关于文档的更多相关信息，如一些词项TF-IDF目的、词频、文档内容相关等，以丰盛倒排记载表的内容，为搜查引擎启动配置扩大;在工业流水线上，单遍扫描构建索引由于其查问类型的丰盛度不够，显然曾经不能满足广阔用户的需求了。搜查用户的需求并不止于关键字查问，像短语查问、含糊查问、准确挑选、含糊挑选、排序、聚合统计等等需求。这象征着咱们在构建倒陈列表时要尽或许失掉文档的更多信息，便于查问时的微运算、重排序、相关性剖析等技术需求。

3.2.3 散布式构建

关于一些大型搜查引擎如Web搜查引擎，单台机器已无法撑持其索引构建，须要多台机器组成集群对其启动散布式处置，将构建成的倒排索引启动宰割，散布在多台机器上，每台机器各自构成独立的索引结构，当用户收回恳求时，会有多台机器照应，并且依据用户的搜查需求在各自的索引结构启动查问，前往相关结果，再将一切结果在内存中启动集中处置，***把处置过的***结果前往给用户。在详细的成功环节中，工程师们往往更钟情于一些通用的面向大规模机器计算的散布式架构如Hadoop中的MapReduce、Java中的Fork/join架构等，极大地提高了软件开发效率。(达观数据冯仁杰)

3.2.4 灵活构建

该方法中的文档汇合是变动的，这要求在对文档集启动索引构建时也要对文档的降级启动自顺应。此疑问经常出现于电商畛域里，如商品的高低架、商品内容的降级等，都会引发索引的灵活降级疑问。于此，咱们常采取一些战略型方法来处置该类型的疑问，提高索引的实时性。经常出现的战略如下两种：

1) 周期性对文档启动全量重建索引;

2) 基于主索引的前提下，构建辅佐索引，用于贮存新文档，保养于内存中，当辅佐索引到达必定的内存占用时，写入磁盘与主索引启动兼并;

战略1是最方便间接、且有效的索引降级战略，关于数量级较大的搜查引擎来说处置方便方便，由于灵活索引计算的复杂性，经常使用其它战略会使得索引难保养，甚至引发重大的性能疑问。所以大型搜查引擎往往更偏向于周期性重建索引，不过这会触及到索引热切换的疑问，少量的文档经常会发生继续性的文档降级状况，这关于索引热切换时会形成必定的艰巨，处置不好会造成数据失落，用户查不到新文档等疑问。

战略2中在启动主辅索引兼并时会遇到比拟大的贮存开支，由于文档量较大，这象征着在启动兼并操作时会触及到少量倒排文件的读写操作，要想将该环节高效化，目前能处置该疑问的文件系统极端***，所以该战略在消费环境中往往可用性并不高。

4 总结

在实践消费环境中，由于业务的冗杂，倒排索引的技术体系会比本文所论述的技术点要复杂得多。本文关键解说了倒排索引的作用、索引构建方法、用户行为剖析以及索引的运行场景，从全体登程，向大家引见现代倒排索引大抵的技术体系，协助大家了解倒排索引的概念，了解搜查引擎。或许本文论述的技术点、架构体系会由于笔者团体的了解偏向而存在一些无余或短少丰盛，如有不懂，欢迎交换。

戳这里，看该作者更多好文