计算莱文斯坦距离

Question

我不确定这个问题是不是重复的。不过，我想了解一下在R、Java或Python中优化的Levenshtein距离算法的实现。我有一个文本文件，里面有很多行字符串（大约2000条记录），这些字符串是按字母顺序排列的，可能它们之间有某种相似性。现在，我想比较文件中所有字符串的每一对，并输出一个距离矩阵。另外，请告诉我如何使用这个矩阵来根据我的需求筛选字符串，比如说Levenshtein距离小于等于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的单词（通过其他单词连接），我想这正是你想要的结果。