在互联网时代，有大量的信息，人们通过搜索引擎并“思考他们的想法”是正常的。那么搜索引擎如何有效地找到目标内容呢？本文主要介绍一个更重要的结构 - —搜索引擎中的倒排索引。

　　1 倒排索引简介

倒置索引（英文：Inverted Index）是一种常用于全文检索系统中的word文档映射结构的索引方法。

现代搜索引擎的大多数索引都是基于倒排索引构建的。这是因为在实际应用中，当用户使用搜索引擎查找信息时，他们通常只在信息中输入某些属性关键字，例如某些用户。如果您不记得歌曲名称，您将输入歌词以查找歌曲名称;输入程序内容剪辑以查找程序等。

面对大量的信息数据，为了满足用户的需求，适应信息时代快速信息获取的趋势，智能开发人员在搜索引擎的开发过程中反向计算这些信息数据，并制定了“关键词——文档的映射结构“表单”通过项目属性信息实现项目的映射，可以帮助用户快速定位目标信息，大大降低了信息获取的难度。索引也称逆向索引，是一种逆向思维操作，是现代信息检索领域最有效的索引结构。

　　2 倒排索引&FAQ

从用户请求到结果的返回，很多朋友都会对检索系统中倒排索引的工作过程感到好奇。在本节中，对倒排索引的一般性理解存在以下问题：

　Q1：何为索引？倒排索引又是什么？

索引是基于目标信息的内容预先创建的存储结构，以便加速信息搜索过程。例如：一本书，没有目录，理论上是可读的，但是当您关闭当前正在阅读的内容时，再次打开该书需要时间才能找到它。如果我们添加几页内容，我们可以快速了解本书的一般内容分布，以及每章页面位置的分布，这样我们的查询内容的效率自然会提高。该书的目录是该书内容的简单索引。

作为索引技术之一的倒索引是基于信息主体的关键属性值构建的。如图1所示：

图1倒排索引概念示例

假设检索系统中只有一个项目——服装A，在根据项目构造其倒排索引结构后，将生成上图右表中的索引结构，以便用户可以搜索“AAA”，“蓝色”，“ldquo; M代码”，&quoquo; “猴子”，可以找到产品，加快搜索速度，扩大搜索范围。

　Q2：当接受到用户查询请求时，倒排索引中发生了什么？

通常，当收到用户查询请求时，在输入反向索引进行检索时，在返回结果的过程中，主要有以下步骤：

步骤1：分析原始查询，如分词系统中的用户请求，生成相应的术语;步骤2：术语在倒排索引中的术语列表中查找相应术语的结果列表;步骤3：对结果列表数据执行微操作。如：计算文件的静态分数，文件相关性等; Step4：根据上述操作分数对文档进行全面排序，最后将结果返回给用户。

上述过程是一个相对简单的检索过程。实际上，在生产环境中，由于业务环境的复杂性，索引的设计模式变得复杂多样。在前面，主要通过概念图介绍倒排索引的体系结构。成熟的检索系统通常具有相对稳定的算法系统，用于处理生产环境中的每个细节技术要求。上述步骤涉及大量相关数据存储技术，搜索算法，排序算法，文本处理技术，甚至I/O技术。

　3 倒排索引技术剖析

构建倒排索引是搜索引擎中的关键步骤。从技术层面来看，构建倒排索引主要分为两部分：

Doc2term术语构建;

倒记录表的构造。

　3.1 term词项构造

期限建设是建立指数过程中不可或缺的一步。术语构造的质量通常直接影响用户的搜索体验和搜索结果的召回。的方法主要采用词系统的文档中的每个属性的文本信息分成一些词汇具有很强的和重要的意义，这是方便了用户找到，如示于下面图2：

图2术语构造的概念图

在术语构建过程中，使用分词系统处理文本往往涉及很多方面，不同语言有不同的处理机制。以下主要介绍处理文本所涉及的几个问题：

（1）文本词条化

