Fuzzy Matching mit expliziten Grenzen

Diesen Beitrag anhören (12 Min.)

SELECT similarity('Schmidt Bau GmbH', 'Schmitt Bau GmbH');
-- 0.72

SELECT similarity('Bäckerei Hoffmann GmbH & Co. KG',
                  'BAECKEREI HOFFMANN DANKE RG 4711');
-- 0.34

Der erste Wert sieht aus wie ein Treffer und ist keiner: zwei verschiedene Firmen, ein Buchstabe Unterschied, beide existieren. Der zweite Wert sieht aus wie Rauschen und ist der richtige Kunde – nur eben so, wie er in einem Überweisungs-Verwendungszweck ankommt: großgeschrieben, ohne Umlaute, mit Rechnungsnummer und Grußformel im selben Feld. Wer diese beiden Zahlen nebeneinander gesehen hat, glaubt keiner Ähnlichkeitsfunktion mehr blind. Genau das ist der richtige Zustand, um mit Fuzzy Matching zu arbeiten.

Ausgangslage: Verwendungszwecke gegen offene Posten

Der Kontext ist dasselbe private Datenprojekt wie im Vormonat: Rechnungs- und Zahlungsdaten abgleichen. Auf der einen Seite stehen offene Posten mit sauberen Debitorennamen aus der Stammdatenpflege. Auf der anderen Seite stehen Kontoumsätze, deren Verwendungszweck ein Freitextfeld ist. Dort schreiben Menschen und Buchhaltungssysteme, was sie wollen: mal die Rechnungsnummer, mal der Firmenname in einer von fünf Schreibweisen, mal beides, mal keins von beidem.

Solange eine Rechnungsnummer im Text steht, ist der Abgleich trivial – ein regulärer Ausdruck, ein exakter Schlüssel, fertig. Interessant wird es bei den restlichen Zahlungen, bei denen nur ein Firmenname als Anker bleibt. „Müller & Söhne GmbH" kommt als „MUELLER SOEHNE", „Mueller u. Soehne Bau" oder „M&S GmbH" an. Exaktes Matching findet hier nichts, und genau dafür gibt es Fuzzy Matching. Die Frage ist nicht, ob man es einsetzt, sondern wie man verhindert, dass aus „ähnlich" stillschweigend „gleich" wird.

Mir hat dabei ein Satz geholfen, den ich mir früh an den Report geschrieben habe: Ein Match ist eine Behauptung mit einer Konfidenz, kein Fakt. Alles Weitere in diesem Beitrag ist die technische Konsequenz aus diesem Satz.

Normalisierung zuerst

Bevor irgendeine Distanzfunktion läuft, lohnt sich der langweiligste Schritt am meisten: Normalisierung. Ein großer Teil der scheinbaren Unschärfe ist gar keine – es sind systematische Unterschiede, die man deterministisch wegräumen kann. Rechtsformen wie GmbH, AG oder KG tragen fast keine Unterscheidungskraft, blähen aber jede Ähnlichkeitsrechnung auf. Umlaute erscheinen im Zahlungsverkehr traditionell als ae/oe/ue. Groß- und Kleinschreibung, doppelte Leerzeichen, Satzzeichen: alles Störgeräusch.

import re

LEGAL_FORMS = re.compile(
    r"\b(gmbh|ag|kg|ug|ohg|gbr|mbh|co)\b\.?",
    re.IGNORECASE,
)

UMLAUT_MAP = str.maketrans(
    {"ä": "ae", "ö": "oe", "ü": "ue", "ß": "ss"}
)

def normalize_name(raw: str) -> str:
    text = raw.strip().lower().translate(UMLAUT_MAP)
    text = LEGAL_FORMS.sub(" ", text)
    text = re.sub(r"[^a-z0-9 ]+", " ", text)
    return re.sub(r"\s+", " ", text).strip()

Nach diesem Schritt sind „Müller & Söhne GmbH" und „MUELLER SOEHNE" beide mueller soehne – ein exakter Treffer, ganz ohne Fuzzy-Verfahren. In meinem Datensatz hat allein die Normalisierung rund die Hälfte der vorher „unscharfen" Fälle in exakte Matches verwandelt. Das ist der Grund, warum ich Normalisierung nicht als Vorstufe des Fuzzy Matching sehe, sondern als eigenständige Stufe mit eigenem Erfolgsmaß. Jeder Fall, der hier exakt wird, muss später nicht mit einer Konfidenz verteidigt werden.

Wichtig ist, dass normalize_name auf beiden Seiten identisch läuft – auf den Debitorennamen genauso wie auf den Verwendungszwecken. Sobald zwei leicht unterschiedliche Normalisierungen im Spiel sind, jagt man Geistern hinterher.

Distanzen, Trigramme, Phonetik

Für den Rest bleiben die klassischen Verfahren, und sie haben unterschiedliche Stärken. Levenshtein zählt Editieroperationen und ist gut für Tippfehler. Jaro-Winkler gewichtet Übereinstimmungen am Wortanfang stärker – passend für Firmennamen, bei denen der Anfang meist stabil ist und hinten Zusätze variieren. Trigramm-Ähnlichkeit zerlegt Strings in Dreiergruppen von Zeichen und vergleicht die Mengen; sie ist unempfindlich gegen Wortreihenfolge und in Postgres über die Erweiterung pg_trgm direkt in SQL verfügbar.

Dazu kommt ein Verfahren, das im deutschsprachigen Raum zu selten erwähnt wird: die Kölner Phonetik. Sie ist das deutsche Gegenstück zu Soundex und bildet Wörter auf einen Lautcode ab, der für die deutsche Aussprache entworfen wurde. „Meyer", „Maier" und „Mayr" landen auf demselben Code – für Distanzfunktionen sind das drei verschiedene Strings, fürs Ohr ist es derselbe Name. Als alleiniges Kriterium ist Phonetik zu grob, als zusätzliches Signal neben einer Distanz ist sie wertvoll.

In Python bündelt rapidfuzz die Distanzverfahren in einer schnellen Bibliothek. Ich kombiniere zwei Maße zu einem Score, weil kein einzelnes Verfahren alle Fehlerarten abdeckt:

from rapidfuzz import fuzz, distance

def score_pair(payment_name: str, debtor_name: str) -> float:
    jaro_winkler = distance.JaroWinkler.similarity(
        payment_name, debtor_name
    )
    token_sort = fuzz.token_sort_ratio(
        payment_name, debtor_name
    ) / 100
    return 0.6 * jaro_winkler + 0.4 * token_sort

token_sort_ratio sortiert die Wörter vor dem Vergleich und fängt damit vertauschte Reihenfolgen ab („bau schmidt" gegen „schmidt bau"). Die Gewichte 0,6 und 0,4 sind kein Naturgesetz – sie sind ein Parameter, den ich an einem von Hand gelabelten Ausschnitt der Daten kalibriert habe. Auch das gehört zur Ehrlichkeit des Verfahrens: Der Score ist eine konstruierte Größe, keine Wahrheit.

Blocking gegen die quadratische Falle

Wer jeden Verwendungszweck gegen jeden offenen Posten vergleicht, bezahlt O(n²). Bei ein paar hundert Datensätzen ist das egal, bei zehntausenden Zahlungen gegen tausende Debitoren nicht mehr. Die Standardantwort heißt Blocking: eine billige, grobe Vorauswahl, die die Kandidatenmenge klein macht, bevor die teuren Vergleiche laufen.

Hier spielt pg_trgm seine zweite Stärke aus. Die Trigramm-Ähnlichkeit ist nicht nur eine Funktion, sondern auch ein indexierbarer Operator. Mit einem GIN-Index über den normalisierten Namen liefert Postgres die ähnlichsten Kandidaten, ohne die ganze Tabelle anzufassen:

CREATE EXTENSION IF NOT EXISTS pg_trgm;

CREATE INDEX idx_open_invoice_debtor_trgm
    ON open_invoice
    USING gin (debtor_name_normalized gin_trgm_ops);

SET pg_trgm.similarity_threshold = 0.45;

SELECT i.invoice_no,
       i.debtor_name_normalized,
       similarity(i.debtor_name_normalized, :payment_name)
           AS trigram_score
FROM open_invoice AS i
WHERE i.debtor_name_normalized % :payment_name
ORDER BY trigram_score DESC
LIMIT 10;

Der Operator % prüft gegen den eingestellten Schwellwert und nutzt dabei den Index. Die 0,45 sind bewusst niedrig angesetzt: In dieser Stufe ist ein übersehener Kandidat schlimmer als zwanzig überflüssige, denn was das Blocking verwirft, sieht die Feinbewertung nie wieder. Die eigentliche Entscheidung fällt später – mit score_pair über die zehn Kandidaten, nicht in SQL.

Diese Zweiteilung hat sich bewährt: Postgres macht die Vorauswahl grob und schnell, Python macht die Bewertung genau und nachvollziehbar. Beide Stufen haben ihren eigenen Schwellwert mit eigener Begründung.

Drei Zonen statt einer Schwelle

Damit zur eigentlichen Pointe. Die meisten Fuzzy-Matching-Beispiele, die man findet, enden mit einer einzigen Schwelle: Score über X gleich Match, darunter kein Match. Das ist die Stelle, an der aus einem nützlichen Werkzeug ein gefährliches wird, denn eine einzelne Schwelle behauptet eine Trennschärfe, die die Daten nicht hergeben. Es gibt immer einen Bereich, in dem das Verfahren schlicht nicht weiß, ob zwei Namen zusammengehören – und dieses Nichtwissen gehört in die Architektur, nicht unter den Teppich.

Deshalb hat der Abgleich bei mir drei Zonen statt einer Schwelle:

Oberhalb der Akzeptanzschwelle wird automatisch zugeordnet, und die Zuordnung trägt den Score als Metadatum.
Zwischen den Schwellen landet das Paar in einer Durchsichtsliste – ein Mensch entscheidet.
Unterhalb der Ablehnungsschwelle passiert nichts, die Zahlung bleibt offen.

THRESHOLDS = {
    "version": "2024-09-03",
    "accept": 0.93,
    "reject": 0.72,
}

def classify(score: float) -> str:
    if score >= THRESHOLDS["accept"]:
        return "accept"
    if score < THRESHOLDS["reject"]:
        return "reject"
    return "review"

Die Schwellwerte stehen versioniert im Repository, nicht als Konstante irgendwo im Code verstreut. Jede Änderung an ihnen ist ein Commit mit Begründung. Das klingt bürokratisch, hat mir aber schon nach zwei Wochen geholfen: Als ich die Akzeptanzschwelle von 0,90 auf 0,93 angehoben habe, weil das Schmidt/Schmitt-Paar aus dem Einstieg durchgerutscht war, konnte ich im Verlauf genau sehen, welche Zuordnungen unter welchem Regelstand entstanden sind.

flowchart LR
    P[Verwendungszweck] --> N[normalize_name]
    D[Debitorenname] --> N
    N --> B[Blocking<br/>pg_trgm, Schwelle 0.45]
    B --> S[Feinbewertung<br/>score_pair]
    S --> Z{Score}
    Z -->|ab 0.93| A[automatisch<br/>zuordnen]
    Z -->|0.72 bis 0.93| R[Durchsicht<br/>durch Menschen]
    Z -->|unter 0.72| X[offen lassen]
    R --> AL[Alias-Regel<br/>versioniert]
    AL --> N

Die Rückkopplung unten rechts im Diagramm ist kein Detail. Jede manuelle Entscheidung aus der Durchsicht wird als Alias-Regel festgehalten – „M&S" ist „Müller & Söhne" – und fließt als Datum zurück in die Normalisierung. Beim nächsten Lauf ist derselbe Fall ein exakter Treffer. Die Grauzone schrumpft dadurch mit der Zeit, und zwar durch dokumentierte Entscheidungen statt durch mutigere Schwellwerte.

Der Report der Grauzone

Die Durchsichtsliste ist bei mir kein Dashboard, sondern eine Markdown-Datei, die jeder Lauf deterministisch erzeugt: gleiche Eingabe, gleiche Schwellwerte, gleicher Report. Sortiert nach Score, mit beiden Namen im Original und normalisiert, dem Trigramm-Wert aus dem Blocking und dem kombinierten Score daneben.

Der Grund für Markdown ist Diffbarkeit. Zwei Läufe lassen sich mit diff vergleichen, und die Differenz erzählt eine Geschichte: Welche Fälle sind durch neue Alias-Regeln aus der Grauzone verschwunden? Welche neuen Zweifelsfälle sind mit dem letzten Kontoauszug dazugekommen? Hat die Schwellwert-Änderung die Zone vergrößert oder verkleinert? Ein Dashboard zeigt den letzten Zustand; ein diffbarer Report zeigt die Bewegung. Für ein Abgleichsystem, dessen Kern die Frage „was hat sich geändert und warum" ist, wiegt das schwerer als jede Oberfläche.

Nebeneffekt: Der Report ist gleichzeitig das Prüfartefakt. Wenn ich in drei Monaten wissen will, warum eine Zahlung so zugeordnet wurde, steht der Score, der Regelstand und gegebenenfalls die manuelle Entscheidung in der Historie.

Asymmetrische Kosten

Bleibt die Frage, wo die Schwellen liegen sollen – und die beantwortet man nicht mit Statistik allein, sondern mit den Kosten der beiden Fehlerarten. Die sind hier deutlich asymmetrisch. Eine unzugeordnete Zahlung ist ein bekanntes Problem: Sie taucht in der Liste der offenen Fälle auf, jemand schaut drauf, ordnet zu, fertig. Eine falsch zugeordnete Zahlung ist ein unbekanntes Problem: Der offene Posten des einen Kunden gilt als beglichen, der andere bekommt womöglich eine Mahnung für eine bezahlte Rechnung. Der Fehler fällt erst auf, wenn sich jemand beschwert – und dann ist die Fehlersuche teuer, weil niemand mehr weiß, welcher Lauf mit welchem Regelstand die Zuordnung erzeugt hat.

Deshalb liegt die Akzeptanzschwelle bewusst hoch und die Grauzone ist breiter, als es die reine Trefferquote nahelegen würde. Ich nehme lieber zwanzig manuelle Durchsichten pro Monat in Kauf als eine stille Falschzuordnung pro Quartal. Das ist keine technische Entscheidung, sondern eine fachliche – aber sie wird erst möglich, weil die Architektur die Stellschraube explizit macht. Eine einzelne, hart codierte Schwelle bietet diese Abwägung gar nicht erst an.

Was ich daraus mitnehme

Fuzzy Matching hat einen schlechten Ruf bei Leuten, die einmal von einer Falschzuordnung gebissen wurden, und einen zu guten Ruf bei Leuten, die nur die Demo gesehen haben. Beides geht am Punkt vorbei. Die Verfahren – Levenshtein, Jaro-Winkler, Trigramme, Kölner Phonetik – sind seit Jahrzehnten verstanden und tun zuverlässig, was sie versprechen: Sie messen Ähnlichkeit. Was sie nicht können, ist Identität feststellen. Der Fehler liegt fast nie im Verfahren, sondern in der Systemgrenze, die aus einem Ähnlichkeitswert stillschweigend eine Tatsache macht.

Nützlich wird das Ganze genau in dem Moment, in dem die Grenzen explizit werden: Normalisierung als eigene Stufe, damit Deterministisches deterministisch bleibt. Blocking mit bewusst niedriger Schwelle, damit die teure Bewertung bezahlbar bleibt. Drei Zonen mit versionierten Schwellwerten, damit das Nichtwissen des Verfahrens einen definierten Ort hat. Ein diffbarer Report, damit die Grauzone beobachtbar schrumpft statt unbemerkt zu wachsen. Und Schwellen, die sich an den asymmetrischen Fehlerkosten orientieren statt an der Trefferquote.

Nichts davon ist neu, und genau das gefällt mir daran. Es ist dieselbe Haltung, die sich schon beim Modellieren der Rechnungsdaten im Vormonat ausgezahlt hat: Unsicherheit nicht wegabstrahieren, sondern ihr einen Namen, einen Wert und einen Platz im Datenmodell geben. Ein Match ist eine Behauptung mit Konfidenz. Systeme, die das ernst nehmen, darf man automatisieren lassen.

Weiterführende Quellen

RapidFuzz auf GitHub: https://github.com/rapidfuzz/RapidFuzz
Postgres 16, Erweiterung pg_trgm: https://www.postgresql.org/docs/16/pgtrgm.html
Kölner Phonetik (Wikipedia): https://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik

Kommentare