Ecrivez une fonction haute performance pour trouver la distance d'édition de Levenstein, qui représente la distance entre les chaînes contenant "pleine largeur".
Cependant, le coût d'ajout, de suppression et de remplacement est égal à 1.
La distance de Levenstein (Lebenstein Kyori) ou la distance d'édition (Henshu Kyori) est une valeur numérique qui indique à quel point les deux chaînes de caractères sont différentes en théorie de l'information. Plus précisément, il correspond au nombre minimum d'étapes requises pour transformer une chaîne de caractères en une autre en insérant, supprimant ou remplaçant des caractères. Pour donner un exemple de la façon de trouver une distance pratique, transformer «chaton» en «assis» nécessite au moins trois étapes comme indiqué ci-dessous, donc Levenstein entre deux mots La distance est de 3. kitten assis (remplacer «k» par «s») assis (remplacer "e" par "i") assis (insérer «g» pour terminer) (De wikipedia)
def levenshtein(s1, s2):
if len(s1) < len(s2):
return levenshtein(s2, s1)
# len(s1) >= len(s2)
if len(s2) == 0:
return len(s1)
previous_row = range(len(s2) + 1)
for i, c1 in enumerate(s1):
current_row = [i + 1]
for j, c2 in enumerate(s2):
insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
deletions = current_row[j] + 1 # than s2
substitutions = previous_row[j] + (c1 != c2)
current_row.append(min(insertions, deletions, substitutions))
previous_row = current_row
return previous_row[-1]
Cité ci-dessous http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
Recommended Posts