具有自定义距离功能的数百万字符串的模糊搜索

Question

我有大量的短字符串和自定义距离功能（例如，damerau – levenshtein距离）。

Q：根据自定义距离从池中获取顶级N字符串的最新解决方案是什么？

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

Answer 1

直截了当的方法是在所有字符串上迭代，计算每个字符串的距离，并在迭代时仅保持最佳n。

如果您需要经常执行此任务，则应该认为，如果您可以提出比实际成本功能快得多的成本的上限/下限估计。例如。预先计算您的字符串的所有n-gram（例如3克）。也许比较长度差可以为距离提供下限。比您可以跳过所有字符串的距离计算，该字符串的下限距离高于您的当前最佳匹配的距离。