Page 149 - 《软件学报》2026年第3期

1112 软件学报 2026 年第 37 卷第 3 期

4. distance[i] = L2_distance(central[i], q) //记录查询向量与每个量化向量的距离
5. end for
6. code_1 = find_min(distance) //搜索与查询向量距离最短的簇中心码字
7. residual = q − WRVQ(code_1) //计算第 1 层残差
8. //模糊匹配层
9. r = residual × d //将残差乘以权重, 该权重是由索引建立时, 根据检索精度和空间消耗权衡设定参数
10. for each c in codebook[2:n+1] do //从模糊匹配层对应的 n 个码本中遍历所有组合
11. central[i] = WRVQ(c) //记录每个组合对应量化向量
12. distance[i] = L2_distance(central[i], r) //记录残差与每个量化向量的距离
13. end for
14. code_2 = find_min_k(distance, k) //搜索与残差距离最短 k 个量化向量
15. code = [ (code_1, n) for each n in code_2] //计算潜在查询区域
16. //搜索层
17. for each c in data index do //遍历数据索引
18. if c[:n+1] in (code_1, code_2) then
19. central[i] = WRVQ(c) //计算真实残差
20. distance[i] = L2_distance(central, q) //计算真实距离
21. end if
22. end for
23. code = find_min(distance) //rerank 排序
24. v = WRVQ(code)
25. return v
从结构上我们可以看到, 当去除了模糊匹配层时, 算法的主体与传统倒排索引相似, 只是通过 WRVQ 量化方
法提升了准确率, 从而带来了更高的准确性. 然而, 在实验中我们发现, 模糊匹配层的加入巧妙地利用了 WRVQ 的
序列特性, 显著提高了搜索效率. 尽管模糊匹配层通过近似的方式缩小了搜索范围, 这不可避免地会导致一定的搜
索准确性的降低, 但在第 3 层的精确搜索中, 仍能获得较高的召回率.
在时间效率上, WRVQ 索引的检索时间复杂度与基于 IVF (inverted file) 的索引结构时间复杂度近似, 主要分
为 3 个部分. 精确匹配层在第 1 个码本中查找查询向量的最近邻簇中心, 这一过程的时间复杂度是 O(logN), 其
中, N 是第 1 个码本的大小. 模糊匹配层的检索方法类似, 时间复杂度为 O(n×logN), 其中, n 代表模糊匹配层对应
的码本个数. 搜索层进行量化编码的遍历, 对于每个搜索簇内的向量, 需要与查询向量的量化表示进行比较, 时间
复杂度为 O(k×N×d), 其中, k 表示搜索层对应的码本个数, d 表示向量维度大小. 因此, 总体的时间复杂度如公式
(15) 所示:

O(logN +n×logN +k×N×d) (15)
与基于其他类型索引结构 (如 HNSW) 的方案相比, WRVQ 索引的树结构保留了索引构建时间短、索引添加
和删除成本低的优势. 通过这一结构, 我们能够在保证合理准确率的前提下显著提升搜索效率.

4 实验分析

4.1 数据集与实验设置
本文使用通用测评库 MTEB 对我们所提出的量化表征算法进行效率和效果的综合评估. 在性能方面, 我们选
择分类任务、检索任务、 重排序任务、语义相似度任务、文本挖掘任务、聚类任务、配对分类任务这 7 个任务.
在效率方面, 我们对比了时空效率和增量更新的性能差异, 如表 1 所示.