Реализация расстояния Левенштейна в питоне

Ваша "реализация" имеет несколько недостатков:

(1) Он должен начинаться с def lev(a, b):, а не def lev(s1, s2):. Пожалуйста, выработайте привычку (а) запускать свой код, прежде чем задавать вопросы о нем (б) цитировать код, который вы на самом деле запустили (путем копирования/вставки, а не повторным вводом (подверженным ошибкам).

(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) Ваша чрезвычайно наивная реализация хуже, потому что она копирует кусочки своих входов.

Вы можете найти работающие не очень наивные реализации в Интернете... google("levenshtein python")... ищите те, которые используют O(max(len(a), len(b))) дополнительной памяти.

То, что вы просили («расстояние редактирования для строки, которая имеет кратчайшее расстояние редактирования до других строк».) Не имеет смысла ... «Строка»??? "Для танго нужны двое" :-)

То, что вы, вероятно, хотите (найти все пары строк в наборе, которые имеют минимальное расстояние), или, может быть, только это минимальное расстояние, — это простое упражнение по программированию. Что вы пробовали?

Кстати, поиск этих пар с помощью упрощенного алгоритма потребует O(N ** 2) выполнения lev(), где N — количество строк в коллекции... если это реальное приложение, вам следует использовать проверенный код, а не пытаться написать его самостоятельно. Если это домашнее задание, так и скажите.

это то, что вы ищете??

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