Clusterbildung
Ein unscharfer Vergleich von allen Datensätzen mit allen ist nicht möglich, da die Anzahl der einzelnen Vergleiche schnell zu einer astronomisch hohen Anzahl von Vergleichen führen würde.
Jede Software zur Dublettensuche wird hier also eine Vorauswahl treffen müssen, bei der jene Datensätze zu Blöcken zusammengefasst werden, die sich zum unscharfen Vergleich lohnen.
FuzzyDupes verwendet ein Verfahren zur Clusterbildung, welches sehr schnell zuverlässige und kleine Cluster ermittelt. Das Verfahren basiert auf N-Grammen, das sind kleine Teilzeichenketten, die das Programm in sehr großer Anzahl verarbeiten kann.
Dieses Verfahren ist mathematisch exakt und die Clustergröße lässt sich dabei frei einstellen. Die aktuelle, durchschnittliche und maximale Clustergröße zeigt das Programm während der Dublettensuche an.
Experimentieren Sie ruhig auch einmal mit anderen Clusterspalten, um zu sehen, ob Sie dadurch ein besseres Ergebnis bekommen oder die Suche beschleunigen können.
Normalisierung
Bevor die Zeichenketten der einzelnen Spalten miteinander unscharf verglichen werden, werden die Daten (temporär im Speicher) normalisiert. Dabei werden Sonderzeichen und Umlaute ersetzt und einige gebräuchliche Abkürzungen und Schreibweisen umgewandelt (z.B. strasse, straße -> str.)
Unscharfer Vergleich
Hier wird mit geeigneten Algorithmen eine (prozentuale) Übereinstimmung der einzelnen Spalten errechnet und daraus (unter Berücksichtigung verschiedener Gewichtungen) eine durchschnittliche Übereinstimmung errechnet.
Es sind verschiedene Pattern-Matching Algorithmen bekannt, die sich zu diesem Zweck mehr oder weniger gut eignen. Jeder Hersteller einer Dubletten-Software wird hier sein eigenes Verfahren einsetzen. Geeignete Verfahren sollten u.a. gut mit Permutationen (Vertauschungen, Verdrehern) der Zeichen klarkommen, um eine gute Trennschärfe zu erzielen.
Liegt die prozentuale Übereinstimmung am Ende über dem festgelegten Schwellenwert, werden diese Sätze als Dublette markiert (erhalten dieselbe fuzzydupes_ID).
Trennschärfe
Die Qualität einer Dublettensuche wird nicht allein daran gemessen, ob möglichst viele Dubletten gefunden werden, sondern auch daran, wie zuverlässig das Ergebnis ist, bzw. wie viele falsche Dubletten ermittelt werden.
Wichtig ist zudem, welchen Einfluss Änderungen des Schwellenwertes auf das Suchergebnis haben. Ungünstig wäre es, wenn kleine Änderungen des Schwellenwertes zu großen Unterschieden im Suchergebnis führen und die Trennschärfe durch kleinere Schwellenwerte negativ beeinflusst wird.
Sie werden feststellen, dass der Schwellenwert bei FuzzyDupes keinen kritischen Einfluss auf das Suchergebnis hat (dass es etwa auf kleinste Änderungen nach dem Komma ankommt). Selbst bei niedrigeren Schwellenwerten erreicht FuzzyDupes eine sehr gute Trennschärfe.