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

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

1 голос
/ 13 ноября 2010

Я реализовал алгоритм, но теперь я хочу найти расстояние редактирования для строки, которая имеет самое короткое расстояние редактирования для других строк.

Вот алгоритм: 

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)

Ответы [ 2 ]

5 голосов
/ 13 ноября 2010

У вашей "реализации" есть несколько недостатков:

(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))) дополнительную память.

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

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

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

0 голосов
/ 13 ноября 2010

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

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