什么是倒排索引Inverted Index

假设淘宝上有以下三个商品描述，我们将建立每个词对应的文档列表，如下表所示

商品 1：苹果手机新款发布，支持 5G 网络

商品 2：小米最新 5G 智能手机，性能卓越

商品 3：华为 5G 网络手机，实际 4G 功耗所以续航时间长

构建倒排索引

对每个商品的描述进行分词和处理后，构建如下的倒排索引

词汇	商品 ID 列表
苹果	1
手机	1, 2, 3
新款	1
发布	1
支持	1
5G	1, 2, 3
网络	1, 3
小米	2
最新	2
智能	2
性能	2
卓越	2
华为	3
实际	3
4G	3
功耗	3
续航	3
时间	3
长	3

用户实际搜索

当用户在淘宝搜索“5G 手机”时，搜索系统会进行以下操作：

分词：将“5G 手机”分解为“5G”和“手机”

查找索引：查询倒排索引，找到含有“5G”和“手机”的商品 ID

1. “5G”对应商品 1, 2
2. “手机”对应商品 1, 2, 3

合并结果：由于两个词的搜索结果相同，返回商品 1, 2

排序和展示：基于其他因素（如商品评分、销量等）对搜索结果进行排序，并展示给用户

存储和查找

存储：对于需要极高读取性能的应用，倒排索引可以存储在内存中的数据结构，如Redis或者是 map 这种数据结构也可以存储在分布式文件系统Hadoop，或者是搜索引擎专用的Elasticsearch

查找：内存数据库提供极快的数据访问速度，适用于实时搜索和高频访问场景

倒排索引的构建过程

1.文档预处理

去噪声：移除文档中的 HTML 标签、特殊符号、数字等无关内容

标准化：统一文档的格式，如将所有文字转换为小写，统一使用的日期和数字格式等

2.分词（Tokenization）

分词：中文文本的分词比英文复杂，因为中文没有明显的词与词之间的空格分隔因此，需要使用专门的中文分词工具来识别中文句子中的词汇，如结巴分词（jieba）、汉语言处理包（HanLP）等

词干提取（Stemming）：将词汇还原为基本形式（例如，“running”还原为“run”）

去停用词：中文的停用词（如“的”、“了”、“在”等）需要特别处理，因为这些词在中文中非常常见，但通常不携带重要信息

编码：确保处理和存储过程中使用统一的字符编码（如 UTF-8），这对于处理中文等多字节语言尤为重要，以防出现乱码问题

查询处理：在处理查询时，同样需要对查询文本进行分词处理，确保查询词与索引中的词能够正确匹配

3.构建倒排记录

创建倒排记录：对于每一个分词，创建一个记录，记录中包含该词出现的所有文档 ID 以及该词在每个文档中的位置

记录更新：随着新文档的添加，不断更新每个词的倒排记录

4.索引存储

索引格式化：将倒排索引以某种格式（如哈希表、B 树）存储在文件或数据库中

压缩：为了节省存储空间和提高查询效率，倒排索引通常会被压缩常用的压缩技术包括编码文档 ID 差值、使用位运算等

5.优化和维护

索引优化：定期优化索引结构，合并小索引文件，删除无用索引，以提高搜索效率

动态更新：支持索引的实时更新，以反映内容的变化

6.索引使用

查询处理：接收用户查询，解析查询词，通过倒排索引快速找到包含这些词的文档

排名算法：基于文档中词的频率、位置等因素对搜索结果进行排名

Go 实现简单倒排索引

package algorithm

type Doc struct {
	Id       int
	Keywords []string
}

func BuildInvertedIndex(docs []Doc) map[string][]int {
	index := make(map[string][]int)
	for _, doc := range docs {
		for _, keyword := range doc.Keywords {
			index[keyword] = append(index[keyword], doc.Id)
		}
	}
	return index
}