Implementando la distancia de Levenshtein en python

He implementado el algoritmo, pero ahora quiero encontrar la distancia de edición para la cadena que tiene la distancia de edición más corta a las otras cadenas.

Aquí está el algoritmo:

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) 

Su “implementación” tiene varios defectos:

(1) Debe comenzar con def lev(a, b): no def lev(s1, s2): Póngase en contacto con los buenos hábitos de (a) ejecutar su código antes de hacer preguntas sobre él (b) y citar el código que realmente ejecutó (copiando / pegando, no volviendo a escribir (propenso a errores)).

(2) No tiene condiciones de terminación; para cualquier argumento, eventualmente terminará tratando de evaluar lev("", "") que se repetirá para siempre si no fuera por los límites de implementación de Python: RuntimeError: maximum recursion depth exceeded .

Necesitas insertar dos líneas:

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

para que funcione.

(3) La distancia de Levenshtein se define recursivamente. No existe tal cosa como el algoritmo (el único). El código recursivo rara vez se ve fuera de un aula y, luego, solo en la capacidad de un “hombre de paja”.

(4) Las implementaciones ingenuas toman tiempo y la memoria es proporcional a len(a) * len(b) … ¿no son esas cadenas normalmente un poco más largas que de 4 a 8?

(5) Su implementación extremadamente ingenua es peor, porque copia porciones de sus entradas.

Puede encontrar implementaciones no muy ingenuas en la web … google (“levenshtein python”) … buscar las que usan O(max(len(a), len(b))) memoria adicional.

Lo que pidió (“la distancia de edición para la cadena que tiene la distancia de edición más corta a las otras cadenas”). No tiene sentido … “LA cadena” ??? “Se necesitan dos para bailar un tango” 🙂

Lo que probablemente desee (encontrar todos los pares de cadenas en una colección que tengan la distancia mínima), o tal vez solo esa distancia mínima, es un simple ejercicio de progtwigción. ¿Qué has probado?

Por cierto, encontrar esos pares mediante un algoritmo simplista tomará O (N ** 2) ejecuciones de lev() donde N es el número de cadenas en la colección … si esta es una aplicación del mundo real, debe buscar para usar código probado en lugar de intentar escribirlo usted mismo. Si esto es tarea, deberías decirlo.

¿Es esto lo que estás buscando?

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