倒排索引Posting List压缩实践：Gamma编码存储与空间优化疑问

1. 先把DocID转成间隙值（Delta） #

Posting List本身是按DocID有序排列的，直接计算间隙值：第一个元素保留，后续每个元素减去前一个元素。比如[1,4,7,19,20,25]转成[1,3,3,12,1,5]，用循环就能搞定，没有复杂逻辑。

2. 实现Gamma编码（把间隙值转成二进制压缩串） #

Gamma编码对小整数压缩效率极高，规则很简单：

• 对正整数x，先算它的二进制位数k（比如x=3是11，k=2；x=12是1100，k=4）
• 先写k-1个0，再写x的二进制串

Python实现代码：

def gamma_encode(x):
    if x <= 0:
        raise ValueError("Gamma编码仅支持正整数")
    k = x.bit_length()
    prefix = '0' * (k - 1)
    suffix = bin(x)[2:]  # 去掉二进制前缀'0b'
    return prefix + suffix

把所有间隙值的Gamma编码串拼接成一个长二进制字符串，比如示例中的间隙值拼接后是10110110001100100101。

3. 二进制串转字节流存储（替代pickle的核心） #

pickle会存储大量对象元数据，空间浪费严重。我们直接把压缩后的二进制串转成字节流写入文件：

• 把长二进制串补成8的倍数（1字节=8位），末尾补0即可
• 每8位二进制转成一个字节，最终得到字节流

代码示例：

def binary_to_bytes(bin_str):
    # 补0到8的倍数
    padding = (8 - len(bin_str) % 8) % 8
    bin_str += '0' * padding
    # 按8位分割转字节
    byte_list = [int(bin_str[i:i+8], 2) for i in range(0, len(bin_str), 8)]
    return bytes(byte_list)

# 假设已得到拼接好的Gamma二进制串gamma_bin
gamma_bin = '10110110001100100101'
byte_stream = binary_to_bytes(gamma_bin)
# 写入文件
with open('postings.bin', 'wb') as f:
    f.write(byte_stream)

4. 词典的紧凑存储（关联词与Posting List） #

原来的{词: Posting List}字典要改成{词: (偏移量, 字节长度, padding)}：

• 偏移量：该词的Posting List压缩字节流在postings.bin中的起始位置
• 字节长度：压缩后字节流的长度
• padding：补的0的个数（解码时要去掉）

词典用JSON存储比pickle紧凑得多：

index_dict = {
    "apple": (0, 5, 3),  # 起始0字节，读5字节，补了3个0
    "banana": (5, 7, 1)
}
import json
with open('dict.json', 'w') as f:
    json.dump(index_dict, f)

5. 解码还原Posting List #

查询时按以下步骤操作：

1. 从dict.json读取目标词的偏移、长度、padding
2. 从postings.bin中seek到偏移位置，读取对应长度的字节流
3. 把字节流转回二进制字符串，去掉末尾补的0
4. 按Gamma编码规则解码出间隙值，再累加还原成原始DocID

解码代码示例：

def bytes_to_binary(byte_stream):
    return ''.join([bin(b)[2:].zfill(8) for b in byte_stream])

def gamma_decode(bin_str):
    ptr = 0
    gaps = []
    while ptr < len(bin_str):
        # 统计前缀0的数量，得到k-1
        k_minus_1 = 0
        while ptr < len(bin_str) and bin_str[ptr] == '0':
            k_minus_1 += 1
            ptr += 1
        if ptr >= len(bin_str):
            break
        # 读取k位二进制
        k = k_minus_1 + 1
        if ptr + k > len(bin_str):
            break
        suffix = bin_str[ptr:ptr+k]
        ptr += k
        gaps.append(int(suffix, 2))
    # 还原DocID
    doc_ids = []
    current = 0
    for gap in gaps:
        current += gap
        doc_ids.append(current)
    return doc_ids

# 读取示例
with open('dict.json', 'r') as f:
    idx_dict = json.load(f)
offset, length, padding = idx_dict["apple"]

with open('postings.bin', 'rb') as f:
    f.seek(offset)
    byte_stream = f.read(length)

bin_str = bytes_to_binary(byte_stream)
# 去掉补的0
bin_str = bin_str[:-padding]
doc_ids = gamma_decode(bin_str)
print(doc_ids)  # 输出[1,4,7,19,20,25]

额外优化建议 #

• 工业界更常用可变字节编码（VB编码），比Gamma编码实现更简单，对大整数的压缩效果也更好
• 词典可以用前缀树（Trie）或跳表存储，进一步压缩词典空间
• 多个Posting List的压缩字节流可以存在同一个文件，用词典记录偏移，减少文件IO开销

内容的提问来源于stack exchange，提问作者carlo97