Schreiben Sie eine leistungsstarke Funktion, um den Levenstein-Bearbeitungsabstand zu ermitteln, der den Abstand zwischen Zeichenfolgen darstellt, die "volle Breite" enthalten.
Die Kosten für das Hinzufügen, Löschen und Ersetzen betragen jedoch alle 1.
Der Levenstein-Abstand (Lebenstein Kyori) oder der Bearbeitungsabstand (Henshu Kyori) ist ein numerischer Wert, der angibt, wie unterschiedlich die beiden Zeichenketten in der Informationstheorie sind. Insbesondere wird die Mindestanzahl von Schritten angegeben, die erforderlich sind, um eine Zeichenfolge durch Einfügen, Löschen oder Ersetzen von Zeichen in eine andere umzuwandeln. Um ein Beispiel dafür zu geben, wie man eine praktische Distanz findet, erfordert die Umwandlung von „Kätzchen“ in „Sitzen“ mindestens drei Schritte, wie unten gezeigt, also Levenstein zwischen zwei Wörtern Die Entfernung beträgt 3. kitten sitten (ersetzen Sie "k" durch "s") sittin (ersetze "e" durch "i") Sitzen (zum Schluss „g“ einfügen) (Aus 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]
Von unten zitiert http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
Recommended Posts