倒排索引压缩实测:delta-varint 省 62% 体积,热点词位图让 AND 快 71 倍
倒排索引压缩实测:delta-varint 省 62% 体积,热点词位图让 AND 快 71 倍
搜索引擎的倒排表里,文档 ID 列表通常占索引体积的七成以上。压缩方式直接决定了三件事:索引能否全部驻留内存、冷启动要读多少字节、以及一次多词查询要付出多少解压开销。本文用一份可复现的合成语料,把最常用的三种表示放到同一张表上比较。
语料与三种表示
20 万篇文档、6 万词表、每篇 8 个词,词频服从 Zipf 分布(s=1.07),倒排项合计 160 万条。平均 df 28.4,中位 df 只有 4,最大 df 131424——典型的「长尾加少量超热点」结构。
三种表示:
- int32 定长数组,每个 docid 固定 4 字节;
- delta-varint,docid 递增,先做差分再用 LEB128 变长编码;
- 位图,第 d 位为 1 表示文档 d 命中该词。
编码核心只有几行:
def varint(n):
out = bytearray()
while True:
b = n & 0x7F
n >>= 7
out.append(b | 0x80 if n else b)
if not n:
return bytes(out)
体积:省 62%,代价是解码慢 7 倍
int32 占用 6.10 MB,delta-varint 只有 2.34 MB,压到 38.3%,省下 61.7%。原因很直接:中位 df 是 4,绝大多数列表的差分值都小于 128,一个字节就够,而 int32 恒定 4 字节。
代价在解码侧。对全部 5.6 万条倒排做一次完整解码:int32 用 struct.unpack 花 248 ms,varint 花 1810 ms,慢 7.3 倍。变长编码没有随机访问能力,必须从头逐字节推进,这是它省空间的直接对价。
查询:解压开销会吃掉压缩红利
取 200 组中频词(df 1000 到 20000)做 AND,平均列表长度合计 6033:
| 方式 | 单次耗时 | 说明 |
|---|---|---|
| 已解码列表 merge | 2020 us | 理想下限 |
| varint 解码 + merge | 3176 us | 比下限慢 57% |
| 位图 AND | 133 us | 不拿 docid |
| 位图 AND + 转列表 | 1865 us | 转列表吃掉 1732 us |
结论有点反直觉:压缩省下的字节并没有在中频词上换成时间。解压后再合并,比直接对已解码列表合并慢 57%;位图算得很快,但把位图展开成 docid 列表要 1732 us,优势立刻消失。
位图:只给 0.09% 的词用
位图最大的问题是按词分配。20 万篇文档,每个词一张 25 KB 位图,5.6 万个词就是 1344 MB,是 int32 的 220 倍,索引会直接离开内存。
但位图的 AND 是纯位运算。两个热点词(df 约 16000,合计 32377 条倒排)做 AND 只要 131 us,同样条件下 merge 需要 9339 us,快 71 倍;附加 bit_count 统计命中数 147 us,再取前 10 个 docid 430 us,仍有 21 倍优势。
阈值取 df 大于等于 N/64,本例即 3125。达标词只有 50 个,占词表 0.09%。把热点词换成位图、其余保留 varint 的混合编码,总体积 2.84 MB,仅比纯 varint 多 21.6%。
落地结论
- 长尾词用 delta-varint:体积优先,一次顺序解码就用完,不做随机访问;
- 热点词用位图:空间换位运算,AND 与 OR 直接落在整型按位操作上;
- 分层阈值用 df 大于等于 N/64 判断,实测只覆盖 0.09% 的词,体积代价 21.6%,换热点查询 20 到 70 倍提速;
- 不要给全部词建位图,220 倍膨胀没有任何压缩算法能救回来。
代码与数据:inv_bench.py 与 inv_bench2.py,Python 3.13.14 单机实测,语料由固定随机种子生成,结果可复现。
- 点赞
- 收藏
- 关注作者
评论(0)