algorithm - 使用自定义距离函数对数百万个字符串进行模糊搜索

Question

我有一大堆短字符串和一个自定义距离函数（比如说 Damerau-Levenshtein 距离）。

问：根据自定义距离从池中获取前 N 个字符串的最先进的解决方案是什么？

我正在寻找解决这个问题的理论方法以及编码实现（Java、Python 等）。

Answer 1

直接的方法是迭代所有字符串，计算每个字符串的距离，并在迭代时只保留最好的 N。

如果您需要大量执行此任务，您应该考虑是否可以为成本计算出比实际成本函数更快的上限/下限估计。例如，为您的字符串预先计算所有 n-gram（例如 3-gram）。或者也许比较长度差异已经可以给出距离的下限。比你可以跳过所有字符串的距离计算，这些字符串的下限距离高于你当前第 n 个最佳匹配的距离。