倒排索引中 “term” 词项 为什么要转换成 id

当我们提到 存储压缩 时，尤其是在处理 倒排索引（Inverted Index）时，主要的目标是减少存储空间和提高查询效率。通过将 词项映射到ID 和 使用位图代替传统的倒排列表，我们能有效减少存储空间的占用，尤其是在处理具有大量重复词项的数据时。下面我将详细解释 词项映射到ID 的收益，并通过具体例子来说明。

1. 词项映射到ID的概念

在传统的倒排索引中，我们通常会维护一个 倒排列表，其中每个词项都会有一个相应的列表，列出所有包含该词项的文档ID。例如，如果我们有以下三个文档：

• 文档 0: “apple banana”

• 文档 1: “apple grape”

• 文档 2: “banana grape”

传统的倒排索引可能是这样的：

词项 倒排列表

apple [0, 1]

banana [0, 2]

grape [1, 2]

这样的索引占用了一些存储空间，因为每个词项的倒排列表都是由文档ID组成的。假设有上千个文档，并且每个文档有大量相同的词项（如 “apple”、“banana”），那么每个倒排列表中会包含大量重复的信息。

存储收益分析：

• 假设文档数量很大，例如 10,000 个文档。对于每个词项，存储它的倒排列表时，可能需要存储上千个文档ID。例如，对于频繁出现的词项 apple，我们需要为它存储一个非常大的列表。

• 映射到ID 是一种压缩策略，通过为每个词项分配一个唯一的整数ID，代替在索引中存储整个词项的文本，这样可以大大节省存储空间。

2. 通过映射到ID实现压缩

映射的过程是将文本中的 词项 转换为一个 唯一的整数ID，例如：

词项 映射ID

apple 0

banana 1

grape 2

这样，当我们进行倒排索引时，就不需要再存储完整的词项文本，而是直接使用词项的ID。

优势：

• 节省存储空间：词项本身可能是长字符串（例如 "apple"），而 ID 只是一个简单的整数（例如 0），整数占用的存储空间要远小于字符串。例如，假设一个词项 apple 的字符串长度为 5 个字节，而对应的ID可能只占用 4 个字节（通常是一个整数）。

• 压缩效果：如果你的文档包含大量重复的词项（如许多文档中都包含 "apple" 这个词），通过将 "apple" 映射为 0，我们不再需要多次存储 "apple" 这个字符串，而是只需要存储一个 ID。

举例说明：

假设有以下 3 个文档和倒排索引：

• 文档 0: “apple banana”

• 文档 1: “apple grape”

• 文档 2: “banana grape”

传统倒排索引（字符串存储）：

词项 倒排列表

apple [0, 1]

banana [0, 2]

grape [1, 2]

这里，我们存储了词项的字符串和倒排列表。假设每个字符串 "apple", "banana", "grape" 的长度分别为 5、6 和 5 字节（即每个词项需要 5-6 字节来存储）。假设有 100,000 个文档，并且每个词项重复多次。

映射到ID后的倒排索引：

词项 ID 倒排列表

apple 0 [0, 1]

banana 1 [0, 2]

grape 2 [1, 2]

通过映射到ID，词项 apple 不再需要存储为字符串 "apple"，而是使用整数 ID 0 来表示。这样，对于每个文档的倒排列表，存储的内容从字符串变成了数字，从而减少了存储空间的占用。整数通常占用 4 字节，而字符串的长度可能会根据词项的实际长度变化，显然整数的存储占用更小。

3. 映射ID的存储压缩收益

假设：

• 字符串存储：每个词项存储需要 6 字节（如 "apple"、"banana" 等），那么一个文档的倒排列表需要存储多个字符串，这会占用较多空间。

• ID存储：将每个词项映射为 ID，ID 只占用 4 字节。例如，对于 "apple"，它的 ID 是 0，只需要 4 字节。

示例：

假设有 10,000 个文档，并且 apple 出现了 5,000 次。如果我们使用 字符串存储，那么 apple 的倒排列表需要存储 5,000 个 "apple" 字符串，总共需要：

• 5,000 * 6 字节 = 30,000 字节

而如果我们使用 ID存储，那么 apple 的倒排列表只需要存储 5,000 个 ID，每个 ID 占用 4 字节，总共需要：

• 5,000 * 4 字节 = 20,000 字节

这样，通过将词项映射到 ID，我们就节省了 10,000 字节的空间。

4. 复杂场景下的收益

如果文档中的词项非常多（例如有 1,000,000 个文档，并且每个文档都包含大量相同的词项），则映射到 ID 的压缩效果将更加显著：

• 假设文档中包含非常常见的词项（例如 apple、banana），并且这些词项在多个文档中重复出现。如果不做映射，每个重复出现的词项都会占用相同的存储空间。

• 而通过映射，所有重复的词项只需要存储它们的 ID，这就大大减少了存储空间。

总结

通过将 词项映射到ID，我们实现了 存储压缩。这种压缩方式通过减少存储的内容（从字符串转为整数ID）来节省存储空间，特别是在处理文档中频繁出现相同词项的情况时，效果更为显著。存储空间的节省和查询效率的提高是这种方法的主要收益。