Duplikaterkennung - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 16

Konvertierung von x 1 .. i − 1 nach y 1 .. j − 1 . Sind x i und y j nicht gleich, so bestehen
ausgehend von den erlaubten Edit-Operationen drei Möglichkeiten 32 :

1. Löschen von x i mit Kosten von 1 und Addition der Edit-Distanz für die
Konvertierung von x 1 .. i − 1 nach y 1 .. j .

2. Einfügen von y i am Ende von x 1 .. i mit Kosten von 1 und Addition der Edit-
Distanz für die Konvertierung von x 1 .. i nach y 1 .. j − 1 .

3. Ersetzen von x i durch y i mit Kosten von 1 und Addition der Edit-Distanz für
die Konvertierung von x 1 .. i − nach y 1 .. j − 1 .

Der Algorithmus zum Befüllen der Matrix arbeitet bottom-up. Die Matrix hat

| x | + 1 Spalten und | y | + 1 Zeilen und wird zunächst mit den Randbedingungen

C i , 0 = j befüllt. Anschließend können sukzessive die Werte derjeni-

gen Zellen berechnet werden, deren linker, oberer und linker-oberer Zellnachbar
bereits berechnet wurden. Dies kann beispielsweise spalten- oder zeilenweise er-
folgen. Die Komplexität des Algorithmus ist O

i und C 0 , j =

. Abbildung 2.2 zeigt dies
für die Zeichenketten „Levenshtein“ und „Meilenstein“. Die Pfeile zeigen den je-
weils optimalen Weg
Aus der Matrix kann anschließend das Transkript abgelesen werden, welches die
einzelnen Änderungsoperationen beschreibt 33 . Beginnend mit Zelle C | x |,| y | springt
man immer zu derjenigen Zelle links, oberhalb oder diagonal links-oben, deren
Zellwert plus die jeweiligen Schrittkosten den aktuellen Zellwert ergeben. Existie-
ren mehrere Alternativen, so handelt es sich um verschiedene valide Edit-Opera-
tionen. Sprünge ohne Edit-Operation bzw. Ersetzen-Operationen entsprechen ei-
nem diagonalen Sprung, Lösch-Operationen einem Sprung nach links und Einfü-
ge-Operationen einem Sprung nach oben. Abbildung 2.3 zeigt das Transkript für
das vorherige Beispiel. Hierbei bedeutet ein „=“ keine Operation, ein „+“ Einfü-
gen eines Buchstabens, ein „-“ Löschen eines Buchstabens und ein „x“ Ersetzen
eines Buchstabens.
Die Levenshtein-Distanz muss anschließend noch in ein Ähnlichkeitsmaß um-
gewandelt werden 34 . Hierfür erfolgt eine Normalisierung auf die längere Zeichen-
kette und anschließend wird der Wert von 1 subtrahiert.

( | x |·| y | )

ed ( x , y )

sim ed ( x , y ) : = 1 −

max {| x |,| y |}

32 Die Kosten für Edit-Operation müssen nicht 1 sein, sondern können für eine verschiedene Gewich-
tung von Lösch-, Einfüge- und Änderungsoperationen abweichen.
33 vgl. hierzu und zum Folgenden [19]. S. 337
34 vgl. hierzu und zum Folgenden [19]. S. 337