©2020-2024 ioDraw All rights reserved
hnswlib 代码分析 hnswlib 源码分析
train过程说明
*
* 主要是生成hnsw模型
* Hnsw中，storage中存储的原始的中心点向量
* 生成hnsw
* 为每层分配空间
* 每层的中心点在当前层及下面的每一层都有中心点，例如第n层在n、n-1、…1层都有临近点，第3层只在3、2、1层有临近点。
* 同一个临近点在各层的数据是连续存储在一起的。
* 新加入的数据在下面的各层查找对应的临近点的候选集，选出最后的临近点，然后建立link
* 调整其他临近点的link，因为临近是相互的
76 void HNSW::set_default_probas(int M, float levelMult)
77 {
78 int nn = 0;
79 cum_nneighbor_per_level.push_back (0);
80 for (int level = 0; ;level++) {
81 float proba = exp(-level / levelMult) * (1 - exp(-1 / levelMult));
///点落在每一层的概率,层越高概率越低，第0层概率为0.5
82 if (proba < 1e-9) break;
83 assign_probas.push_back(proba); ///向量落入每一层的概率
84 nn += level == 0 ? M * 2 : M;
85 cum_nneighbor_per_level.push_back (nn); ///每一层临近点的个数(每一层保存的是前几层的和)
86 }
87 }
203 /*n:向量个数, 为offsets,neighbors赋值*/
204 int HNSW::prepare_level_tab(size_t n, bool preset_levels)
205 {
206 size_t n0 = offsets.size() - 1;
207
208 if (preset_levels) {
209 FAISS_ASSERT (n0 + n == levels.size());
210 } else {
211 FAISS_ASSERT (n0 == levels.size());
212 for (int i = 0; i < n; i++) { ///为每条数据指定放到第几层
213 int pt_level = random_level(); ///数据放入第几层
214 levels.push_back(pt_level + 1); ///根据概率为数据指定level
215 }
216 }
217
218 int max_level = 0;
219 for (int i = 0; i < n; i++) { ///感觉这里是为offsets neighbors分配空间
220 int pt_level = levels[i + n0] - 1; ///第几层
221 if (pt_level > max_level) max_level = pt_level;
222 offsets.push_back(offsets.back() +
223 cum_nb_neighbors(pt_level + 1)); ///偏移是前面所有个数的累加
224 neighbors.resize(offsets.back(), -1);
225 }
226
227 return max_level; ///
}
439 /// Finds neighbors and builds links with them, starting from an entry
440 /// point. The own neighbor list is assumed to be locked.
pt_id:向量(query向量)对应的id, nearest:最近点的idx(可以理解为中心点id)，d_nearest:
最近距离,level:对应的层。在当前层查找最近的临近点，然后更新相关的临近点(随着新中心点加入，已加入的中心点的临近点也会发生变化)
441 void HNSW::add_links_starting_from(DistanceComputer& ptdis,
442 storage_idx_t pt_id,
443 storage_idx_t nearest,
444 float d_nearest,
445 int level,
446 omp_lock_t *locks,
447 VisitedTable &vt)
448 {
449 std::priority_queue<NodeDistCloser> link_targets;
450
451 search_neighbors_to_add(*this, ptdis, link_targets, nearest, d_nearest,
452 level, vt); ///当前层中和query最近的中心点放到link_targets队列中
453
454 // but we can afford(给予) only this many neighbors
455 int M = nb_neighbors(level); ///当前层的连接点数
456
457 ::faiss::shrink_neighbor_list(ptdis, link_targets, M);
///根据需要缩减临近点的数量(保留有代表性的临近点),把最优的放入link_targets中
458
459 while (!link_targets.empty()) {
460 int other_id = link_targets.top().id;
462 omp_set_lock(&locks[other_id]);
463 add_link(*this, ptdis, other_id, pt_id, level);
///调整other_id对应临近点(临近点是有限的)
464 omp_unset_lock(&locks[other_id]);
465
466 add_link(*this, ptdis, pt_id, other_id, level); ///调整新的链接(临近点是有限的)
467
468 link_targets.pop();
469 }
470 }