aldebaran Knowhow

Softwareunterstützte Dublettensuche

Dubletten sind unerwünschte doppelte Datensätze, die ein und dasselbe Objekt bezeichnen. Dieser Artikel beschreibt anhand einer von aldebaran entwickelten Adressdatenbank, wie man das Problem der Dublettensuche rechnergestützt angehen kann. Die Anwendung wurde in Java realisiert.

Zurück zur Übersicht

Hintergrund

Dubletten sind doppelte Datensätze, die ein und dasselbe Objekt bezeichnen, z.B. eine versehentlich mehrfach aufgenommene Adresse; evtl. in etwas unterschiedlicher Schreibweise.

Gewünscht ist aber natürlich ein eindeutiger Bezug:

• Ein Kunde steht nur einmal, und zwar mit der korrekten Adresse, in der Kundendatenbank.
• Für ein Buch gibt es genau eine Karte im Bibliothekskatalog.

Bei der Pflege von Daten kommt es im Laufe der Zeit meist zu Fehlern, unter anderem zu Dubletten. Verzichtet man auf das Aufspüren und Löschen der Dubletten, so verwässert der Datenbestand und verliert an Wert:

• Veraltete Adressen bleiben im Bestand.
• Mailingaktionen verteuern sich und verärgen "mehrfach bedachte" Kunden.
• Bücher lassen sich in einem unnötig großen Karteikasten schlechter finden.

Dieser Artikel beschreibt anhand einer von aldebaran entwickelten Adressdatenbank, wie man das Problem der Dublettensuche rechnergestützt angehen kann. Die Anwendung wurde in Java realisiert.

Entstehung von Dubletten

Bei einer Adressdatenbank sind die häufigsten Ursachen für Dubletten:

1. Datensätze, die versehentlich doppelt aufgenommen werden, weil sich Namen auf verschiedene Arten schreiben lassen (häufig bei der telefonischen Aufnahme der Daten)
   Ergebnis: Frida Maier <=> Frieda Meyer
2. ein gewöhnliches "Vertippen", insbesondere Buchstabenauslassungen, -verdopplungen, -dreher
   Wilhelm Hausmann <=> Wilhem Haumsann
3. die Anlage eines neuen Datensatzes beim Umzug einer Person, statt der Korrektur der bisherigen Anschrift
   Ergebnis:
   Friedrich Küppersbusch, Lange Straße 5 <=>
   Friedrich Küppersbusch, Kurzer Weg 8

Daraus ergeben sich als Anforderungen an eine Dublettensuche:

für 1:
Erkennen von gleichklingenden Wörtern, sog. Homophonen

für 2:
Erkennen von "ähnlichen" Wörtern mit nur geringen Abweichungen, z.B. Hausmann und Haumsann

für 3:
Vergleichsmöglichkeit ausgewählter Datenfelder, z.B. für "Umgezogene" Vergleich des Namens und der Email, aber nicht der Adressfelder

Auf 1 und 2, die Homophonen und die "ähnlichen" Wörter, gehen wir zunächst näher ein:

Gleichsetzung ähnlicher Schreibweisen

Die grundlegende Idee ist, ein geeignetes Ähnlichkeitsmaß zu bestimmen, welches bei der Anwendung auf zwei Zeichenketten (o. a. "Strings") in Form einer Zahl Auskunft darüber gibt, wie stark diese sich gleichen; diese Zahl kann man sich als eine Art "Abstand" vorstellen. Beträgt der Abstand 0, so sind die Zeichenketten identisch. Je größer die Zahl ist, desto mehr weichen sie voneinander ab.

Das bekannteste derartige Maß ist die Levenshtein-Distanz (benannt nach dem Mathematiker Vladimir I. Levenštejn). Sie gibt die minimale Anzahl der benötigten Einfügungen, Löschungen oder Substitutionen an, um die zu vergleichenden Zeichenketten ineinander zu überführen. So ist der Abstand zwischen den Zeichenketten "schlau"; und "schlank"; gleich 2, da mindestens zweimal von den drei Operationen "einfügen", "löschen", "substituieren" Gebrauch gemacht werden muss. Bezeichnet etwa "dL" die Levenshtein-Distanz, so bringen wir dieses durch

