Implémentation de la distance Levenshtein en python

Question

J'ai implémenté l'algorithme, mais maintenant je veux trouver la distance d'édition de la chaîne qui a la plus courte distance d'édition par rapport aux autres chaînes.

Voici l'algorithme:

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) 

Answer 1

est ce que vous cherchez ??

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

Answer 2

Votre "mise en œuvre" a plusieurs défauts:

(1) Il devrait commencer par def lev(a, b):, non def lev(s1, s2):. S'il vous plaît prenez les bonnes habitudes de (a) exécuter votre code avant de poser des questions à son sujet (b) en citant le code que vous avez réellement exécuté (par copier/coller, pas par (retable) retaper).

(2) Il n'y a pas de conditions de terminaison; pour tous les arguments, il finira par essayer d'évaluer lev("", "") qui serait bouclé à jamais s'il n'y avait pas les limites d'implémentation Python: RuntimeError: maximum recursion depth exceeded.

Vous devez insérer deux lignes:

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

pour le faire fonctionner. (3) La distance de Levenshtein est définie récursivement. Il n'y a pas d'algorithme "le" (un et unique). Le code récursif est rarement vu à l'extérieur d'une salle de classe et seulement à titre de «pailleur».

(4) Les implémentations naïves prennent du temps et la mémoire est proportionnelle à len(a) * len(b) ... ces chaînes ne sont-elles pas normalement un peu plus longues que 4 à 8?

(5) Votre implémentation extrêmement naïve est pire, car elle copie des tranches de ses entrées.

Vous pouvez trouver travail implémentations non-très naïfs sur le web ... Google ("de python levenshtein") ... recherchez ceux qui utilisent O(max(len(a), len(b))) la mémoire supplémentaire. Ce que vous avez demandé ("la distance d'édition pour la chaîne qui a la distance d'édition la plus courte pour les autres chaînes.") N'a pas de sens ... "LA chaîne" ??? "Il faut deux pour faire du tango" :-)

Ce que vous voulez probablement (trouver toutes les paires de chaînes dans une collection qui ont la distance minimale), ou peut-être juste cette distance minimale, est un exercice de programmation simple. Qu'avez-vous essayé? Par ailleurs, trouver ces paires par un algorithme simpliste prendra O (N ** 2) exécutions de lev() où N est le nombre de chaînes dans la collection ... si c'est une application du monde réel, vous devrait chercher à utiliser du code éprouvé plutôt que d'essayer de l'écrire vous-même. Si c'est devoirs, vous devriez le dire.