倒排索引压缩实测:delta-varint 省 62% 体积,热点词位图让 AND 快 71 倍

举报
yd_243452805 发表于 2026/11/18 09:53:41 2026/11/18
【摘要】 用 20 万篇文档、6 万词表的合成语料实测倒排表三种表示:int32、delta-varint、位图。delta-varint 把体积压到 38.3%,但全量解码慢 7.3 倍;位图若按词全量分配会膨胀 220 倍,只对 df≥N/64 的热点词启用后总体积仅涨 21.6%,两个热点词做 AND 从 9.3 ms 降到 131 us,快 71 倍。

倒排索引压缩实测:delta-varint 省 62% 体积,热点词位图让 AND 快 71 倍

搜索引擎的倒排表里,文档 ID 列表通常占索引体积的七成以上。压缩方式直接决定了三件事:索引能否全部驻留内存、冷启动要读多少字节、以及一次多词查询要付出多少解压开销。本文用一份可复现的合成语料,把最常用的三种表示放到同一张表上比较。

语料与三种表示

20 万篇文档、6 万词表、每篇 8 个词,词频服从 Zipf 分布(s=1.07),倒排项合计 160 万条。平均 df 28.4,中位 df 只有 4,最大 df 131424——典型的「长尾加少量超热点」结构。

三种表示:

  1. int32 定长数组,每个 docid 固定 4 字节;
  2. delta-varint,docid 递增,先做差分再用 LEB128 变长编码;
  3. 位图,第 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 单机实测,语料由固定随机种子生成,结果可复现。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。