在python中实现Levenshtein距离

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

这里的算法：

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)

来源

2010-11-13 Karl Grims

那是行使功能吗？ a和b没有被定义，如果你的意思是arg是a和b，它会遍历递归限制。 – Hollister 2010-11-13 17:25:07

这是你在找什么？

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-13 17:22:54 mouad

这是错误的：levenshtein_distance（“ABCDEFGH”，“AABCDEFGH”）返回8，当它应该是1（插入'A'） – luispedro 2010-11-13 17:49:15

@luispedro：实际上我知道并且像我说的在我的答案中__我简单地实现了Levenshtein distance__，我写了这个__Simple Implementation__来显示我的答案的第二部分，这是OP要求的：__getting与其他字符串具有最短编辑距离的字符串，并且因为他放置的算法不起作用:) – mouad 2010-11-13 17:54:31

这很好，但是我怎样才能在不使用itertools和集合的情况下编写它？ – 2010-11-13 18:02:01

你的 “执行” 有几个缺陷：

（1）它应与def lev(a, b):，不def lev(s1, s2):启动。（b）引用您实际运行的代码（通过复制/粘贴，而不是（容易出错）重新输入），请进入（a）运行代码的良好习惯。（2）不具有终止条件;对于任何参数，它最终都会试图评估lev("", "")，它将永远循环，因为它不适用于Python实现限制：RuntimeError: maximum recursion depth exceeded。

你需要插入两行：

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

，使其工作。（3）Levenshtein距离为递归定义。没有“the”（唯一的）算法。递归代码很少在教室外看到，然后只能用“strawman”的能力。

（4）天真的实现需要时间和内存成正比len(a) * len(b) ......没有这些字符串通常一点点时间超过4〜8？

（5）你非常天真的执行更糟糕，因为它复制其输入的切片。

你可以找到工作在网络上不是很天真的实现...谷歌（“levenshtein python”）...寻找使用O(max(len(a), len(b)))额外的内存。

你问的（“编辑距离为谁拥有别人串最短编辑距离的字符串。”）没有意义......“字符串” ??? “这巴掌拍不响” :-)

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

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

来源

2010-11-13 17:59:53

在python中实现Levenshtein距离

回答

相关问题