Informationen zum Buch
Levenshtein-Distanz
Einführung
In diesem Kapitel behandeln wir die Levenshtein-Distanz und zeigen einige Beispiel-Implementierungen in Python. Es gibt viele Anwendungs-Bereiche für die Levenshtein-Distanz und die zugrunde liegenden Ideen sind weit verbreitet. z.B. in Bereichen wie Computer-Wissenschaften, Computerlinguistik, Bioinformatik, Molekular-Biologie und DNA-Analyse. Ebenso können Ähnlichkeiten in Melodien und Rhythmen gemessen werden. Die Levenshtein-Distanz ist auch im alltäglichen Leben zu finden. Immer wenn Sie ein Programm oder eine Applikation verwenden, die in irgendeiner Art und Weise die Rechtschreibung prüft oder Fehler korrigiert, werden die Programmierer die "Editierdistanz" oder "Levenshtein-Distanz" verwenden.Möglicherweise haben Sie bereits ein weiteren möglichen Anwendungs-Bereich erkannt: Stellen Sie sich vor, Sie verwenden ein Python-Dictionary, mit Strings als Schlüssel.
Schauen wir uns dazu das folgende Beispiel an, in dem Städtenamen der Vereinigten Staaten oft falsch geschrieben sind:
cities = {"Pittsburgh":"Pennsylvania",
"Tucson":"Arizona",
"Cincinnati":"Ohio",
"Albuquerque":"New Mexico",
"Culpeper":"Virginia",
"Asheville":"North Carolina",
"Worcester":"Massachusetts",
"Manhattan":"New York",
"Phoenix":"Arizona",
"Niagara Falls":"New York"}
Beim Versuch die entsprechenden Städtenamen aus dem Dictionary zu lesen, treten Exceptions auf:
cities["Tuscon"]
cities["Pittsburg"]
cities["Cincinati"]
cities["Albequerque"]
Wenn ein Mensch die Fehler sieht, wird er oder sie kein Problem damit haben die Stadt zu erkennen. Auf der anderen Seite ist das Python-Dictionary kleinlich und verzeiht keine Fehler. Es akzeptiert nur eindeutige Schlüssel. Die Frage ist, bis zu welchem Grad sind zwei Strings gleich? Was wir brauchen ist eine String-Ähnlichkeits-Metrik oder eine Messung für die "Entfernung" von Strings. Eine String-Metrik misst die Entfernung zwischen zwei Zeichenketten. Eine der bekanntesten Metriken ist die s.g. Levenshtein-Distanz oder Editierdistanz. Levenshtein berechnet die nötige Anzahl der Ersetzungen und Löschungen um einen String in einen anderen umzuwandeln.
Die minimale Editierdistanz oder Levenshtein-Distanz
Die minmale Editierdistanz zwischen zwei Strings ist die kleinste Anzahl an nötigen Editier-Operationen um einen String in einen anderen umzuwandeln. Die Editier-Operationen bestehen aus Einfüge-, Lösch- und Ersetz-Operationen.Die einfachste Menge von Editier-Operationen kann wie folgt definiert werden:
- Einfügen eines einzelnen Zeichens. Das bedeutet dass wir ein Zeichen zu einem String s hinzufügen.
Beispiel: Wenn wir den String s = "Manhatan" haben, können wir das Zeichen "t" einfügen um die korrekte Schreibweise zu erhalten:>>> s = "Manhatan" >>> s = s[:5] + "t" + s[5:] >>> print(s) Manhattan
- Löschung eines einzelnen Zeichens.
Beispiel:>>> s = "Mannhattan" >>> s = s[:2] + s[3:] >>> s 'Manhattan'
- Ersetzen eines einzelnen Zeichens.
Im folgenden Beispiel ändern wir den Buchstaben "o" in den Buchstaben "a" um die Schreibweise zu korrigieren.>>> s = "Manhatton" >>> s = s[:7] + "a" + s[8:] >>> s 'Manhattan'
>>> s = "Mannhaton" >>> s = s[:2] + s[3:] # deletion >>> s 'Manhaton' >>> s = s[:5] + "t" + s[5:] # insertion >>> s 'Manhatton' >>> s = s[:7] + "a" + s[8:] # substitution >>> s 'Manhattan'Wir können jeder dieser Operation eine Gewichtung zuordnen, z.B. jedes auf den Wert 1 setzen. Es ist auch möglich dafür zu argumentieren, dass Ersetz-Operationen mehr wert sind, als Lösch-Operationen. Manchmal wird so die Gewichtung für Ersetz-Operationen auf 2 gesetzt.
Mathematische Definition der Levenshtein-Distanz
Die Levenshtein-Distanz zwischen zwei Strings a und b ist gegeben durch leva,b(len(a), len(b)) wenn leva,b(i,j) gleich ist mit -max(i,j) wenn min(i,j)=0- andernfalls:
min(leva,b(i-1, j) + 1,
leva,b(i, j+1) + 1,
leva,b(i-1, j+1) + 1ai≠bj)
Wobei 1ai≠bjdie Indikator-Funktion gleich ist mit 0 wenn ai=bj
und andernfallss gleich 1. Und leva,b(i,j) ist die Distanz zwischen dem ersten Zeichen i aus a und dem ersten Zeichen j aus b.
Die Levenshtein-Distanz hat folgende Eigenschaften:
- Ist 0, wenn die Strings gleich sind
- Ist mindestens die Differenz der Länge der beiden Strings
- Ist höchstens die Länge des längeren Strings
- Dreiecksungleichung: Die Levenshtein-Distanz zwischen zwei Strings ist nicht größer als die Summe der Levenshtein-Distanzen zu einem dritten String.
Rekursive Levenshtein-Funktion in Python
Die folgende Python-Funktion implementiert die Levenshtein-Distanz in einer rekursiven Variante:
def LD(s, t):
if s == "":
return len(t)
if t == "":
return len(s)
if s[-1] == t[-1]:
cost = 0
else:
cost = 1
res = min([LD(s[:-1], t)+1,
LD(s, t[:-1])+1,
LD(s[:-1], t[:-1]) + cost])
return res
print(LD("Python", "Peithen"))
Das Python-Code liefert uns das folgende Ergebnis:
3Die rekursive Implementierung ist sehr ineffizient, weil es die Levenshtein-Distanz von gleichen Teil-Strings immer wieder neu berechnet. Im folgenden Beispiel zählen wir die Anzahl der Aufrufe indem wir eine Dekorateur-Funktion. Wenn ihnen diese Thematik nicht bekannt ist, empfehlen wir unser Kapitel über Memoisation und Dekorateure.
from collections import Counter
def call_counter(func):
def helper(*args, **kwargs):
helper.calls += 1
key = str(args) + str(kwargs)
helper.c[key] += 1
return func(*args, **kwargs)
helper.c = Counter()
helper.calls = 0
helper.__name__= func.__name__
return helper
@call_counter
def LD(s, t):
if s == "":
return len(t)
if t == "":
return len(s)
if s[-1] == t[-1]:
cost = 0
else:
cost = 1
res = min([LD(s[:-1], t)+1,
LD(s, t[:-1])+1,
LD(s[:-1], t[:-1]) + cost])
return res
print(LD("Python", "Peithen"))
print("LD was called " + str(LD.calls) + " times!")
print(LD.c.most_common())
Folgendes Ergebnis erhalten wir:
3
LD was called 29737 times!
[("('', 'P'){}", 5336), ("('P', ''){}", 4942), ("('', ''){}", 3653), ("('P', 'P'){}", 3653), ("('', 'Pe'){}", 2364), ("('P', 'Pe'){}", 1683), ("('Py', ''){}", 1666), ("('Py', 'P'){}", 1289), ("('', 'Pei'){}", 912), ("('Py', 'Pe'){}", 681), ("('P', 'Pei'){}", 681), ("('Pyt', ''){}", 462), ("('Pyt', 'P'){}", 377), ("('Py', 'Pei'){}", 321), ("('', 'Peit'){}", 292), ("('Pyt', 'Pe'){}", 231), ("('P', 'Peit'){}", 231), ("('Py', 'Peit'){}", 129), ("('Pyt', 'Pei'){}", 129), ("('Pyth', ''){}", 98), ("('Pyth', 'P'){}", 85), ("('', 'Peith'){}", 72), ("('Pyt', 'Peit'){}", 63), ("('Pyth', 'Pe'){}", 61), ("('P', 'Peith'){}", 61), ("('Py', 'Peith'){}", 41), ("('Pyth', 'Pei'){}", 41), ("('Pyth', 'Peit'){}", 25), ("('Pyt', 'Peith'){}", 25), ("('Pytho', ''){}", 14), ("('Pyth', 'Peith'){}", 13), ("('Pytho', 'P'){}", 13), ("('', 'Peithe'){}", 12), ("('Pytho', 'Pe'){}", 11), ("('P', 'Peithe'){}", 11), ("('Py', 'Peithe'){}", 9), ("('Pytho', 'Pei'){}", 9), ("('Pyt', 'Peithe'){}", 7), ("('Pytho', 'Peit'){}", 7), ("('Pyth', 'Peithe'){}", 5), ("('Pytho', 'Peith'){}", 5), ("('Pytho', 'Peithe'){}", 3), ("('Python', 'Pei'){}", 1), ("('Python', 'Peithe'){}", 1), ("('', 'Peithen'){}", 1), ("('P', 'Peithen'){}", 1), ("('Pytho', 'Peithen'){}", 1), ("('Py', 'Peithen'){}", 1), ("('Python', 'P'){}", 1), ("('Python', 'Peit'){}", 1), ("('Pyt', 'Peithen'){}", 1), ("('Pyth', 'Peithen'){}", 1), ("('Python', 'Peith'){}", 1), ("('Python', ''){}", 1), ("('Python', 'Pe'){}", 1), ("('Python', 'Peithen'){}", 1)]
Wir sehen dass die rekursive Funktion hoch-ineffizient ist. Die Levenshtein-Distanz der Strings s="" und t="P" wird 5336 Mal aufgerufen.
In der folgenden Version fügen wir etwas "Speicher" unserer rekursiven Levenshtein-Funktion hinzu anhand eines Dictionaries:
def call_counter(func):
def helper(*args, **kwargs):
helper.calls += 1
return func(*args, **kwargs)
helper.calls = 0
helper.__name__= func.__name__
return helper
memo = {}
@call_counter
def levenshtein(s, t):
if s == "":
return len(t)
if t == "":
return len(s)
cost = 0 if s[-1] == t[-1] else 1
i1 = (s[:-1], t)
if not i1 in memo:
memo[i1] = levenshtein(*i1)
i2 = (s, t[:-1])
if not i2 in memo:
memo[i2] = levenshtein(*i2)
i3 = (s[:-1], t[:-1])
if not i3 in memo:
memo[i3] = levenshtein(*i3)
res = min([memo[i1]+1, memo[i2]+1, memo[i3]+cost])
return res
print(levenshtein("Python", "Pethno"))
print("The function was called " + str(levenshtein.calls) + " times!")
Der vorige Code ergibt folgende Ausgabe:
3 The function was called 49 times!Diese Version ist nun effizienter, hat aber einen Design-Fehler. Wir haben den Code mit Statements versehen, welche das Dictionary mem verändern. Natürlich ist das Design besser, wenn wir den Code nicht mit der Logik versehen, welche die Werte in de Levenshtein-Funktion speichert. Diesen Code können wir ebenfalls mit einem Dekorateur "auslagern". Folgende Version benutzt einen Dekorateur "memoize" um die Werte zu speichern:
def call_counter(func):
def helper(*args, **kwargs):
helper.calls += 1
return func(*args, **kwargs)
helper.calls = 0
helper.__name__= func.__name__
return helper
def memoize(func):
mem = {}
def memoizer(*args, **kwargs):
key = str(args) + str(kwargs)
if key not in mem:
mem[key] = func(*args, **kwargs)
return mem[key]
return memoizer
@call_counter
@memoize
def levenshtein(s, t):
if s == "":
return len(t)
if t == "":
return len(s)
if s[-1] == t[-1]:
cost = 0
else:
cost = 1
res = min([levenshtein(s[:-1], t)+1,
levenshtein(s, t[:-1])+1,
levenshtein(s[:-1], t[:-1]) + cost])
return res
print(levenshtein("Python", "Peithen"))
print("The function was called " + str(levenshtein.calls) + " times!")
Der Code liefert folgendes Ergebnis:
3 The function was called 127 times!Die zusätzlichen Aufrufe kommen aus den bedingten Aufrufen als Argumente der Funktion "min".
Iterative Berechnung der Levenshtein-Distanz
Um die Levenshtein-Distanz in einer nicht-rekursiven Variante zu berechnen, benutzen wir eine Matrix welche die Levenshtein-Distanzen zwischen allen Präfixes des ersten Strings und allen Präfixes des zweiten Strings. Wir können die Werte in der Matrix dynamisch berechnen. Der letzte berechnete Wert ist die Distanz zwischen den beiden Strings. Dies ist ein Beispiel eines Algorithmus einer dynamischen "Bottum-Up"-Programmierung.Der Algorithmus funktioniert folgendermaßen:
Wir definieren die Gewichtung der Einfüge-, Lösch- und Ersetz-Operationen auf 1. Wir berechnen die Distanz zwischen den beiden Strings s und t mit der len(s) == m und len(t) == n. Eine Matrix D beinhaltet in der Zelle (i,j) die Levenshtein-Distanz zwischen s[:i+1] und t[:j+1]. Die Werte der Matrix werden berechnet beginnend von der linken oberen Ecke bis zur rechten unteren Ecke.
Wir beginnen mit der Berechnung in der Zeile und Spalte mit dem Index 0. Berechnung meint an dieser Stelle, dass die Zeile mit dem Index 0 gefüllt wird mit der Länge der Teil-Strings t, respektive wird die Spalte an dem Index 0 mit der Länge des Teil-Strings s gefüllt.
Die Werte aller anderen Elemente der Matrix sind nur abhängig von den jeweils linken, oberen und links oberen Nachbarn.
Die Berechnung von D(i,j) für i und j größer 0 funktioniert folgendermaßen:
D(i,j) bedeutet, dass wir die Levenshtein-Distanz für die Teil-Strings s[0:i-1] und t[0:j-1] berechnen. Wenn die letzten Zeichen dieser Teil-Strings gleich sind entspricht die Editierdistanz der Distanz der TEil-Strings s[0:-1] und t[0:-1]. Diese kann auch leer sein, wenn s oder t nur ein Zeichen enthält. Wenn die letzten Zeichen von s[0:i-1] und t[0:j-1] nicht gleich sind, entspricht die Editierdistanz D[i,j] der Summe von 1 + min(D[i,j-1], D[i-1,j], D[i-1,j-1]).
Wir stellen es im folgenden Code dar:
def iterative_levenshtein(s, t):
"""
iterative_levenshtein(s, t) -> ldist
ldist is the Levenshtein distance between the strings
s and t.
For all i and j, dist[i,j] will contain the Levenshtein
distance between the first i characters of s and the
first j characters of t
"""
rows = len(s)+1
cols = len(t)+1
dist = [[0 for x in range(cols)] for x in range(rows)]
# source prefixes can be transformed into empty strings
# by deletions:
for i in range(1, rows):
dist[i][0] = i
# target prefixes can be created from an empty source string
# by inserting the characters
for i in range(1, cols):
dist[0][i] = i
for col in range(1, cols):
for row in range(1, rows):
if s[row-1] == t[col-1]:
cost = 0
else:
cost = 1
dist[row][col] = min(dist[row-1][col] + 1, # deletion
dist[row][col-1] + 1, # insertion
dist[row-1][col-1] + cost) # substitution
for r in range(rows):
print(dist[r])
return dist[row][col]
print(iterative_levenshtein("flaw", "lawn"))
Die Ausführung des Codes liefert folgende Ausgabe:
[0, 1, 2, 3, 4] [1, 1, 2, 3, 4] [2, 1, 2, 3, 4] [3, 2, 1, 2, 3] [4, 3, 2, 1, 2] 2Die folgende Abbildung zeigt in der gelben Markierung den optimalen Pfad durch die Matrix. Wir beginnen mit einer Lösch-Operation ("f"), wir behalten das "l" (keine zusätzliche Gewichtung), anschließend behalten wir das "a" und "w". Der letzte Schritt ist eine Einfüge-Operation, welche die Gewichtung auf 2 erhöht. Dies ist die endgültige Levenshtein-Distanz.
Für ein weiteres Beispiel errechnenen wir die Levenshtein-Distanz für unser Beispiel zu Beginn dieses Kapitels. Wir reisen also "zurück" nach New York City und dem spannenden Stadtteil Manhattan. Wir vergleichen es mit dem falschen Schreibweise "Manahaton". Das ist eine Kombination aus diversen falschen Schreibweisen.
print(iterative_levenshtein("Manhattan", "Manahaton"))
Der Code liefert folgendes Ergebnis:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [1, 0, 1, 2, 3, 4, 5, 6, 7, 8] [2, 1, 0, 1, 2, 3, 4, 5, 6, 7] [3, 2, 1, 0, 1, 2, 3, 4, 5, 6] [4, 3, 2, 1, 1, 1, 2, 3, 4, 5] [5, 4, 3, 2, 1, 2, 1, 2, 3, 4] [6, 5, 4, 3, 2, 2, 2, 1, 2, 3] [7, 6, 5, 4, 3, 3, 3, 2, 2, 3] [8, 7, 6, 5, 4, 4, 3, 3, 3, 3] [9, 8, 7, 6, 5, 5, 4, 4, 4, 3] 3Soweit sind die Gewichtungen für Einfüge-, Lösch- und Ersetz-Operationen alle auf 1 gesetzt.
def iterative_levenshtein(s, t, costs=(1, 1, 1)):
"""
iterative_levenshtein(s, t) -> ldist
ldist is the Levenshtein distance between the strings
s and t.
For all i and j, dist[i,j] will contain the Levenshtein
distance between the first i characters of s and the
first j characters of t
costs: a tuple or a list with three integers (d, i, s)
where d defines the costs for a deletion
i defines the costs for an insertion and
s defines the costs for a substitution
"""
rows = len(s)+1
cols = len(t)+1
deletes, inserts, substitutes = costs
dist = [[0 for x in range(cols)] for x in range(rows)]
# source prefixes can be transformed into empty strings
# by deletions:
for row in range(1, rows):
dist[row][0] = row * deletes
# target prefixes can be created from an empty source string
# by inserting the characters
for col in range(1, cols):
dist[0][col] = col * inserts
for col in range(1, cols):
for row in range(1, rows):
if s[row-1] == t[col-1]:
cost = 0
else:
cost = substitutes
dist[row][col] = min(dist[row-1][col] + deletes,
dist[row][col-1] + inserts,
dist[row-1][col-1] + cost) # substitution
for r in range(rows):
print(dist[r])
return dist[row][col]
# default:
print(iterative_levenshtein("abc", "xyz"))
# the costs for substitions are twice as high as inserts and delets:
print(iterative_levenshtein("abc", "xyz", costs=(1, 1, 2)))
# inserts and deletes are twice as high as substitutes
print(iterative_levenshtein("abc", "xyz", costs=(2, 2, 1)))
Wir erhalten folgende Ausgabe:
[0, 1, 2, 3] [1, 1, 2, 3] [2, 2, 2, 3] [3, 3, 3, 3] 3 [0, 1, 2, 3] [1, 2, 3, 4] [2, 3, 4, 5] [3, 4, 5, 6] 6 [0, 2, 4, 6] [2, 1, 3, 5] [4, 3, 2, 4] [6, 5, 4, 3] 3Die Abbildung zeigt die Situation des Aufrufs von iterative_levenshtein mit der Standard-Gewichtung von 1 für Einfüge-, Lösch- und Ersetz-Operationen: Der Inhalt der Matrix sieht folgendermaßen aus, wenn wir Gewichtung der Ersetz-Operationen verdoppeln. Aufruf: iterative_levenshtein("abc", "xyz", costs=(1, 1, 2)): Bei folgendem Aufruf entspricht die Gewichtung der Ersetz-Operation der Hälfte der Einfüge- oder Lösch-Operation: Es ist ebenso möglich individuelle Gewichtungen für jedes Zeichen zu definieren. Anstelle ein Tupel mit drei Werten an die Funktion zu übergeben, nutzen wir ein Dictionary mit Werten für jedes Zeichen:
def iterative_levenshtein(s, t, **weight_dict):
"""
iterative_levenshtein(s, t) -> ldist
ldist is the Levenshtein distance between the strings
s and t.
For all i and j, dist[i,j] will contain the Levenshtein
distance between the first i characters of s and the
first j characters of t
weight_dict: keyword parameters setting the costs for characters,
the default value for a character will be 1
"""
rows = len(s)+1
cols = len(t)+1
alphabet = "abcdefghijklmnopqrstuvwxyz"
w = dict( (x, (1, 1, 1)) for x in alphabet + alphabet.upper())
if weight_dict:
w.update(weight_dict)
dist = [[0 for x in range(cols)] for x in range(rows)]
# source prefixes can be transformed into empty strings
# by deletions:
for row in range(1, rows):
dist[row][0] = dist[row-1][0] + w[s[row-1]][0]
# target prefixes can be created from an empty source string
# by inserting the characters
for col in range(1, cols):
dist[0][col] = dist[0][col-1] + w[t[col-1]][1]
for col in range(1, cols):
for row in range(1, rows):
deletes = w[s[row-1]][0]
inserts = w[t[col-1]][1]
subs = max( (w[s[row-1]][2], w[t[col-1]][2]))
if s[row-1] == t[col-1]:
subs = 0
else:
subs = subs
dist[row][col] = min(dist[row-1][col] + deletes,
dist[row][col-1] + inserts,
dist[row-1][col-1] + subs) # substitution
for r in range(rows):
print(dist[r])
return dist[row][col]
# default:
print(iterative_levenshtein("abx",
"xya",
x=(3, 2, 8),
y=(4, 5, 4),
a=(7, 6, 6)) )
#print(iterative_levenshtein("abc", "xyz", costs=(1,1,substitution_costs)))
Wir erhalten folgende Ausgabe:
subs: 8 deletes: 7 inserts: 2 a x subs: 8 deletes: 1 inserts: 2 b x subs: 0 deletes: 3 inserts: 2 x x subs: 6 deletes: 7 inserts: 5 a y subs: 4 deletes: 1 inserts: 5 b y subs: 8 deletes: 3 inserts: 5 x y subs: 0 deletes: 7 inserts: 6 a a subs: 6 deletes: 1 inserts: 6 b a subs: 8 deletes: 3 inserts: 6 x a [0, 2, 7, 13] [7, 8, 8, 7] [8, 9, 9, 8] [11, 8, 12, 11] 11Die folgende Abbildung illustriert die Funktionsweise des Algorithmus mit gewichteten Zeichen. Die orangenen Pfeile zeigen den Pfad der kleinsten Editierdistanz 11.