048|搜索索引及其相关技术概述
2017-12-22洪亮劼来自北京
《AI技术内参》
本周我们分享的主题是从宏观上来剖析现代搜索架构。周一我介绍了搜索系统的一个大的分
类，一类是从20世纪50年代开始研发并使用的传统文本匹配信息检索系统，一类是从2000
年开始发展并逐渐成熟的机器学习信息检索系统。周三我们剖析了搜索系统的另一个框架体
系，多轮打分系统，阐述了为什么需要多轮打分，以及每一轮打分又有什么特性。
今天，我们来看一个在本周已经反复涉及到的话题：倒排索引（InvertedIndex）。一起来聊
聊它的核心技术。值得注意的是，关于索引的很多话题其实都会牵涉到搜索中的“查询关键字
处理”（QueryProcessing），我们今天的分享就主要来谈谈索引及相关技术在“查询关键
字处理”这个场景下的应用。
经典的索引结构
经典的索引结构由“字段”（Field）和对应的列表组成。一般来说，“字段”就是某一个查
询关键字。在英文里，这就是一个单独的单词；在中文里，这也许就是一个词或者短语。每个
字段所对应的列表就是包含这个查询关键字的文档列表。
有两点值得注意。
第一，在文档列表里的文档，大多按照某种重要的顺序排列，这方便我们首先提取重要性高的
文档。比如，某个文档整体和查询关键字的相关度大，那么就会排列到这个列表的前面。
第二，对于每个字段，也就是查询关键字而言，所有包含这个查询关键字的文档并不一定都会
包含到这个列表中，这个列表可以是一个节选。
另外，我们前面已经讲过了，之所以叫做“索引”，也是因为这个列表中并不实际存储整个文
档，往往是只存储文档的编号。
如果用户输入的查询关键字包含多个词组，根据这个最基础的结构，我们可以很容易地获取包
含所有关键字的文档集合。这个操作仅仅相当于在多个列表中做“归并排序”（Merge
Sort）。
除了在索引中仅仅保存最基本的文档标号信息以外，另外一些文档的基础信息也可以一并存放
在索引中。比如，经常存放的信息还有文档包含某个查询关键字的次数。保存次数信息本质上
是在保存“词频”（TermFrequency）这个文档特性。
我们前面分享经典的信息检索模型的时候，介绍过很多模型，例如TF-IDF、BM25或者语言
模型，都对词频的计算有很强的依赖。在索引中存放词频信息有助于近似计算这些基础的检索
模型。
另外一个经常存放的信息就是查询关键字在文档中出现的位置（Position）。位置信息对于有
多个查询关键字的时候尤为重要。比如，我们要搜索的词组是“五道口电影院”。在这样的情
况下，我们非常希望“五道口”在某个文档中出现的位置和“电影院”在文档中出现的位置相
邻。这样，我们可以确认这个文档的确是关于“五道口电影院”的，而不是恰好含有“五道
口”和“电影院”这两个词。
同时，位置信息还可以帮助搜索引擎生成搜索结果界面上的“结果摘要”信息。我们经常看到
搜索结果页面上有几句话的摘要信息，这个信息就需要查询关键字的位置来生成。
索引技术
除了最基础的索引技术以外，研发人员开发了多种技术让索引更加高效。
第一个技术当然就是希望对索引进行压缩。索引信息很快就会随着可能的关键字数目的膨胀而
扩展。索引中每一个关键字所对应的文档列表也会越来越庞大。因此，能否快速处理索引信息
并为后续的计算节约时间就变得非常关键。本周三我们分享了多轮打分系统。多轮打分系统的
的一个重要思想就是整个流程必须在几百毫秒的响应时间内完成。因此，每一个步骤，包括从
索引中提取“顶部K个文档”的过程都需要很快捷。
压缩技术博大精深，我们在今天的分享中就不展开讨论这部分的内容了。在这里，我们只需要
从高维度上把握这个问题的一个基本思路。索引的一个基本信息就是相对于某个查询关键字的
文档列表。而存储在文档列表里的并不是文档本身的数据，而是文档的某种信息，比如文档本
身的编号。而编号就是数字，文档列表最终就是一个数字序列。压缩技术中有很多算法就是对
一个数字序列进行压缩。
那么，到底怎样才能起到压缩的作用呢？我们这里举一个例子。比方说，有一种压缩算法是基
于一种叫“差值编码”（DeltaEncoding）的技术。简单来说，就是不直接记录文档编号本
身，而是按照文档编号的顺序，记录文档编号之间的差值。
对于某些非常频繁的查询关键字而言，这些词汇有可能会出现在非常多、甚至是绝大多数的文
档中。而采用这种“差值编码”来对文档列表进行重新编排，我们就可以用一组很小的数（这
些数表达两个相邻文档编号的差值）来代表文档列表。当然，这种方法对于文档很少的查询关
键字效果肯定不明显。同时，这种技术也