string - 如何找到两个彼此靠近的字符串

Question

我有 n 个字符串，我想找到最近的一对。

找到这对的最快实用算法是什么？

Answer 1

论文“ The Closest Pair Problem under the Hamming Metric ”，Min, Kao, Zhu 似乎是你要找的，它适用于寻找一个最接近的对。

对于您的情况，其中 n ^0.294 < D < n，其中 D 是数据的维度 (1000)，n 是数据集的大小，算法将以 O(n ^1.843 D ^0.533 ) 运行。