File IndexScalarQuantizer.h

namespace faiss

k-means 聚类算法的多种变体实现。

版权所有 (c) Facebook, Inc. 及其关联公司。

此源代码根据 MIT 许可证授权，该许可证位于此源树的根目录中的 LICENSE 文件中。

IDSelector 旨在定义要处理的向量子集（用于删除或作为搜索的子集）

PQ4 SIMD 压缩和累积函数

基本内核使用 bbs = nb * 2 * 16 个向量累积 nq 查询向量，并生成一个用于该向量的输出矩阵。 这对于 nq * nb <= 4 很有用，否则寄存器溢出变得太大。

这些函数的实现分布在 3 个 cpp 文件中，以减少并行编译时间。 模板被显式实例化。

此文件包含用于计算距离的内核的回调。

在整个库中，向量以 float * 指针的形式提供。 当批量处理（添加/搜索）多个向量时，大多数算法都可以得到优化。 在这种情况下，它们作为矩阵传入。 当大小为 d 的 n 个向量作为 float * x 提供时，向量 i 的分量 j 是

x[ i * d + j ]

其中 0 <= i < n 且 0 <= j < d。换句话说，矩阵始终是紧凑的。指定矩阵的大小时，我们称其为 n*d 矩阵，这意味着行优先存储。

I/O 函数可以读/写到文件名、文件句柄或抽象介质的对象。

读取函数返回应使用 delete 释放的对象。这些对象中的所有引用都归该对象所有。

倒排列表的定义 + 一些实现该接口的常用类。

由于 IVF（倒排文件）索引在大规模用例中非常有用，因此我们将与它们相关的一些函数分组到这个小型库中。大多数函数都可以用于 IndexIVF 和嵌入在 IndexPreTransform 中的 IndexIVF。

在此文件中实现了 L2 和内积之外的其他度量

实现一些神经网络层，主要用于支持 QINCo

定义一些将转换应用于一组向量的对象。 通常这些是预处理步骤。

struct IndexScalarQuantizer : public faiss::IndexFlatCodes
#include <IndexScalarQuantizer.h>

基于标量量化器构建的 Flat 索引。

公共函数

IndexScalarQuantizer(int d, ScalarQuantizer::QuantizerType qtype, MetricType metric = METRIC_L2)

构造函数。

参数:

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

IndexScalarQuantizer()
virtual void train(idx_t n, const float *x) override

对代表性向量集执行训练。

参数:

  • n – 训练向量的数量

  • x – 训练向量，大小为 n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

通过解码实现的搜索

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

FlatCodesDistanceComputer 提供一个 distance_to_code 方法

默认实现使用 sa_decode 显式解码向量。

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

编码一组向量

参数:

  • n – 向量的数量

  • x – 输入向量，大小为 n * d

  • bytes – 输出编码向量，大小为 n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数:

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

公共成员

ScalarQuantizer sq

用于编码向量。

struct IndexIVFScalarQuantizer : public faiss::IndexIVF
#include <IndexScalarQuantizer.h>

IVF 实现，其中残差的组件使用标量量化器进行编码。 所有距离计算都是非对称的，因此编码向量会被解码并计算近似距离。

公共函数

IndexIVFScalarQuantizer(Index *quantizer, size_t d, size_t nlist, ScalarQuantizer::QuantizerType qtype, MetricType metric = METRIC_L2, bool by_residual = true)
IndexIVFScalarQuantizer()
virtual void train_encoder(idx_t n, const float *x, const idx_t *assign) override

训练向量的编码器。

如果 by_residual 为 true，则使用残差和相应的 assign 数组调用它；否则，x 是原始训练向量，assign=nullptr

virtual idx_t train_encoder_num_vectors() const override

可以被子类重新定义，以指示它们需要多少训练向量

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listnos = false) const override

对一组向量进行编码，就像它们出现在倒排列表中一样

参数:

  • list_nos – 量化器返回的倒排列表 id (大小为 n)。 -1s 被忽略。

  • codes – 输出代码，大小为 n * code_size

  • include_listno – 将列表 id 包含在代码中（在这种情况下，将 ceil(log8(nlist)) 添加到代码大小）

virtual void add_core(idx_t n, const float *x, const idx_t *xids, const idx_t *precomputed_idx, void *inverted_list_context = nullptr) override

向量加法的实现，其中向量分配是预定义的。 默认实现将代码提取交给 encode_vectors。

参数:

precomputed_idx – 输入向量的量化索引（大小为 n）

virtual InvertedListScanner *get_InvertedListScanner(bool store_pairs, const IDSelector *sel) const override

获取此索引的扫描器 (store_pairs 意味着忽略标签)

默认搜索实现使用它来计算距离

virtual void reconstruct_from_offset(int64_t list_no, int64_t offset, float *recons) const override

根据 (inv list index + inv list offset) 而不是 id 重构向量的给定位置。

当 direct_map 未维护并且 inv list offset 由 search_preassigned() 计算且 store_pairs 设置时，此方法非常有用。

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数:

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

公共成员

ScalarQuantizer sq