一段文本信息，本身就是一系列语言。该技术要点的主要任务是将一段连续的文本序列信息分成多个子序列。它关系到语言本身，它处理文本的方法是在不同的语言往往不同。对于中国，由于它的模棱两可和表意功能，在实际应用中，有必要用NLP相关技术从内容，甚至是人工注释等，提取特征，生成相应的字典，然后使用基于分词词典。分词可以看到更好的文本输入效果。

对于英语，通用英语句子，段落内容，它会使用空格字符作为词之间的分隔符，因此在一般情况下，英文内容由空格字符分隔，可以取得更好的成绩，但英语也将有一些特殊的方式，如与撇号&MDASH格式;—“老师&rsquo的;办公室&rdquo ;,连字符格式——“讲英语和rdquo ;,也需要处理相应的单词提取出来。

　　（2）停用词过滤

停用词是出现在具有高频率和低值的文档列表中的单词。在英语中，例如，停止用英语文件，如多次出现的话：”的是”的，”的中”的&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&在频繁的出现在所有文件的情况下，如果这样的话编入索引的长期建设，多重全生成卷文档索引列表。停用词过滤的使用通常取决于实际使用场景。更频繁地使用关键字查询，例如电子商务品牌的垂直搜索引擎。合适的停用词列表尤为重要;对于网络搜索引擎如百度，谷歌等，这种类型的搜索引擎面向更多的查询场景，更加通用，往往不需要停止文字过滤。

　（3）词条归一化

基于以上两点，在将文档的内容转换为一个或多个术语之后，在查询中，最理想的情况是用户输入的关键字恰好与术语匹配。实际上，很多时候用户输入的查询和术语是用户通常不完全匹配，并且用户仍然希望查询与术语匹配。例如，当用户查询“颜色”时，用户肯定希望看到“颜色”的返回结果。术语标准化的任务是将一些看似不完整的术语划分为等同的类，例如英文单词颜色和美国单词颜色被分类为一类，空调和空调被分类为一类，等等。这样，当用户搜索等价类中的任何单词时，返回包含等价类中的任何单词的文档。

　（4）词干提取、词形还原

这是术语规范化的两种重要方式，用于扩展搜索范围。阻止的主要思想是“减少”以将单词转换成词干，例如：“将被视为”海滩   < ;; bananas”             作为“香蕉”等等;恢复的主要思想是“转换”，例如：转换“做”，“完成”，“做”等等。进入原型< do”，“给予”，“给予”进入原型“给予”等人;词干的实现一般是基于规则来减少术语的后缀，至于形式的恢复，实现方法需要字典来映射变形;基于术语归一化技术的组合它将对扩展的搜索范围产生一定的积极影响。

　　3.2 倒排记录表的构建

倒排记录表的构建过程针对大量文档数据。它在大小和大小上比术语集合大得多，并且不能完全存储在内存中并且需要写入磁盘。因此，在构建倒排记录表时需要考虑使用内存。

图3倒置索引概念图

在存储器不能完全存储的情况下，反转记录表的主要构造思想是“分割”，即基于某些处理逻辑对相等部分的全部文档集合进行批量处理。对于不同的业务需求，构建倒置记录的方法通常是不同的。基本构建方法如下：

S1:将文档集合转换为< ;; word 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中，当遇到主索引和辅助索引合并时，遇到大的存储开销。由于文档量很大，这意味着在合并操作期间读取和写入大量反转文件，并且要执行该过程。高效，可以处理此问题的文件系统极为罕见，因此该策略在生产环境中通常不太常用。

　4 总结

在实际生产环境中，由于业务的复杂性，倒排索引的技术系统比本文所述的技术要点复杂得多。本文主要阐述了倒排索引，索引构造方法，用户行为分析和索引应用场景的作用。从整体上讲，我们介绍了现代倒排索引的一般技术系统，以帮助您理解倒排索引的概念并理解搜索。发动机。由于作者的个人理解偏差，本文中描述的技术要点和架构系统可能存在一些缺陷或缺乏丰富性。如有疑问，欢迎交流。

作者：李仁杰，哲学数据搜索工程师

« Facebook如何获得20亿用户？答案是“科学”和“同情” | 网络安全不容忽视，百度搜索安全讲座干货全部秘密！ »