Softwareunterstützte Dublettensuche

Dubletten sind unerwünschte doppelte Datensätze, die beispielsweise häufig in Adressdatenbanken auftreten. Dieser Artikel systematisiert Klassen von Dubletten und stellt Lösungsstrategien vor, um Dubletten zu identifizieren und zu entfernen. Eine von aldebaran in Java realisierte Anwendung setzt dieses Wissen praktisch um.

Was sind Dubletten und wieso sind sie unerwünscht?

Im Zusammenhang mit Adressdatenbanken sind Dubletten Datensätze, die eine Person bzw. Institution bezeichnen, die aber bereits in einem vorangehenden Datensatz erfasst ist. Dabei ist es die Regel, dass solche doppelten Datensätze trotz desselben Bezuges voneinander abweichen. Dies umfasst beispielsweise eine mehrfach aufgenommene Person mit unterschiedlichen Adressen oder Variationen, die durch unterschiedliche Schreibweise entstehen.

In dieser Reihenfolge gelesen, sind die Datensätze 2. bis 4. als Dubletten des Datensatzes 1. zu sehen. Gleichwertig kann man jegliche drei dieser Datensätze als Dubletten des verbliebenen Datensatzes bezeichnen.

Entstehung von Dubletten

Dubletten entstehen, wenn Adressdatenbanken erweitert werden, sei es durch einzelne Datensatzaufnahmen oder durch das Zusammenführen ganzer Datenbanken. Ursächlich für Dubletten ist immer ein unterbliebener oder unzureichender Abgleich mit den bestehenden Datensätzen. Der manuelle Abgleich wird dabei erschwert, weil bei einer Suche in den Bestandsdaten kein Treffer erzielt wird:

Bei der Ersteingabe kam es zu Tippfehlern (Buchstabenauslassungen, -verdopplungen, -dreher, z.B. Wilhelm Hausmann ⇔ Wilhem Haumsann)

Namen lassen sich auf verschiedene Arten schreiben (problematisch insbesondere bei der telefonischen Aufnahme, z.B. Frida Maier ⇔ Frieda Meyer)

Die Person ist mittlerweile umgezogen, die alte Adresse wird aber bei der Suche als Kriterium mit herangezogen (und statt der Korrektur der bisherigen Anschrift kommt es zur Neuaufnahme, z.B. zusätzlich zu „Fritz Busch, Hauptstraße 1“ wird auch „Fritz Busch, Nebenstraße 1“ erfasst)

Daraus ergeben sich an eine softwaregestützte Dublettensuche an obige Aspekte anknüpfend folgende Anforderungen:

Erkennen von „ähnlichen“ Wörtern mit nur „geringen“ Abweichungen

Erkennen von gleich klingenden Wörtern, sog. Homophonen

Vergleichsmöglichkeit ausgewählter Datenfelder, z.B. bei umgezogenen Personen der Vergleich des Namens und der Email ohne Berücksichtigung der Anschrift

Gleichsetzung ähnlicher Schreibweisen

Um ähnliche Schreibweisen zu identifizieren lässt sich ein Ähnlichkeitsmaß nutzen. Dies ist eine Abbildung, die zwei Zeichenketten (o. a. Strings) eine Zahl zuordnet. Diese Zahl wird als Abstand der Argumente interpretiert. 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 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 oben genannten drei Operationen Gebrauch gemacht werden muss. Bezeichnet etwa „d_L“ die Levenshtein-Distanz, so gilt

In Bezug auf die bei der manuellen Eingabe relativ leicht unterlaufenden „Dreher“ ist die Levenshtein-Distanz allerdings keine günstige Wahl. So ist etwa auch

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

aber abweichend

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

Für eine Dublettensuche ist es sinnvoll, zwei Zeichenketten, deren Distanz unter einer Schranke L liegt, gleichzusetzen und so über kleine Schreibfehler „hinwegzusehen“. Der letzten Endes in der Anwendung gewählte Schrankenwert, beruht auf den Ergebnissen von vielen Versuchsreihen. Es ist in jedem Falle ratsam, L in Abhängigkeit von der Länge der beteiligten Strings zu wählen. Darüber hinaus kann es hilfreich sein, dem Anwender des Programms einen Einfluss auf diese Schranke zu gewähren.

Gleichsetzung gleichklingender Schreibweisen

