python - 如何有效地计算大量数据的距离矩阵

Question

我有一个问题，我试图使用 Edit/Levenshtein 距离计算最近的字符串。

我有一个包含大约 250,000 个唯一字符串的列表，对于列表中的每个项目，我需要返回列表中最接近的字符串的索引。

我的问题是我不能只使用 pdist 之类的东西，因为它会生成一个 250k^2/2 数组并且会导致内存问题。但是如果我像这样逐行操作

def closest(s):
    """
    Returns index of minimum Levenshtein distance
    """
    distances = [levenshtein_distance(s, X[i]) for i in range(len(X))]
    minimum_distance = min(i for i in distances if i > 0)
    return distances.index(minimum_distance)

这也将非常低效，因为它没有像 pdist 那样进行优化，并且与生成密集矩阵相同。

有人有什么建议吗？非常感谢！

标签： pythonpandasdataframescikit-learn