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

这是词条规范化的两种重要方式，用于扩展检索范围。词干提取的主要思想是“缩减”，将词条转化为词干，如：将“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 中在进行主辅索引合并时会遇到比较大的储存开销，由于文档量较大，这意味着在进行合并操作时会涉及到大量倒排文件的读写操作，要想将该过程高效化，目前能处理该问题的文件系统极其稀少，所以该策略在生产环境中往往可用性并不高。

四、总结

在实际生产环境中，由于业务的繁杂，倒排索引的技术体系会比本文所阐述的技术点要复杂得多。本文主要讲解了倒排索引的作用、索引构建方法、用户行为分析以及索引的应用场景，从整体出发，向大家介绍现代倒排索引大致的技术体系，帮助大家了解倒排索引的概念，了解搜索引擎。可能本文阐述的技术点、架构体系会因为笔者个人的理解偏差而存在一些不足或欠缺丰富，如有疑问，欢迎交流。

作者：冯仁杰，达观数据搜索工程师

（编辑：ASP站长网）