文件 lattice_Zn.h

namespace faiss

实现具有多种变体的 k-means 聚类。

此源代码根据 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 ZnSphereSearch

#include <lattice_Zn.h>

返回球体中最接近查询的顶点。仅返回坐标，不返回 ID。

算法：所有点都是从一个原子向量导出的，直到置换和符号更改。搜索函数找到最合适的原子和转换。

被 faiss::ZnSphereCodec 继承

公共函数

ZnSphereSearch(int dim, int r2)

float search(const float *x, float *c) const: 查找最近的质心。 x 不需要标准化

float search(const float *x, float *c, float *tmp, int *tmp_int, int *ibest_out = nullptr) const: 完整调用。需要外部分配的临时空间

void search_multi(int n, const float *x, float *c_out, float *dp_out)

公共成员

int dimS

int r2

int natom

std::vector<float> voc: 大小为 dim * ntatom

struct EnumeratedVectors

被 faiss::ZnSphereCodec, faiss::ZnSphereCodecRec 继承

公共函数

inline explicit EnumeratedVectors(int dim)

virtual uint64_t encode(const float *x) const = 0: 从集合中编码一个向量

virtual void decode(uint64_t code, float *c) const = 0: 解码它

void encode_multi(size_t nc, const float *c, uint64_t *codes) const

void decode_multi(size_t nc, const uint64_t *codes, float *c) const

void find_nn(size_t n, const uint64_t *codes, size_t nq, const float *xq, int64_t *idx, float *dis)

inline virtual ~EnumeratedVectors()

公共成员

uint64_t nv: 集合的大小

int dim

struct Repeat

公共成员

float val

int n

struct Repeats

#include <lattice_Zn.h>

Repeats: 用于编码具有n个val值的向量。编码向量的符号和排列。对原子很有用。

被 faiss::ZnSphereCodec::CodeSegment 继承。

公共函数

Repeats(int dim = 0, const float *c = nullptr)

uint64_t count() const

uint64_t encode(const float *c) const

void decode(uint64_t code, float *c) const

公共成员

int dim

std::vector<Repeat> repeats

struct ZnSphereCodec : public faiss::ZnSphereSearch, public faiss::EnumeratedVectors 

#include <lattice_Zn.h>

可以为编码向量返回ID的编解码器

使用 ZnSphereSearch 通过编码排列和符号来编码向量。依赖于 ZnSphereSearch，因为它使用原子数。

被 faiss::ZnSphereCodecAlt 继承。

公共函数

ZnSphereCodec(int dim, int r2)

uint64_t search_and_encode(const float *x) const

virtual void decode(uint64_t code, float *c) const override: 解码它

virtual uint64_t encode(const float *x) const override: 接受不需要是质心的向量。

float search(const float *x, float *c) const: 查找最近的质心。 x 不需要标准化

float search(const float *x, float *c, float *tmp, int *tmp_int, int *ibest_out = nullptr) const: 完整调用。需要外部分配的临时空间

void search_multi(int n, const float *x, float *c_out, float *dp_out)

void encode_multi(size_t nc, const float *c, uint64_t *codes) const

void decode_multi(size_t nc, const uint64_t *codes, float *c) const

void find_nn(size_t n, const uint64_t *codes, size_t nq, const float *xq, int64_t *idx, float *dis)

公共成员

std::vector<CodeSegment> code_segments

uint64_t nv

size_t code_size

int dimS

int r2

int natom

std::vector<float> voc: 大小为 dim * ntatom

int dim

struct CodeSegment : public faiss::Repeats 

公共函数

inline explicit CodeSegment(const Repeats &r)

uint64_t count() const

uint64_t encode(const float *c) const

void decode(uint64_t code, float *c) const

公共成员

uint64_t c0

int signbits

int dim

std::vector<Repeat> repeats

struct ZnSphereCodecRec : public faiss::EnumeratedVectors 

#include <lattice_Zn.h>

递归球面编解码器

使用维度上的递归分解来编码由 ZnSphereSearch 找到的质心。这些代码与 ZnSpehreCodec 的代码不兼容

公共函数

ZnSphereCodecRec(int dim, int r2)

uint64_t encode_centroid(const float *c) const

virtual void decode(uint64_t code, float *c) const override: 解码它

virtual uint64_t encode(const float *x) const override: 向量需要是质心 (不适用于任意向量)

uint64_t get_nv(int ld, int r2a) const

uint64_t get_nv_cum(int ld, int r2t, int r2a) const

void set_nv_cum(int ld, int r2t, int r2a, uint64_t v)

void encode_multi(size_t nc, const float *c, uint64_t *codes) const

void decode_multi(size_t nc, const uint64_t *codes, float *c) const

void find_nn(size_t n, const uint64_t *codes, size_t nq, const float *xq, int64_t *idx, float *dis)

公共成员

int r2

int log2_dim

int code_size

所有可能的向量数量。

所有可能的向量的累积数量。

解码缓存的引导维度。

用于解码的缓存。

向量的数量。: 集合的大小

向量的维度。

如果维度是 2 的幂次方，则使用递归编码器；否则使用常规编码器。

#include <lattice_Zn.h>

如果 dim 是 2 的幂，则使用递归编解码器，否则使用常规编解码器

公共函数

ZnSphereCodecAlt 的构造函数。

对向量进行编码。: 接受不需要是质心的向量。

解码代码到向量。: 解码它

搜索并编码向量。

搜索最近的向量。: 查找最近的质心。 x 不需要标准化

搜索最近的向量。该版本提供额外的临时存储空间。: 完整调用。需要外部分配的临时空间

并行搜索多个向量。

编码多个向量。

void decode_multi(size_t nc, const uint64_t *codes, float *c) const

void find_nn(size_t n, const uint64_t *codes, size_t nq, const float *xq, int64_t *idx, float *dis)

公共成员

bool use_rec

ZnSphereCodecRec znc_rec

std::vector<CodeSegment> code_segments

uint64_t nv

size_t code_size

int dimS

int r2

int natom

std::vector<float> voc: 大小为 dim * ntatom

int dim