倒排索引压缩与潜在语义索引：信息检索的高效策略

### 倒排索引压缩与潜在语义索引：信息检索的高效策略 在信息检索领域，为了提升搜索效率和减少存储空间的占用，倒排索引压缩和潜在语义索引是两种非常重要的技术。下面将详细介绍这两种技术的原理、方法和应用。 #### 倒排索引压缩 倒排索引通常非常庞大，为了加快搜索速度，应尽可能将其存于内存以避免磁盘 I/O。因此，减小索引大小成为关键问题，而索引压缩就是一种自然的解决方案，它旨在用更少的比特或字节来表示相同的信息。无损压缩方法能够精确还原原始索引，是本文讨论的重点。 倒排索引主要用于存储文档 ID 和每个词项的偏移量，由于这些信息都由正整数表示，所以这里主要讨论整数压缩技术。 在未压缩的情况下，大多数架构中整数采用固定的 4 字节（32 位）表示，但实际上很少有整数需要这么多字节，因此存在更紧凑的表示方式（压缩）。倒排列表的压缩方案通常分为可变比特方案和可变字节方案。 可变比特方案中，整数用整数个比特表示，常见的方法有一元编码、Elias gamma 编码、Elias delta 编码和 Golomb 编码。可变字节方案中，整数用整数个字节存储，每个字节 8 位，简单的字节方案是可变字节编码。这些编码方案将整数映射到自定界的二进制码字，无需额外的分隔符或标记就能检测每个整数的起始和结束位。 倒排索引还有一个有趣的特性，能让压缩更有效。由于每个倒排列表中的文档 ID 按升序排列，我们可以存储相邻文档 ID 之间的差值（即间隙），而不是实际的 ID。这样间隙通常比文档 ID 小，所需的比特数也更少。在搜索时，如果算法线性遍历每个倒排列表，就能轻松恢复文档 ID。同样，每个记录中的偏移量也是有序的，也可以采用类似的存储方式。 例如，排序后的文档 ID 为 4、10、300 和 305，它们可以用间隙 4、6、290 和 5 表示。给定间隙列表，很容易恢复原始的文档 ID。对于频繁出现的词项，间隙通常较小，可以用短码（更少的比特）编码；对于不常见或罕见的词项，虽然间隙可能较大，但由于包含这些词项的文档数量较少，所以占用的空间也不多。存储间隙可以显著减小索引大小。 下面详细介绍各种编码方案，每种方案都包括编码（压缩）和解码（解压缩）方法。 ##### 一元编码 一元编码很简单，它用 x - 1 个零比特后跟一个一比特来表示数字 x。例如，5 表示为 00001，其中一比特就是分隔符。解码也很直接。这种方案对非常小的数字有效，但对大数字很浪费，因此在实际中很少单独使用。 | 十进制 | 一元编码 | | ---- | ---- | | 1 | 1 | | 2 | 01 | | 3 | 001 | | 4 | 0001 | | 5 | 00001 | | 6 | 000001 | | 7 | 0000001 | | 8 | 00000001 | | 9 | 000000001 | | 10 | 0000000001 | ##### Elias gamma 编码 编码步骤如下： 1. 将 x 转换为二进制。 2. 从步骤 1 中二进制的位数减 1，然后在前面添加相应数量的零。 例如，数字 9 的二进制是 1001，有 4 位，1 + ⌈log₂9⌉ = 4，一元表示为 0001，去掉最高位后 9 的二进制是 001，所以 9 用 Elias gamma 编码表示为 0001001。 解码步骤如下： 1. 从数据流中读取并计数零，直到遇到第一个一，记零的数量为 K。 2. 将遇到的一作为整数的第一位，值为 2ᴷ，读取接下来的 K 位。 例如，要解压缩 0001001，先读取零，得到 K = 3，然后将 1 与接下来的 3 位组合，得到 1001（二进制的 9）。 Elias gamma 编码对小整数有效，但不适合大整数，对于大整数，参数化的 Golomb 码或 Elias delta 码更合适。 ##### Elias delta 编码 编码时，正整数 x 用 1 + ⌈log₂x⌉ 的 gamma 码表示，后跟 x 去掉最高位的二进制表示。 例如，对于数字 9，1 + ⌈log₂9⌉ = 4，4 的 gamma 码是 00100，9 去掉最高位的二进制是 001，所以 9 的 delta 码是 00100001。 解码步骤如下： 1. 从数据流中读取并计数零，直到遇到第一个一，记零的数量为 L。 2. 将遇到的一作为整数的第一位，值为 2ᴸ，读取接下来的 L 位，得到整数 M。 3. 在最终输出的首位放一个一，代表值 2ᴹ，读取并追加接下来的 M - 1 位。 例如，要解码 00100001，第一步得到 L = 2，第二步读取 5 位得到 M = 4（二进制 100），最后在 001 前加 1 得到 1001（二进制的 9）。 虽然 Elias 编码能实现可接受的压缩和解码速度，但 Golomb 编码在这两方面能有更好的表现。 ##### Golomb 编码 Golomb 编码是一种参数化编码，要编码的整数相对于一个常数 b 存储。这里介绍一种版本。 编码时，正整数 x 分为两部分表示： 1. 第一部分是 q + 1 的一元表示，其中 q 是 ⌊(x / b)⌋ 的商。 2. 第二部分是余数 r = x - qb 的特殊二进制表示，有 b 种可能的余数。 余数的二进制表示需要 ⌊log₂b⌋ 或 ⌈log₂b⌉ 位。为了节省空间，前几个余数用 ⌊log₂b⌋ 位表示，其余的用 ⌈log₂b⌉ 位表示。设 i = ⌊log₂b⌋，前 d 个余数用 i 位编码，d = 2ⁱ⁺¹ - b。 例如，当 b = 3 时，要编码 x = 9，商 q = ⌊9 / 3⌋ = 3，i = ⌊log₂3⌋ = 1，d = 1。可能的余数 0、1、2 分别编码为 0、10、11，9 的余数 r = 9 - 3×3 = 0，所以 9 的最终编码为 00010。 解码步骤如下： 1. 解码一元编码的商 q（消耗相关比特）。 2. 计算 i = ⌊log₂b⌋ 和 d = 2ⁱ⁺¹ - b。 3. 读取接下来的 i 位并赋值给 r。 4. 如果 r ≥ d，则读取一位并追加到 r 的末尾，然后 r = r - d。 5. 返回 x = qb + r。 例如，要解码 11111（b = 10），首先 q = 0，消耗第一位。然后 i = ⌊log₂10⌋ = 3，d = 6。读取接下来的三位 111（十进制 7）赋值给 r，因为 7 > 6，读取一位 1，r 变为 1111（十进制 15），新的 r = 15 - 6 = 9，最后 x = 0×10 + 9 = 9。 对于