d_L("schlau", "schlank") = 2

zum Ausdruck.

Gerade in Bezug auf die relativ leicht unterlaufenden "Dreher" bei der manuellen Eingabe von Daten ist die Levenshtein-Distanz ungeeignet. So ist etwa auch

d_L("schlau", "shclau") = 2,

das heißt bei Verwendung der Levenshtein-Distanz, sind sowohl "schlank" als auch "shclau" im selben Maße dem Wort "schlau" ähnlich.

Die naheliegende Lösung ist, auch das Vertauschen, o. a. die Transposition, zweier benachbarter Buchstaben als weitere Operation zuzulassen. Das resultierende Maß ist die Damerau-Distanz, in Zeichen "d_D" (benannt nach Fred J. Damerau): Sie ist gleich der minimalen Anzahl der benötigten Einfügungen, Löschungen, Substitutionen oder Transpositionen, die benötigt werden, um eine von zwei gegebenen Zeichenketten in die andere zu überführen.

Entsprechend gilt zwar wie im Falle von d_L

d_D("schlau", "schlank") = 2,

aber abweichend

d_D("schlau", "shclau") = 1.

Obwohl die Berechnung der Damerau-Distanz etwas aufwändiger ist als die der Levenshtein-Distanz, ist im Hinblick auf die relativ häufige Vertauschung zweier Buchstaben die Damerau-Distanz vorzuziehen.

Im Rahmen einer programmgestützten Dublettensuche ist es demnach sinnvoll, zwei Zeichenketten, deren Distanz unter einer Schranke L liegt, zu identifizieren, d. h. gleichzusetzen, also über kleine Schreibfehler "hinwegzusehen". Die Wahl der geeignete Schranke beruht auf den Ergebnissen von Versuchsreihen. Naheliegend ist in jedem Falle, L in Abhängigkeit von der Länge der beteiligten Strings zu wählen. Darüberhinaus ist es stets sinnvoll, dem Anwender der Dublettensuche einen Einfluss auf diese Schranke zu gewähren, natürlich unter Kapselung des hier erläuterterten technischen Hintergrundes.

Gleichsetzung gleichklingender Schreibweisen

Da die Identifizierung von Homophonen sprachabhängig ist, sind die meisten frei zur Verfügung stehenden Algorithmen eher auf die englische Sprache ausgerichtet. Allen gleich ist die Anforderung, eine Eingabezeichenkette so abzubilden, dass die Ausgaben für gleichklingende Eingaben identisch sind. Darüberhinaus besteht der Wunsch, die Bildmenge, das heißt die Menge der möglichen Ausgaben der Umformung, möglichst groß zu halten.

Bezeichnet etwa "h"; eine solche Abbildung, so soll die Identität

h("Maier") = h("Meyer")

gelten, dagegen aber

h("Maler") != h("Mueller").

Das bekannteste Verfahren ist recht alt (Anfang 20. Jhd.) und trägt heute üblicherweise den Namen "Soundex". Hier werden fast alle Konsonanten des Alphabetes gemäß ihres Klanges in sechs Klassen aufgeteilt, die übrigen Konsonanten als auch sämtliche Vokale finden keine Beachtung. Die Ausgabe von Soundex entspricht dem ersten Buchstaben der Eingabe ergänzt durch einen dreistelligen Zahlencode, der sich unmittelbar aus den weiteren Buchstaben der Eingabe mittels der erwähnten Klasseneinteilung ergibt. Bezeichnet "h_S" die Soundex-Abbildung, so ist etwa

h_S("Maler") = M460.

Allerdings lässt sich schon anhand der skizzierten Beschreibung erkennen, dass diese Abbildung recht grob ist, in dem Sinne, dass viele Eingabezeichenketten, die sehr unterschiedlich klingen, doch dieselbe Ausgabe haben. So gilt dann auch

h_S("Mueller") = M460,

der Soundex-Algorithmus ist demnach im Rahmen einer Dublettensuche ungeeignet.

