互联网时代，信息量巨大，人们通过搜索引擎直接获取“所想”是常态。那么搜索引擎如何高效地找到目标内容呢？本文主要介绍搜索引擎中一个比较重要的结构——倒排索引。1倒排索引简介倒排索引（英文：InvertedIndex）是全文检索系统中常用作词-文档映射结构的一种索引方法。大多数现代搜索引擎的索引都是基于倒排索引构建的。这是由于在实际应用中，用户使用搜索引擎查找信息时，往往只输入信息中的某个属性关键词。比如有的用户不记得歌名，就会输入歌词找歌名；输入节目的一段内容来查找节目，等等。面对海量的信息数据，为了满足用户的需求，顺应信息时代信息快速获取的趋势，聪明的开发者在开发搜索引擎时对这些信息数据进行逆向计算，开发出“关键词-文档”的形式一种映射结构，通过物品属性信息实现物品之间的映射，可以帮助用户快速定位目标信息，大大降低了信息获取的难度。倒排索引，又称倒排索引，是一种逆向思维运算，是现代信息检索领域最有效的索引结构。（大观数据冯仁杰）2倒排索引&FAQ从用户请求到结果返回，很多朋友都会好奇倒排索引在检索系统中的工作过程。本节讨论一些对倒排索引的一般理解，有以下问题：Q1什么是索引？什么是倒排索引？索引是为了加快信息搜索过程，根据目标信息内容预先创建的存储结构。例如：一本没有目录的书，理论上是可以读的，但是当你关闭当前正在阅读的内容时，下次再打开这本书进行搜索就需要更多的时间。如果我们增加目录的几页，我们就可以很快的了解这本书的大致内容分布，以及每一章的页位分布，这样我们查询内容的效率自然会提高。图书目录是图书内容的简单索引。倒排索引是一种索引技术，它是根据信息主体的关键属性值构建的。如图1所示：图1倒排索引概念示例图假设检索系统中只有一个item——衣服A，根据这个item构建倒排索引结构后，上右表中的索引结构会生成，让用户通过搜索“AAA”、“蓝色”、“M码”、“猴子”，就可以找到商品，加快了搜索速度，扩大了搜索范围。Q2当收到用户查询请求时，倒排索引会发生什么？通常，当收到用户查询请求，进入倒排索引进行检索时，返回结果的过程主要有以下几个步骤：Step1：在分词系统中对用户请求等原始查询进行分析，生成相应的词条;Step2：terms在倒排索引的term列表中查找对应term的结果列表；Step3：对结果列表数据进行微操作，如：计算文档静态分数、文档相关性等；Step4：根据上述计算分值对文档进行综合排序，最后将结果返回给用户；上述过程是一个比较简单的检索过程。事实上，在生产环境中，由于业务环境的复杂性，索引的设计模式会变得复杂和繁多。上一篇文章主要通过概念图介绍了倒排索引的架构体系。一个成熟的检索系统往往有一个相对稳定的算法体系来处理生产环境中的每一个细节技术需求。以上步骤涉及到大量相关的数据存储技术、搜索算法、排序算法、文本处理技术，甚至I/O技术。3倒排索引技术分析建立倒排索引是搜索引擎中至关重要的一步。从技术角度来看，倒排索引的构建主要分为两部分：1）Doc2term术语构建；2)行记录表的逆向构造。（大观数据冯仁杰）3.1术语构建术语构建是索引构建过程中不可或缺的一步。词条构造的好坏往往直接影响用户的搜索体验和搜索结果的召回率。这个过程主要是利用分词系统将文档中各个属性的文本信息拆分成一些强而重要的词，方便用户搜索，如下图2所示：图2术语构造概念图termconstruction的过程在中，使用分词系统处理文本往往涉及到很多方面，针对不同的语言，会有不同的处理机制。下面主要介绍处理文本涉及到的几个问题：(1)文本输入一段文本信息，它本身就是一个由语言组成的字符串系列。该技术点的主要任务是将一段连续的文本序列信息拆分成多个子序列。这与语言本身有关。面对不同的语言，处理文本的方式往往是不同的。对于中文，由于其表意文字的多义性和紧凑性特点，在实际应用中，一般需要使用NLP相关技术从内容中提取特征，甚至人工标注内容生成对应的字典，然后使用分词器基于字典。分词，为了看到更好的文字录入效果。对于英文，常见的英文句子和段落内容，它会使用空格作为单词之间的分隔符，所以一般情况下，用空格分割英文内容已经可以达到较好的效果，但是英文中也会有一些特殊的模式，比如带有空格的格式撇号-“Teacher'soffice”，连字符的格式-“English-speaking”，也需要进行相应处理以提取单词。（大观数据冯仁杰）（2）停用词过滤停用词是指文档列表中出现频率高，价值不大的词。以英文为例，英文文档中频繁出现的停用词如：“is”、“the”、“I”、“and”、“me”等；这样的词经常出现在所有文档中，如果用这样的词作为词条进行索引构建，会生成多个全文索引列表。停用词过滤的使用往往取决于实际的使用场景。对于频繁使用关键词查询的场景，比如某电商品牌的垂直搜索引擎，合适的停用词列表尤为重要；对于网页搜索引擎，如百度、谷歌等，这类搜索引擎面向更多的查询场景，通用性强，往往不需要停用词过滤。(3)条目归一化是基于以上两点。将文档内容转化为一个或多个term后，理想的情况是用户输入的关键字与查询时的term完全匹配。事实上，很多时候用户输入的query往往与词条不完全匹配，但用户还是希望query能够与词条匹配。例如，当用户查询“颜色”时，用户一定也想看到“颜色”的返回值。结果。词条归一化的任务是将一些看起来不完全一致的词条划分为一个等价类，比如英国词color和美国词color归为一类，Air-conditioner和airconditioner归为一类等；这样，当用户搜索等价类中的任意词时，将返回包含等价类中任意词的文档。(4)词干抽取和词条还原是词条标准化的两种重要方式，用于扩大检索范围。词干提取的主要思路是“归约”，将词条转化为词干，如：将“beaches”处理成“beach”，将“bananas”处理成“banana”等；词形还原的主要思想是“转换”，例如：将“doing”、“done”、“did”转换为原型“do”，将“given”、“gave”转换为原型“give”等.;词干抽取的实现方法一般是根据规则来减少词条的后缀，至于形式的还原，实现方法需要一个字典来映射形式的变化；基于这种词条归一化技术的结合，对于扩大检索范围将有一定的积极作用。3.2发帖列表的构建发帖列表的构建过程面向海量的文档数据集，其规模和规模远大于术语集，无法完全存储在内存中，需要写入磁盘。因此，我们在构建postingslist时有必要考虑内存占用。图3倒排索引概念图在没有全量内存的情况下，倒排记录表的主要构建思路是“切分”，即按照一定的处理逻辑，对全文档集合的等份进行批量处理。针对不同的业务需求，张贴列表的构建方法往往不同。基本构造方法如下：S1：将文档集合经过一系列处理，转化为“termID-documentID”对；S2：对词条ID和文档ID进行排序，将词条对相同的文档ID合并到该词条对应的发帖列表中，效果如图3；S3：将上述步骤生成的倒排索引写入磁盘生成中间文件；S4：将上述所有中间文件合并到最终的倒排索引Indexing中；从业务应用场景来看，发帖记录的构建方式主要有：单遍扫描和多遍扫描；从工程的角度来看，postingrecords的构建方式主要有：分布式构建和动态构建；3.2.1Single-passscan构建顾名思义，single-passscan是指只遍历一次文档集合，完成倒排索引的构建。由于内存开销的问题，会把全文档集分成若干个内存大小相同的文档集，然后依次执行上面提到的构造方法。该方法可以快速构建简单可行的倒排索引，帮助用户通过关键词匹配快速找到目标文档。3.2.2Multi-passscanningMulti-passscanning主要用于在建立索引时获取文档更多的相关信息，比如一些termTF-IDF指标、词频、文档内容关系等，丰富索引的内容贴子表，为搜索引擎扩充功能；在工业流水线上，由于查询类型不够丰富，单遍扫描建立索引显然无法满足广大用户的需求。搜索用户的需求不局限于关键字查询，如词组查询、模糊查询、精确过滤、模糊过滤、排序、聚合统计等。这意味着我们在构建搜索引擎时应该从文档中获取尽可能多的信息倒排列表，方便查询时的微操作、重排序、关联分析等技术需求。3.2.3分布式构建对于一些大型搜索引擎如Web搜索引擎，单机已经不能支持其索引构建，需要多台机器组成一个集群进行分布式处理，将构建的倒排索引进行划分和分散式。在多台机器上，每台机器形成一个独立的索引结构。当一个用户发出请求时，多台机器都会响应，并根据用户的搜索需要在各自的索引结构中进行查询，返回相关结果，然后所有的结果在内存中集中处理，***返回处理后的结果***结果给用户。在具体实现过程中，工程师往往更喜欢一些通用的分布式架构用于大规模机器计算，比如Hadoop中的MapReduce、Java中的Fork/join架构等，大大提高了软件开发的效率。（大观数据，冯仁杰）3.2.4动态构建该方法中的文档集合是变化的，需要在对文档集合进行索引时自适应更新文档。这个问题在电商领域比较常见，比如产品的下架和下架，产品内容的更新等，都会引起动态索引更新的问题。在这里，我们经常采用一些策略性的方法来解决这类问题，提高索引的实时性。常用策略如下：1)定期对文档进行全量重新索引；2）在有主索引的前提下，建立辅助索引，用于存储新的文档，并在内存中维护。当辅助索引达到一定的内存占用时写入磁盘，与主索引合并；策略1是最简单、直接、有效的索引更新策略，对于数量级大的搜索引擎简单方便。由于动态索引计算的复杂性，使用其他策略会使索引难以维护，甚至会导致严重的性能问题。因此，大型搜索引擎往往更倾向于定期重建索引，但这会涉及到索引热切换的问题。大量的文档往往会产生连续的文档更新，这会对索引热切换造成一定的困难。如果不好，会导致数据丢失，用户找不到新文档等问题。策略二在合并主二级索引时会有比较大的存储开销。由于文件量很大，这就意味着合并操作中会涉及到大量的倒排文件的读写操作。为了使流程高效，目前能够处理这个问题的文件系统已经非常成熟，所以这种策略在生产环境中的可用性往往不高。4小结在实际生产环境中，由于业务的复杂性，倒排索引的技术体系会比本文介绍的技术要点复杂很多。本文主要讲解倒排索引的作用、索引构建方法、用户行为分析和索引应用场景。从整体出发，介绍了现代倒排索引的一般技术体系，帮助您理解倒排索引和搜索引擎的概念。或许本文所描述的技术要点和架构体系由于笔者个人的理解偏差，可能存在一些不足或不够丰富的地方。如有任何问题，欢迎交流。【本文为专栏作者“大观数据”原创稿件，如需转载可通过专栏取得联系】点此查看该作者更多好文
