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

这是词条规范化的两种重要方式，用于扩展检索范围。词干提取的主要思想是“缩减”，将词条转化为词干，如：将“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 分布式构建

（编辑：惠州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!