Da die Identifizierung von Homophonen sprachabhängig ist, sind die meisten frei zur Verfügung stehenden Algorithmen auf die englische Sprache ausgerichtet. Allen gleich ist die Anforderung, eine Eingabezeichenkette so abzubilden, dass die Ausgaben für gleichklingende Eingaben identisch sind. Darüber hinaus besteht der Wunsch, die Bildmenge, das heißt die Menge der möglichen Ausgaben der Umformung, möglichst groß zu halten (zur Verdeutlichung ein Extrembeispiel: Bildet man jede beliebige Zeichenkette auf die Zeichenkette „Autsch“ ab, so haben zwar u. a. gleichklingende Eingabezeichenketten dieselbe Ausgabe, nämlich „Autsch“, aber eben auch gänzlich anders lautende Eingabezeichenketten; es wäre hinsichtlich der Prüfung auf Dubletten nichts gewonnen).

Bezeichnet etwa „h“ eine solche Abbildung, so soll die Identität

gelten, dagegen aber

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 Klangs in sechs Klassen aufgeteilt; sowohl 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

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

Der weit verbreitete Soundex-Algorithmus ist demnach im Rahmen einer Dublettensuche ungeeignet.

Als Alternative hat in der Zeitschrift c't der Autor Jörg Michael das Programm „phonet“ vorgestellt. Es verwendet hunderte von Regeln, die speziell auf die deutsche Sprache abgestimmt sind, und erfüllt genau die eingangs erwähnten Anforderungen. 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 daher von einer Art „Normalform“ von Zeichenketten sprechen. Ein Beispiel ist die Anwendung auf diverse Schreibarten des Namens „Meyer“; es gilt

Der Vollständigkeit halber ist zu ergänzen, dass das Programm phonet zwei Regelsätze zur Normalisierung besitzt. In diesem Artikel als auch in der Umsetzung kommt stets der erste Regelsatz zur Anwendung, der die Eingaben etwas feiner kategorisiert. Eine Anpassung des Regelwerks ist zwar machbar, aber erfahrungsgemäß selten lohnenswert, da ein hoher Aufwand nur im Detail geringe Verbesserungen erzielt und leicht unerwünschte Seiteneffekte auftreten.

Umsetzung einer Adressverwaltung mit integrierter Dublettensuche

Nur gänzlich identische Datensätze können programmatisch auf einfachste Weise als Dubletten 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 der von aldebaran entwickelten Dublettensuche ist es daher, Listen von ähnlichen und daher möglicherweise mehrfachen Datensätzen im Datenbestand zu bilden und dem Benutzer zur Entscheidung vorzulegen.

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 genannten Techniken gegen jeden anderen zu vergleichen – der Aufwand steigt quadratisch mit der Anzahl der Datensätze. Auch eine große Anzahl von Datenfeldern je Datensatz erschwert das Vergleichen. Die gewählte Lösung zerlegt daher die Gesamtmenge aller Datensätzen zunächst in kleinere Teilmengen. Alle diese Mengen weisen dabei als gemeinsam 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.

Der letzte Schritt einer Dublettensuche ist die Ermittlung aller beteiligten Damerau-Distanzen innerhalb der gewählten Datenfelder einer Teilmenge. Je nach Ergebnis einer gewissen Verrechnung dieser Abstände werden dem Benutzer mögliche Dubletten in Form einer Liste präsentiert.

Die Einflussnahme auf die oben eingeführte Schranke L in Bezug auf die Damerau-Distanzen erfolgt durch die Wahl einer Toleranzstufe seitens des Benutzers. Die genaue Art der im letzten Absatz nicht näher erläuterten „Verrechnung“ geschieht mittels weiterer Auswahlmöglichkeiten.

In der von aldebaran entwickelten Adressverwaltung kommen hinsichtlich der Dublettensuche zusätzliche, bisher nicht genannte Techniken zum Einsatz. So helfen noch vor den genannten Vergleichen verschiedene Stoppwortlisten sowie ausführliche automatische Transformationen und verbessern in der Folge die Qualität der vorgelegten Listen von Dublettenkandidaten.

Schlussbemerkungen

Eine leistungsfähige, softwaregestützte Dublettensuche benötigt gründliche Vorüberlegungen. Diese tragen dazu bei, den unvermeidlichen Arbeitsaufwand für die Bereinigung der vorhandenen Dubletten zu minimieren.

Um bereinigte Datensätze vor erneuten Dubletten zu bewahren, sieht die Softwarelösung von aldebaran bereits bei der Anlage neuer Datensätze eine „On-the-fly“-Dublettensuche vor und kann so den Nutzer frühzeitig automatisch vor der Anlage einer Dublette warnen.

Wenn Sie Fragen oder Interesse an einer Lösung zum Dublettenabgleich haben, sind wir Ihnen natürlich gerne behilflich!