文件 hamming.h

namespace faiss

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

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

此源代码已获得 MIT 许可，可在该源树的根目录中的 LICENSE 文件中找到。

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

PQ4 SIMD 打包和累积函数

基本内核累积 nq 个查询向量，其中 bbs = nb * 2 * 16 个向量，并生成该输出矩阵。它对于 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

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

函数

void bitvec_print(const uint8_t *b, size_t d)
void fvecs2bitvecs(const float *x, uint8_t *b, size_t d, size_t n)
void bitvecs2fvecs(const uint8_t *b, float *x, size_t d, size_t n)
void fvec2bitvec(const float *x, uint8_t *b, size_t d)
void bitvec_shuffle(size_t n, size_t da, size_t db, const int *order, const uint8_t *a, uint8_t *b)

从 b(i, j) := a(i, order[j]) 混洗位

void hammings(const uint8_t *a, const uint8_t *b, size_t na, size_t nb, size_t nbytespercode, hamdis_t *dis)

计算 na 和 nb 个二进制向量之间的一组汉明距离

参数:

  • a – 大小为 na * nbytespercode

  • b – 大小为 nb * nbytespercode

  • nbytespercode – 应该是 8 的倍数

  • dis – 输出距离，大小为 na * nb

void hammings_knn_hc(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t ncodes, int ordered, ApproxTopK_mode_t approx_topk_mode = ApproxTopK_mode_t::EXACT_TOPK)

返回一组二进制查询向量的 k 个最小汉明距离，使用最大堆。

参数:

  • a – 查询，大小为 ha->nh * ncodes

  • b – 数据库，大小为 nb * ncodes

  • nb – 数据库向量的数量

  • ncodes – 二进制代码的大小（字节）

  • ordered – 如果 != 0：按递减距离对结果排序（对于 k/n > 0.01 可能是瓶颈）

  • approx_topk_mode – 允许使用近似 top-k 功能来加速堆

void hammings_knn(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t ncodes, int ordered)
void hammings_knn_mc(const uint8_t *a, const uint8_t *b, size_t na, size_t nb, size_t k, size_t ncodes, int32_t *distances, int64_t *labels)

返回一组二进制查询向量的 k 个最小汉明距离，使用计数最大值。

参数:

  • a – 查询向量, 大小为 na * ncodes

  • b – 数据库，大小为 nb * ncodes

  • na – 查询向量的数量

  • nb – 数据库向量的数量

  • k – 返回的向量/距离的数量

  • ncodes – 二进制代码的大小（字节）

  • distances – 输出每个查询向量到其 k 个最近邻的距离

  • labels – 输出每个查询向量的 k 个最近邻的 ID

void hamming_range_search(const uint8_t *a, const uint8_t *b, size_t na, size_t nb, int radius, size_t ncodes, RangeSearchResult *result)

与 hammings_knn 相同，但我们正在使用 radius 进行范围搜索

void hamming_count_thres(const uint8_t *bs1, const uint8_t *bs2, size_t n1, size_t n2, hamdis_t ht, size_t ncodes, size_t *nptr)
size_t match_hamming_thres(const uint8_t *bs1, const uint8_t *bs2, size_t n1, size_t n2, hamdis_t ht, size_t ncodes, int64_t *idx, hamdis_t *dis)
void crosshamming_count_thres(const uint8_t *dbs, size_t n, hamdis_t ht, size_t ncodes, size_t *nptr)
void generalized_hammings_knn_hc(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t code_size, int ordered = true)

广义汉明距离（=计算相同代码字节的数量）

void pack_bitstrings(size_t n, size_t M, int nbit, const int32_t *unpacked, uint8_t *packed, size_t code_size)

打包一组大小为 M * nbit 的 n 个代码

参数:

  • n – 要打包的代码数量

  • M – 每个代码的基本代码数量

  • nbit – 每个基本代码的位数

  • unpacked – 输入解包的代码，大小 (n, M)

  • packed – 输出打包的代码，大小 (n, code_size)

  • code_size – 应该 >= ceil(M * nbit / 8)

void pack_bitstrings(size_t n, size_t M, const int32_t *nbits, const int32_t *unpacked, uint8_t *packed, size_t code_size)

打包一组可变大小的 n 个代码

参数:

nbit – 每个条目的位数（大小为 M）

void unpack_bitstrings(size_t n, size_t M, int nbit, const uint8_t *packed, size_t code_size, int32_t *unpacked)

解包一组大小为 M * nbit 的 n 个代码

参数:

  • n – 要打包的代码数量

  • M – 每个代码的基本代码数量

  • nbit – 每个基本代码的位数

  • unpacked – 输入解包的代码，大小 (n, M)

  • packed – 输出打包的代码，大小 (n, code_size)

  • code_size – 应该 >= ceil(M * nbit / 8)

void unpack_bitstrings(size_t n, size_t M, const int32_t *nbits, const uint8_t *packed, size_t code_size, int32_t *unpacked)

解包一组 n 个可变大小的代码

参数:

nbit – 每个条目的位数（大小为 M）

变量

FAISS_API size_t hamming_batch_size
struct BitstringWriter

公共函数

inline BitstringWriter(uint8_t *code, size_t code_size)
inline void write(uint64_t x, int nbit)

公共成员

uint8_t *code
size_t code_size
size_t i
struct BitstringReader

公共函数

inline BitstringReader(const uint8_t *code, size_t code_size)
inline uint64_t read(int nbit)

公共成员

const uint8_t *code
size_t code_size
size_t i