4. 变长编码（VByte）：原理、算法与倒排列表应用

VByte（Variable Byte）是倒排索引压缩中最经典的变长编码之一。它用每个字节的最高位（continuation bit）标记当前字节是否为某个整数的最后一个字节，从而用 1~5 个字节表示任意 32 位无符号整数。VByte 在解压速度上远优于位对齐编码（如 Golomb、Rice），且压缩比适中，是搜索引擎中“以速度换空间”的常用方案。

4.1 VByte 编码原理

VByte 将每个整数拆分为若干 7 位有效数据块，每个数据块存入一个字节的低 7 位，字节的最高位作为“延续位”：

• 延续位 = 1：当前字节是整数的最后一个字节。
• 延续位 = 0：后面还有后续字节。

编码时从整数的低位开始，每次取 7 位，直到所有位处理完毕。最后一个字节的延续位置 1，其余字节的延续位置 0。解码时依次读取字节，检查延续位，若为 0 则继续读取，若为 1 则拼接出完整整数。

4.2 编码与解码算法步骤

4.2.1 编码算法

1. 输入：32 位无符号整数 n。
2. 循环：当 n >= 128 时，取 n 的低 7 位，与 0x80 按位或（延续位=0），存入输出缓冲区；n >>= 7。
3. 最后字节：将剩余的 n 与 0x80 按位或（延续位=1），存入输出缓冲区。
4. 输出：字节序列，长度 1~5 字节。

// C 风格 VByte 编码
void vbyte_encode(uint32_t n, uint8_t* &out) {
    while (n >= 128) {
        *out++ = (n & 0x7F) | 0x80;  // 延续位=0
        n >>= 7;
    }
    *out++ = n | 0x80;  // 延续位=1
}

4.2.2 解码算法

1. 输入：VByte 编码的字节流。
2. 循环：读取一个字节 b，取低 7 位拼接到结果 val 的高位；若 b & 0x80 == 0，继续读取下一个字节；若 b & 0x80 != 0，解码结束。
3. 输出：还原的 32 位整数 val。

// C 风格 VByte 解码
uint32_t vbyte_decode(const uint8_t* &in) {
    uint32_t val = 0;
    int shift = 0;
    uint8_t b;
    do {
        b = *in++;
        val |= (uint32_t)(b & 0x7F) << shift;
        shift += 7;
    } while ((b & 0x80) == 0);
    return val;
}

4.3 VByte 在倒排列表中的应用

倒排列表存储的是文档 ID 序列和词频（TF）序列。直接存储原始 ID 会导致大量冗余，因此搜索引擎通常先对文档 ID 进行 差值（d-gap）转换，再对差值序列进行 VByte 编码。

词频（TF）通常与文档 ID 交替存储或使用独立流。由于词频值一般较小（多数为 1~10），VByte 编码后大多只需 1 个字节，压缩效率极高。

4.4 VByte 的优缺点与适用场景