Levenshtein距离的计算

Question

我不确定这个问题是否重复。但是，我想知道更多关于优化的Levenshtein距离算法在R或Java或Python中的实现。我有一个文本文件，其中包含许多字符串逐行(接近2000条记录如下所示)，按字母顺序排列，它们之间可能有某种相似性。现在，我想比较文件中所有的字符串对并输出距离矩阵。另外，请让我知道如何使用这个矩阵来根据我的要求过滤集合字符串，说LD <=2。

如果问题不清楚，你需要更多的信息，再来找我。

Sample Text File
----------------
abc
abcd
abe
bac
bad
back
blade
cub
cube
cute
dump
duke

Answer 1

所以这可以用稍微相反的方式完成。创建您的字典d = {word:[] for word in file}。现在:

for word in d:
    for neighbor in edit_distance_1(word):
        if neighbor in d:
            d[word].append(neighbor)

现在d将是其编辑距离为1的邻居的所有单词的图。您可以进一步跟踪这些边缘以获得编辑距离2个单词(通过其他单词)，我相信这是您想要的。