如何找到两个相似的字符串？

Question

3

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

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

- Simd

你的数据集有10万个字符串，你会有新的查询到达吗？或者你会使用数据集中的一个字符串作为一个查询吗？ - gsamaras

对于给定的100k个字符串输入，我想要一个答案，即一对比所有其他字符串更接近的字符串。 - Simd

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gsamaras · Accepted Answer

这篇论文 "Hamming度量下的最近对问题"，作者Min、Kao、Zhu，看起来是你在寻找的内容，它适用于查找单个最近对。

对于你的情况，其中 n^0.294 < D < n，其中 D 是你的数据维数（1000），n 是数据集大小，该算法的运行时间为 O(n^1.843 D^0.533)。