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

Damerau hat in einer Untersuchung 36 festgestellt, dass 80% der Rechtschreib-
fehler in eine von vier Kategorien fallen: ein Buchstabe ist falsch, ein Buchstabe
fehlt, ein zusätzlicher Buchstabe wurde eingefügt oder zwei nebeneinander lie-
gende Buchstaben wurden vertauscht. Die drei erst genannten Kategorien werden
mit einer einzigen Edit-Operation von der Levenshtein-Distanz behandelt, ver-
tauschte Buchstaben verursachen jedoch zwei Edit-Operationen 37 . Die Damerau-
Levenshtein-Distanz erweitert daher die Levenshtein-Distanz um eine zusätzliche
Edit-Operation „Vertauschen“ 38 Dies geschieht, indem in die Rekursionsgleichung
der Levenshtein-Distanz zusätzlich der Term

C i − 2 , j − 2 + d ( x i − 1 , y j )+ d ( x i , y j − 1 )+ 1

in die Minimierung eingefügt wird.

2.4.2 Tokenbasierte Ähnlichkeitsmaße
Bei der Edit-Distanz werden die Buchstaben in ihrer Reihenfolge verglichen 39 . Bei
Zeichenketten mit mehreren Wörtern können die Wörter jedoch unterschiedliche
Reihenfolgen und dabei doch eine ähnliche Bedeutung aufweisen. Für die Zei-
chenketten „Max Mustermann“ und „Mustermann, Max“ beträgt die Edit-Distanz
beispielsweise 9, obwohl es sich intuitiv um die gleichen Personen handelt. To-
kenbasierte Verfahren zerlegen die Zeichenketten in Token und prüfen dann, wie
viele Token in beiden Zeichenketten identisch sind. Die Zerlegung in Token kann
entweder anhand von Trennzeichen erfolgen (z.B. Leerzeichen, Satzzeichen) oder
es werden n-Gramme gebildet.
Schürle 40 definiert n-Gramme wie folgt: „ Gegeben sei eine beliebige Zeichen-
kette A. Unter einem n-Gramm von A versteht man eine Zeichenkette der Länge
n, welches als ganzes, d.h. ohne Unterbrechung, in A enthalten ist. “ Damit jeder
Buchstabe in exakt n n-Grammen enthalten ist, werden oft noch n-1 Leerzeichen
am Anfang und Ende der Zeichenkette eingefügt 41 .
Vergleicht man beispielsweise die Zeichenketten „Mayer“ und „Maier“ mit n=3,
so ergeben sich folgende Mengen von 3-Grammen 42 :

36 vgl. [9], S. 171
37 Entweder es werden beide Buchstaben in den Wert des anderen geändert oder es wird ein Buchstabe
gelöscht und an der richtigen Stelle wieder eingefügt.
38 vgl. [21], S. 177 ff.
39 vgl. hierzu und zum Folgenden [19], S.339
40 [32], S. 38
41 vgl. [29], S. 670
42 3-Gramme werden auch Trigramme genannt