Erfreulicherweise hat in der Zeitschrift c't der Autor Jörg Michael das Programm "phone" vorgestellt, welches unter Verwendung von hunderten Regeln, die speziell auf die deutsche Sprache abgestimmt sind, genau die eingangs erwähnten Anforderungen erfüllt. Die Ausgaben des phonet-Algorithmus', dessen Abbildung hier mit "h_P" bezeichnet wird, bilden dabei im Gegensatz zum Soundex-Algorithmus alle Eingaben derart ab, dass die Ausgabe ähnlich der Eingabe klingt. Man kann also etwas überspitzt von einer Art "Normalform" von gleichlautenden Zeichenketten sprechen. Als Beispiel seien hier die Anwendung von phonet auf diverse Schreibarten des Namens "Meyer" genannt. Es gilt

h_P("Maier") = h_P("Mayer") = h_P("Meier") = h_P("Meyer") = "MEIA".

Der Vollständigkeit halber sei an dieser Stelle noch erwähnt, dass das Programm phonet zwei Regelsätze zur Normalisierung der Eingaben besitzt. In diesem Artikel kommt dabei stets der erste Regelsatz zur Anwendung, der die Eingaben etwas feiner kategorisiert als der zweite.

Diverse Testläufe mit dem phonet-Algorithmus lieferten sehr befriedigende Ergebnisse. Eine weitere Anpassung des Regelwerkes ist möglich, wenn auch nicht ganz einfach, da es leicht zu unerwünschten Seiteneffekten kommt.

Umsetzung

Nur vollständig identische Datensätze können von einem Programm als Doubletten identifiziert und gelöscht werden. Schon bei kleinen Abweichungen muss ein Mensch entscheiden, welcher der Datensätze ggf. zu korrigieren bzw. zu verwerfen ist.

Ziel unserer Dublettensuche war es daher, Listen von ähnlichen und daher mglw. doppelten Datensätzen im Datenbestand zu bilden und dem Benutzer zur Entscheidung zu übergeben.

Leider ist es schon bei mittelgroßen Datenbeständen (im konkreten Fall ging es um ca. 15.000 Adressen) nicht möglich, jeden Datensatz anhand der oben ganannten Techniken gegen jeden anderen zu vergleichen (der Aufwand steigt quadratisch mit der Anzahl der Datensätze). Erschwerend kam dabei eine Vielzahl von Datenfeldern je Datensatz hinzu. Die gewählte Lösung bestand darin, zunächst die Gesamtmenge aller Datensätzen in kleinere "Ausgangsmengen" zu zerlegen. Alle diese Ausgangsmengen weisen dabei als gemeinsames, kennzeichnendes Merkmal ein identisches sogenanntes "Pivot-Feld" auf. Der Ausdruck Pivot-Feld rührt aus dem gewählten Datenfeld als "Dreh- und Angelpunkt" der weiteren Suche her. Das Pivot-Feld wird dabei vom Anwender der Dublettensuche bestimmt; eine besonders günstige Wahl sind hier zusätzlich eingeführte, synthetische Datenfelder, in denen jeweils die "phonetische Normalform" (im obigen phonet-Sinne) ihrer Stammfelder hinterlegt ist.

In einigen Fällen sind aber selbst die eben genannten Ausgangsmengen mit identischem Pivotfeld zu umfangreich, sodass eine weitere Gruppierungsmöglichkeit anhand eines benutzerbestimmten Feldes eingeführt wurde. Diese zweite Aufteilung ist aber absichtlich nicht trennscharf in dem Sinne, dass es sinnvoll sein kann, ein und denselben Datensatz in mehreren Gruppen zu führen.

Der letzte Schritt unserer Dublettensuche ist eine Ermittlung aller beteiligter Damerau-Distanzen innerhalb aller gewählten Datenfelder einer Gruppe. Je nach Ergebnis einer gewissen Verrechnung dieser Abstände können dem Benutzer mögliche Dubletten in Form einer Liste präsentiert werden.

Die Einflussnahme auf die oben eingeführte Schranke L in Bezug auf die Damerau-Distanzen erfolgen durch die Wahl einer Toleranzstufe seitens des Benutzers, die Art der im letzten Absatz nicht weiter erläuterten "Verrechung" mittels eines weiteren Auswahlknopfes. Der entwickelte Dialog zur Dublettensuche entpricht im wesentlichen dem abgebildeten: