Dublettenprüfung in großen Datenbeständen

Das Problem: Datenqualität in gewachsenen Beständen

Wer mit großen Personendatenbeständen arbeitet, ob in der Finanzbranche, bei Leasinggesellschaften oder in der öffentlichen Verwaltung, kennt das Thema: Über Jahre hinweg wachsen Datenbestände, werden aus verschiedenen Quellen zusammengeführt, und irgendwann stellt sich die Frage, wie viele Personen haben wir eigentlich wirklich? Die Antwort ist oft ernüchternd. Gerade in Behörden, wo Daten aus kommunalen, Landes- und Bundesregistern zusammenfließen, entstehen Dubletten durch Tippfehler, unterschiedliche Schreibweisen, Systemmigrationen und fehlende gemeinsame Identifikatoren. Im Kontext von Adressqualifizierung und Scoring, etwa bei Leasinggesellschaften, oder bei der Zusammenführung von Registerdaten in der öffentlichen Verwaltung ist saubere Datenqualität nicht optional, sondern geschäftskritisch.

Die Herausforderung bei der Dublettenprüfung liegt darin, dass ein einfacher String-Vergleich nicht ausreicht. “Müller” und “Mueller”, “Hauptstraße 5” und “Hauptstr. 5”, “Schmidt” und “Schmitt”, das sind für einen Computer völlig verschiedene Strings, für einen Menschen aber offensichtlich dieselbe Person oder Adresse.

Phonetische Algorithmen: Klang statt Zeichen

Der erste Ansatz zur Lösung dieses Problems sind phonetische Algorithmen. Sie bilden Zeichenketten auf einen Code ab, der repräsentiert, wie ein Wort klingt, nicht wie es geschrieben wird.

Soundex

Der klassische Soundex-Algorithmus stammt aus den 1920er-Jahren und wurde ursprünglich für den US-Census entwickelt. Er funktioniert für englische Namen akzeptabel, versagt aber bei deutschen Phonemen. “Schmidt” und “Schmitt” erhalten zwar denselben Code, aber bei vielen typisch deutschen Namen ist die Trefferquote unbefriedigend.

Kölner Phonetik

Die Kölner Phonetik (Cologne Phonetic) wurde speziell für die deutsche Sprache entwickelt und berücksichtigt deren phonetische Besonderheiten. Sie behandelt Umlaute korrekt, unterscheidet zwischen hartem und weichem “ch” und kennt typisch deutsche Lautkombinationen.

// Apache Commons Codec bietet eine fertige Implementierung
ColognePhonetic cologne = new ColognePhonetic();
String code1 = cologne.colognePhonetic("Müller");
String code2 = cologne.colognePhonetic("Mueller");
// Beide liefern denselben phonetischen Code
boolean match = cologne.isEncodeEqual("Müller", "Mueller"); // true

In der Praxis hat sich die Kölner Phonetik als deutlich überlegen gegenüber Soundex erwiesen, wenn es um deutsche Personennamen geht. Allerdings reicht ein einzelner Algorithmus selten aus.

Levenshtein-Distanz: Wie ähnlich sind zwei Strings?

Die Levenshtein-Distanz misst die minimale Anzahl von Einfüge-, Lösch- und Ersetzungsoperationen, die nötig sind, um einen String in einen anderen zu überführen. Sie eignet sich besonders gut für Postanschriften, bei denen phonetische Algorithmen an ihre Grenzen stoßen.

// Normalisierte Levenshtein-Distanz als Ähnlichkeitsmaß
public static double similarity(String s1, String s2) {
    int distance = levenshteinDistance(s1, s2);
    int maxLength = Math.max(s1.length(), s2.length());
    return 1.0 - ((double) distance / maxLength);
}

Ein normalisierter Wert zwischen 0 und 1 ermöglicht es, Schwellenwerte zu definieren: Ab welchem Ähnlichkeitsgrad betrachten wir zwei Adressen als potenzielle Dublette?

Der Scoring-Ansatz: Mehrere Signale kombinieren

In der Praxis hat sich ein gewichtetes Scoring-Modell bewährt, bei dem verschiedene Felder unabhängig verglichen und die Ergebnisse zu einem Gesamtscore zusammengeführt werden.

Feld	Methode	Gewichtung
Nachname	Kölner Phonetik + Levenshtein	30%
Vorname	Kölner Phonetik	15%
Straße	Levenshtein (nach Normalisierung)	20%
PLZ	Exakter Vergleich	20%
Ort	Levenshtein	10%
Geburtsdatum	Exakter Vergleich	5%

Die Normalisierung der Straßennamen ist dabei ein eigenes Thema: “Str.” wird zu “Straße”, Hausnummerzusätze werden getrennt, und Sonderzeichen werden vereinheitlicht. Ohne diese Vorverarbeitung sinkt die Erkennungsrate erheblich.

Schwellenwerte und manuelle Nachprüfung

Ein Score über 0.95 kann als sichere Dublette behandelt werden. Scores zwischen 0.75 und 0.95 landen in einer Warteschlange zur manuellen Prüfung. Alles darunter wird als eigenständiger Datensatz betrachtet. Diese Schwellenwerte müssen pro Datenbestand kalibriert werden, es gibt keine universellen Werte.

Performance: Blocking-Strategien

Bei großen Datenbeständen, wir sprechen von mehreren Millionen Datensätzen, ist ein Vergleich jedes Datensatzes mit jedem anderen nicht praktikabel. Die Komplexität wäre O(n^2). Die Lösung sind Blocking-Strategien, die den Suchraum eingrenzen:

• PLZ-Blocking: Nur Datensätze mit gleicher PLZ werden verglichen
• Phonetisches Blocking: Nur Datensätze mit gleichem phonetischem Code des Nachnamens
• Sorted Neighborhood: Sortierung nach einem Schlüssel und Vergleich innerhalb eines gleitenden Fensters

In der Praxis kombiniert man mehrere Blocking-Strategien, um sowohl die Performance als auch die Erkennungsrate zu optimieren. Mit PLZ-Blocking und phonetischem Blocking auf dem Nachnamen reduziert sich die Anzahl der notwendigen Vergleiche um mehrere Größenordnungen.

Die Grenzfälle: Umzüge innerhalb derselben PLZ

Jedes Scoring-Modell hat blinde Flecken, und einer der tückischsten betrifft Umzüge. Wenn eine Person innerhalb derselben Postleitzahl umzieht, vielleicht sogar in derselben Straße nur die Hausnummer wechselt, entsteht ein Datensatz, der dem alten zum Verwechseln ähnlich sieht. Name identisch, PLZ identisch, Straße identisch oder fast identisch, der Score schießt auf 0.98. Das System meldet: sichere Dublette.

Nur ist es keine. Es sind zwei gültige, historisch korrekte Adressen derselben Person. Die eine ist veraltet, die andere aktuell. Löscht man die vermeintliche Dublette, verliert man entweder die aktuelle Adresse oder die Zuordnung zu alten Vorgängen.

Das Problem verschärft sich in der Praxis:

• Ehepaare am selben Wohnort mit ähnlichen Nachnamen (z.B. durch Doppelnamen)
• Eltern und erwachsene Kinder an derselben Adresse
• Umzüge innerhalb eines Wohnblocks, Hausnummer 12a wird zu 12b

Die Lösung liegt nicht im Algorithmus, sondern im Prozess: Potenzielle Dubletten mit sehr hohem Score und gleichzeitig identischer PLZ werden nicht automatisch zusammengeführt, sondern in eine separate Prüfkategorie geschoben. Zusätzliche Signale helfen bei der Unterscheidung, Geburtsdatum, Kundennummer oder der Zeitstempel der letzten Adressänderung. Wenn zwei Datensätze denselben Namen an derselben Adresse haben, aber einer ein Erfassungsdatum von 2015 und der andere von 2018 trägt, ist ein Umzug mit Rückkehr oder ein Verwandter wahrscheinlicher als eine echte Dublette.

Fazit

Dublettenprüfung ist kein Problem, das sich mit einer einzelnen Bibliothek oder einem einzelnen Algorithmus lösen lässt. Es erfordert eine Kombination aus phonetischen Verfahren, Ähnlichkeitsmaßen und durchdachtem Scoring, abgestimmt auf den konkreten Datenbestand und die fachlichen Anforderungen. Die Kölner Phonetik in Kombination mit der Levenshtein-Distanz und einem gewichteten Scoring-Modell hat sich in der Praxis als robuster Ansatz bewährt, der sowohl bei Personennamen als auch bei Postanschriften zuverlässige Ergebnisse liefert.

Aber der beste Algorithmus nützt wenig, wenn man die Grenzfälle nicht kennt. Umzüge innerhalb derselben PLZ, Familienmitglieder an derselben Adresse, historische vs. aktuelle Daten, das sind die Fälle, die den Unterschied zwischen einem guten und einem produktionsreifen System ausmachen.