1

我已经实现了该算法，但现在我想找到与其他字符串具有最短编辑距离的字符串的编辑距离。

这是算法：

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)
4

2 回答 2

5

您的“实施”有几个缺陷：

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

（二）没有终止条件；对于任何参数，它最终会尝试评估lev("", "")哪个会永远循环，如果不是因为 Python 实现限制：RuntimeError: maximum recursion depth exceeded.

您需要插入两行：

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

让它工作。

(3) Levenshtein 距离是递归定义的。没有“the”（唯一的）算法之类的东西。递归代码很少在课堂外看到，而且只能以“稻草人”的身份出现。

(4) 幼稚的实现所花费的时间和内存与len(a) * len(b)……这些字符串通常不是比 4 到 8 长一点吗？

(5) 您极其幼稚的实现更糟糕，因为它复制了输入的切片。

您可以在网络上找到工作的不太天真的实现... google("levenshtein python") ... 寻找那些使用O(max(len(a), len(b)))额外内存的实现。

你所要求的（“与其他字符串具有最短编辑距离的字符串的编辑距离。”）没有意义......“字符串”？？？“一个巴掌拍不响” ：-）

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

顺便说一句，通过简单的算法找到这些对将需要 O(N ** 2) 次执行，lev()其中 N 是集合中的字符串数......如果这是一个真实世界的应用程序，你应该考虑使用经过验证的代码而不是尝试自己编写。如果这是家庭作业，你应该这样说。

于 2010-11-13T17:59:53.867 回答
0

这就是你要找的吗？？

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])
于 2010-11-13T17:22:54.867 回答