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

Die Funktion sim ist ein domänen- und typspezifisches Ähnlichkeitsmaß für ein
einzelnes Attribut. In den folgenden Unterkapiteln werden solche Ähnlichkeits-
maße beschrieben.

2.4.1 Edit-basierte Ähnlichkeitsmaße

Edit-basierte Ähnlichkeitsmaße vergleichen zwei Zeichenketten buchstabenwei-
se. Je mehr Buchstaben übereinstimmen, desto ähnlicher sind sich die Zeichen-
ketten. Ein weit verbreitetes Edit-basiertes Ähnlichkeitsmaß ist die Levenshtein-
Distanz 27 bzw. Edit-Distanz. Sie ist definiert als die minimale Anzahl von Edit-
Operationen, um eine Zeichenkette in eine andere Zeichenkette zu transformieren.
Edit-Operationen sind Einfügen, Löschen und Ersetzen eines Buchstabens.
Zur Berechnung der Levenshtein-Distanz existieren verschiedene Algorithmen.
Der in diesem Kapitel vorgestellte Algorithmus basiert auf der dynamischen Pro-
grammierung 28 . Gegeben sind zwei Zeichenketten x und y , für die die Edit-Distanz
ed

gesucht wird. Es wird eine Matrix C 0 ..| x |, 0 ..| y | erzeugt, wobei C i , j die mi-
nimale Anzahl an Edit-Operationen darstellt, um x 1 .. i in y 1 .. j zu konvertieren 29 .
Die Werte der Matrix können mit einer Rekursionsgleichung 30 formuliert werden:
C i , 0 =

( x , y )

i

C 0 , j = j

, = [

C i − 1 , j +

,

Ci j min 1

C i , j − 1 + ,

C i − 1 , j − 1 +

1

d ( x i , y j )]

mit

d ( x i , y j )= 0 wenn x i = y j

= 1 ansonsten

j bezeichnen
die Edit-Distanz zwischen einer Zeichenkette der Länge i bzw. j und einer leeren
Zeichenkette. In diesem Fall werden für die Konvertierung i bzw. j Löschoperatio-
nen benötigt 31 . Für zwei nicht leere Zeichenketten der Länge i , j betrachtet man
die letzten Buchstaben x i und y j . Gilt x i =

Für die Edit-Distanz gilt dann ed ( x , y )= C | x |,| y | . C i , 0 = i und C 0 , j =

y j , so ist keine Edit-Operation für den
letzten Buchstaben notwendig und die Edit-Distanz entspricht derjenigen für die

27 vgl. [20]
28 vgl. hierzu und zum Folgenden [35] S. 171 f.
29 x 1 .. i ist ein Präfix der Länge i von der Zeichenkette x . Analog ist y 1 .. j ist ein Präfix der Länge j von
der Zeichenkette y .
30 vgl. hierzu und zum Folgenden [25], S. 43 f.
31 Aus Sicht der leeren Zeichenkette können auch i , j Einfüge-Operationen verwendet werden.