在Python中实现Levenshtein距离

Question

我已经实现了这个算法，但现在我想找出与其他字符串的编辑距离最短的那个字符串。

下面是这个算法：

def lev(s1, s2):
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1)

Answer 1

这就是你想要的东西吗？？

import itertools
import collections

# My Simple implementation of Levenshtein distance
def levenshtein_distance(string1, string2):
    """
    >>> levenshtein_distance('AATZ', 'AAAZ')
    1
    >>> levenshtein_distance('AATZZZ', 'AAAZ')
    3
    """

    distance = 0

    if len(string1) < len(string2):
        string1, string2 = string2, string1

    for i, v in itertools.izip_longest(string1, string2, fillvalue='-'):
        if i != v:
            distance += 1
    return distance

# Find the string with the shortest edit distance.
list_of_string = ['AATC', 'TAGCGATC', 'ATCGAT']

strings_distances = collections.defaultdict(int)

for strings in itertools.combinations(list_of_string, 2):
    strings_distances[strings[0]] += levenshtein_distance(*strings)
    strings_distances[strings[1]] += levenshtein_distance(*strings)

shortest = min(strings_distances.iteritems(), key=lambda x: x[1])

Answer 2

你的“实现”有几个问题：

(1) 开头应该是 def lev(a, b):，而不是 def lev(s1, s2):。请养成好习惯，(a) 在提问之前先运行你的代码，(b) 引用你实际运行过的代码（通过复制粘贴，而不是容易出错的重新输入）。

(2) 代码没有结束条件；对于任何参数，它最终会尝试计算 lev("", "")，如果不是因为Python的实现限制，这会导致无限循环：RuntimeError: maximum recursion depth exceeded。

你需要插入两行代码：

if not a: return len(b)
if not b: return len(a)

这样才能让它正常工作。

(3) 莱文斯坦距离是通过递归定义的。并没有“唯一”的算法。递归代码在课堂之外很少见，通常只是作为一种示例。

(4) 简单的实现会消耗与 len(a) * len(b) 成正比的时间和内存……这些字符串通常不会比4到8长吗？

(5) 你的这个非常简单的实现更糟，因为它会复制输入的切片。

你可以在网上找到一些可用的、不那么简单的实现……搜索“levenshtein python”……找那些使用 O(max(len(a), len(b))) 额外内存的实现。

你问的这个问题（“与其他字符串的编辑距离最短的字符串的编辑距离。”）没有意义……“那个字符串”？？“双人舞需要两个人”:-)

你可能想要的（找到集合中所有字符串对的最小距离），或者只是那个最小距离，是一个简单的编程练习。你尝试过什么？

顺便说一下，使用简单算法找到这些对需要执行 lev() 的 O(N ** 2) 次，其中 N 是集合中字符串的数量……如果这是一个实际应用，你应该考虑使用经过验证的代码，而不是自己尝试写。如果这是作业，你应该说明一下。