乘积量化 PQProduct quantization

把向量分成子空间，用各自码本中的编码近似表示。

常见操作#

d 为维度，M 为子空间数，K 为每个子空间码字数，n 为待扫描编码数；这里 d 可被 M 整除，K = 2^b，每个子空间维度 d/M。

操作	时间复杂度	条件与说明
训练码本	M 个子空间聚类	依赖训练样本数、K、迭代数与聚类算法，不能仅按编码长度估算。
编码一个向量	朴素穷举码字 $O(Kd)$	每子空间选择最近质心；加速器、批处理和编码策略可改变实际成本。
建立查询距离表	$O(Kd)$	计算查询到各子空间质心的距离。
扫描 n 个编码	$O(nM)$	对每个候选查 M 次表并累加；top-k 选择工作另计。

这些是基本 ADC 的成本。IVF-PQ 只扫描部分列表，OPQ 另有旋转；压缩后的距离是近似值，需要评估召回率。

1 个案例 · 附源码

Faiss·PQ 编码器v1.9.0

把向量拆成多组子向量，用各自码本中的编号表示每组子向量。

附源码片段 · 内存管理

基础原理参考资料

Jégou, Douze & Schmid · Product Quantization乘积码本与非对称距离估计的原始论文。

Faiss 1.9 · ProductQuantizer训练、编码、距离表和编码扫描实现。