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

N 1 :={„ M“, „ Ma“, „May“, „aye“, „yer“, „er “, „r “}

N 2 :={„ M“, „ Ma“, „Mai“, „aie“, „ier“, „er “, „r “}

Daraus ergibt sich:

∪

N 1 N 2 :={„ M“, „ Ma“, „May“, „aye“, „yer“, „Mai“, „aie“,

„ier“, „er “,„r “}

N 1 ∩ N 2 :={„ M“,„ Ma“, „er “,„r “}

Zur Bestimmung der Ähnlichkeit zweier Zeichenketten existieren verschiedene
Berechnungsvorschriften. Der Wertebereich der Ähnlichkeit liegt wiederum zwi-
schen 0 für komplett unterschiedliche Zeichenketten und 1 für identische Zeichen-
ketten. Ein viel verwendetes Maß ist die Jaccard-Ähnlichkeit, die die Anzahl der
gemeinsamen Token beider Zeichenketten mit der Anzahl unterschiedlicher Token
beider Zeichenketten vergleicht 43 .

= |

∩ |

N 1 N 2

sim Token 1 ( x , y ) :

| N 1 ∪ N 2 |

Ein zweites Maß ist der Dice-Koeffizient 44 , der im Nenner nicht mehr die An-
zahl unterschiedlicher n-Gramme von N 1 und N 2 enthält, sondern deren durch-
schnittliche Anzahl.

| N 1 ∩ N 2 |

sim Token 2 ( x , y ) : =

0 , 5 · ( | N 1 | + | N 2 | )

Aus sim Token 2 lässt sich dann noch ein drittes Maß ableiten, welches jedoch statt
dem arithmetischen Mittel das geometrische Mittel im Nenner verwendet 45 .

| N 1 ∩ N 2 |

sim Token 3 ( x , y ) : = |

N 1 |·| N 2 |

Für die Zeichenketten „Mayer“ und „Maier“ zeigt Tabelle 2.1 die berechnete
Distanz für die bisher vorgestellten Ähnlichkeitsmaße.

Ähnlichkeitsmaß sim Token 1 sim Token 2 sim Token 3 sim ed

2
5

4
7

4
7

4
5

Wert

Tabelle 2.1: Ähnlichkeit für „Mayer“ und „Maier“

43 vgl. [19], S. 339
44 vgl. [2], S. 256 f.
45 vgl. [32], S. 39