statische Zeichenketten - Vergleiche

statische Zeichenketten - Vergleiche

statische Zeichenketten - Vergleiche

statische Zeichenketten - Vergleiche

statische Zeichenketten - Vergleiche

statische Zeichenketten - Vergleiche

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Phonetische Suche

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Levenshtein

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Needleman-Wunsch / Smith-Waterman

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Zusammenfassung

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Phonetische Suche

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Levenshtein

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Needleman-Wunsch / Smith-Waterman

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Zusammenfassung

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Phonetische Suche

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Levenshtein

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Needleman-Wunsch / Smith-Waterman

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Zusammenfassung

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Phonetische Suche

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Levenshtein

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Needleman-Wunsch / Smith-Waterman

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Zusammenfassung

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Phonetische Suche

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Levenshtein

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Needleman-Wunsch / Smith-Waterman

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Zusammenfassung

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Phonetische Suche

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Tabelle: Soundex-Zuordnung

1	B, F, P, V
2	C, G, J, K, Q, S, X, Z
3	D, T
4	L
5	M, N
6	R

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Levenshtein

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

 

 

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Needleman-Wunsch / Smith-Waterman

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Zusammenfassung

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.

Tabelle: Ähnlichkeitswerte versch. Methoden und Beispiele

.	Soundex	SubStr	jaro	jaWi	Levensht	bagDist
„Sam J Chapman“ - „Samuel Chapman“	0,50	0,79	0,88	0,91	0,79	0,82
„Sam J Chapman“ - „S Chapman“	0,50	0,62	0,68	0,71	0,69	0,85
„Samuel Chapman“ - „S Chapman“	0,25	0,57	0,46	0,51	0,64	0,82
„Sam J Chapman“ - „Sam J Chapman“	1,00	1,00	1,00	1,00	1,00	1,00
„Samuel John Chapman“ - „John Smith“	0,25	0,26	0,37	0,37	0,26	0,66
„John Smith“ - „Richard Smith“	0,25	0,46	0,57	0,57	0,54	0,65
„John Smith“ - „Sam J Chapman“	0,25	0,00	0,32	0,32	0,01	0,58
„Sam J Chapman“ - „Richard Smith“	0,00	0,00	0,29	0,32	0,00	0,46
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,57	0,70	0,79	0,68	0,84
„Sam J Chapman“ - „Samuel John Chapman“	0,75	0,74	0,77	0,88	0,74	0,87
„Cunningham“-“Cunnigham“	0,75	0,90	0,97	0,98	0,90	0,95
„Campell“-“Campbell“	0,75	0,88	0,81	0,89	0,87	0,94
„Nichleson“-“Nichulson“	1,00	0,78	0,93	0,96	0,78	0,89
„Massey“-“Massie“	1,00	0,67	0,78	0,87	0,67	0,83

Der Annäherungs-Vergleich ist ein wichtiges Feature für die erfolgreiche Gewichtsermittlung wenn Zeichenketten von Namen und Adressen verglichen werden sollen. Anstelle einer einfachen Ja-Nein-Gewichtung ganzer Terme oder x Anfangsbuchstaben erlauben Annäherungsvergleiche partielle Übereinstimmungen, falls Strings aufgrund typographischer, geographischbedingter oder andere Fehler nicht identisch aber sehr ähnlich sind.

Eine Vielzahl von Annäherungsalgorithmen sind entwickelt worden, sowohl im statischen DuplikateFinden als auch in den Informatik und natürliche Sprachverarbeitung entwickelnden Interessengruppen.

Abhängig von der Fehlerursache können diese unterteilt werden in

Verfahren zur phonetischen Distanz

Sie wandeln die Attributinhalte in Lautsprache um und vergleichen sie auf dieser Basis. Beispiel: Soundex

Editierdistanz – Verfahren

Diese messen den Abstand der Buchstaben in zum Vergleich herangezogenen Wörtern. Beispiel: Levenshtein

typewrite Distanz – Verfahren

welche die Dimension der Eingabegeräte betrachten und beispielsweise Tastenabstände benachbarter Tasten betrachten und damit die Wortähnlichkeit ermitteln. Beispiel: Needleman-Wunsch, Smith-Waterman

Swapping - Distanz

Sie betrachten die Möglichkeit, daß bei der Eingabe Terme an das falsche Attribut gekoppelt wurden (Wortvertauschung)

informationsbasierende Verfahren

Beispiel: Kompression

Sie unterscheiden sich hauptsächlich in Abarbeitungsgeschwindigkeit und Genauigkeit Ihrer Ergebnisse.

Es ist mitunter daher empfehlenswert, nochmals Vorselektionen durch einfacherere Methoden durchzuführen, wie beispielsweise eine BagDistanz-Annäherung vor der Berechnung einer Levenshtein-Distanz.

Erkenntnis aus der Phonetik und Phonologie werden genutzt, um die klangliche Repräsentation eines Wortes zu ermitteln. Um diese phonet. Repräsentation zu finden, werden Wörter in „Phoneme“ zerlegt. Je nach gewünschter Unschärfe der Sucher werden ähnliche Laute zusammengefasst und damit in die klangliche Dimension abgebildet. Dort können sie ebenfalls durch im Anschluß erläuterte Methoden equivalent untersucht werden (bswp. Lautersetzungen, -auslassungen, Levenshtein-Analyse). Es ist zu beachten, daß die Art der Abbildung jeweils sprachenabhängig ist.

Soundex ([Soundex00]) ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen in englischer Sprache, welcher ebenso für den deutschen Sprachraum gute Ergebnisse liefert. Er kodiert gleichklingende Wörter zu identischen Zeichenfolgen, welche aus dem Anfangsbuchstaben sowie 3 Ziffern, die aus dem darauffolgenden Konsonanten des Wortes generiert werden. Hierbei besitzen ähnliche Laute den gleichen Ziffern-Code.

Doppelt vokommende Buchstaben werden wie Einzelbuchstaben betrachtet, ebenso aufeinanderfolgende Buchstaben mit gleichem Soundex-Code, so daß "Dackelmann" beispielsweise mit "D-245" beschrieben wird. Namenszusätze wie beispielsweise "von" können ignoriert werden.

Werden 2 Konsonanten mit gleichem Soundex-Code durch Vokale getrennt, so wird der rechte Konsonant nicht verworfen, es sei denn, das trennende Zeichen ist ein H oder ein W.

Wie gezeigt, handelt es sich hierbei um eine schnelle, grobe Einteilung, welche ebenso als Grobauswahl-Filter genutzt werden könnte.

Q-Gramme

Qgramme stellen eine Erweiterung der bereits besprochenen Bigramme dar. Hierbei wird über eine Zeichenketten σ ein Sliding-Windows (Gleitfenster) mit der Länge q > 2 gezogen. Da Q-Gramme am Beginn und am Ende der Zeichenkette σ weniger als $\mid q\mid$ Zeichen besitzen können, werden die Sonderzeichen # als Prefix mit q -1 Auftreten und $ als Suffix mit q-1 Auftreten eingeführt. Das Wort "Dresden" würde demnach bei q=3 als ['##D', '#Dr', 'Dre', 'res', 'esd', 'sde', 'den', 'en$', 'n$$'] dargestellt werden.

Zusätzlich können die Auftrittspositionen der Q-Gramme ebenfalls gespeichert werden, man nennt diese auch "positionell bestimmte Qgramme". Dadurch ist ein feinerer Abgleich möglich. Die Auftrittswahrscheinlichkeit ist, wie auch bei der folgenden BagDistanz, stets größer als die Edit-Distanz.

Jaro

Jaro [Winkler91] führte eine String-Vergleichsmessung ein, welche Einträgen einen Ählichkeitswert zuordnet. Der String-Vergleich ist abhängig von der Zeichenkettenlänge und für die Art der typischerweise durch Personen verursachte Fehler angepasst. Es wird beim Anpassen der genauen Abkommensgewichtung genutzt, wenn 2 Zeichenketten nicht auf zeichengenau zusammenpassen. Genauer gesagt, wenn die Anzahl der gemeinsamen Zeichen im Zeichenkettenpaar c > 0, so berechnet sich der Jaro String-Vergleich nach:

$\Phi =W_1\cdot c/d+W_2\cdot c/r+W_t\cdot (c-\tau )/c$

wobei

$W_1$ = Gewichtung der Zeichen im ersten der beiden Datensätze

$W_2$ = Gewichtung der Zeichen im zweiten der beiden Datensätze

$W_t$ = Gewichtung der Transposition

$d$ = Länge der Zeichenkette im ersten Datensatz

$r$ = Länge der Zeichenkette im zweiten Datensatz

$\tau$ = Anzahl der Transpositionen des Zeichens

$c$ = Anzahl der gemeinsamen Zeichen im Zeichenketten-Paar

Falls $c=0$, dann $\Phi =0$ .

Zwei Zeichen werden als gleich angesehen, wenn Sie nicht weiter als $(m/2–1)$ von einander entfernt sind. Dabei ist $m=\max (d/r)$ . Zeichen, welche bei beiden Zeichenketten gleich sind, gelten als "zugeordnet", die übrigen Zeichen als "unzugeordnet". Jede Zeichenkette hat demnach die selbe Anzahl zugeordneter Zeichen.

Die Nummer von Transpositionen wird wie folgt berechnet:

Das erste zugeordnete Zeichen in einem String wird mit dem ersten Zeichen der zweiten Zeichenkette verglichen. Falls die Zeichen nicht identisch sind, ist dies bereits eine halbe Transposition. Dann wird das zweite Zeichen der ersten Zeichenkette mit dem zweiten zugeordneten Zeichen der zweiten Zeichenkette verglichen, etc. Die Anzahl der nicht-übereinstimmenden Zeichen wird durch 2 geteilt um die Anzahl der Transpositionen zu erhalten.

Falls 2 Terme zeichengenau übereinstimmen, dann ergibt sich der Jaro-Vergleicher $\Phi$ aus $W_1+W_2+W_t$, was gleichzeitig das Maximum ist, welches Φ erreichen kann. Das Minimum ist 0 und tritt auf, wenn beide Zeichenketten keine Zeichen gemeinsam haben.

Als Anfangsgewichtungen werden oftmals $W_1$ , $W_2$ , $W_{\mathrm{t}}$ willkürlich auf $1/3$ gesetzt. Die neue Zeichen-Comparator Metrik verändert grundsätzlich den Basis- Zeichen-Comparator je nachdem ob die ersten paar Zeichen in den verglichenen Zeichenketten übereinstimmen.

Da diese Gewichtungen für verschiedene Felder, wie Vorname, Nachname und Hausnummer, variieren können, gibt [Winkler93] Grundlagen für die Modellierung der Gewichtungsanpassung als eine stückweise lineare Funktion. Diese Prozeduren benötigen eine repräsentative Menge von Paaren, von denen die Identität bekannt ist.

Winkler-Jaro

William E. Winkler nutzt die Technik Jaros, geht allerdings davon aus, dass typographische Fehler häufiger am Ende von Wörtern vorkommen, und daher der Beginn von Wörtern schwerer zur Identifizierung gewichtet wird, meist die ersten 4 Zeichen. Die teilweise Übereinstimmungsgewichtung wird daher erhöht, falls der Beginn zweier Zeichensätze gleich ist.

$\mathrm{Jaro}-\mathrm{Winkler}(s,t)=\mathrm{Jaro}(s,t)+(P\text{'}/10)·(1-\mathrm{Jaro}(s,t))$

BagDistanz

Die "Bag Distance" ist eine einfache Distanz-Messung, welche stets eine Distanz kleiner oder gleich der Edit Distanz angibt. Sie wird daher auch oft als letzte Vorauswahl-Instanz für mit Levenshtein zu testende Terme genutzt, da sie für 2 gegebene Zeichenketten $s_1$ und $s_2$ in $O(\mathrm{len}(s_1)+\mathrm{len}(s_2))$ berechnet werden kann. Die Bag-Distanz wird daraufhin durch das Maximunm der Zeichenkette geteilt und ergibt so einen Wert zwischen 0.0 und 1.0. Daher wird die Bag-Distanz Ähnlichkeit immer größer sein als die der Edit Distanz.

Die grundlegende Methode für die Festlegung des Ähnlichkeitsgrades zwischen zwei Einzelwörter basiert auf dem "Levenshtein"- oder "Edit Distance"-Algorithmus. Dabei wird versucht, den minimale Weg für die Umformung einer Zeichenketten durch Löschen oder Ersetzen von Zeichen zu finden, sodass die zwei Zeichenketten angeglichen werden können. Die einzelnen Schritte der Umformung werden ständig bewertet und ergeben nach der Umformung den Ähnlichkeitsgrad, der bezogen auf der Länge des längeren Wortes in Prozent ausgedrückt werden kann.

Im allgemeinen wird diese Umformung durch einen Dynamic-Programming-Ansatz gelöst. Eine Matrix wird initialisiert, die für jede (m, N) - Zelle die "Edit-Distanz" zwischen dem m-Buchstabenpräfix des einen Wortes und den n-Präfixes des zweiten Wortes enthält. Wird dies Tabelle beispielsweise von der oberen linken Ecke zur unteren rechten Ecke gefüllt, so kostet jeder Sprung horizontal oder vertikal einen virtuellen Betrag, da es einem Editieren, Einfügen oder Löschen eines Zeichens entspricht. Die Zahl am rechten unteren Ende dieses Beispiels entspricht somit dem Levenshtein-Abstand zwischen beiden Wörtern.

Gleiche Zeichen ergeben auf der Zeichenebene eine Bewertung von 1.0. Die Punkte für Strafe und Score werden über Experten vorgegeben oder anhand vieler Beispielen eingestellt.

Als erste natürliche Erweiterung führten Needleman und Wunsch zusätzliche Parameter ein. So können die Einzelkosten für Zeichenersetzung, -einfügung und -löschung individuell definiert werden. Weiterhin ist die Strafpunktzahl für Löcher (sog. „gaps“) einzeln definiert. Dies ist von Bedeutung, wenn in einer Zeichenkette ein Begriff abgekürzt, in der zweiten jedoch ausgeschrieben wurde. Der Needleman-Wunsch-Algorithmus findet im Bereich der Bioinformatik zur Identifikation von Proteinen rege Anwendung.

Bisher ist es nicht möglich, die längste übereinstimmende Teilsequenz beider Zeichenketten zu finden und anzupassen. Um dieses Problem zu beheben wurden von T.Smith und M. Waterman entsprechende Modifikationen am Needleman-Wunsch-Algorithmus eingefügt, die genau dies ermöglichen. Der modifizierte Algorithmus wird Smith-Waterman-Algorithmus genannt. [Vldb01]

Die erweiterte EditDistanz besitzt zusätzlich die Möglichkeit, Substitutionen zu nutzen und Blöcke fortlaufender Zeichen zu jeweils bestimmten Strafpunkten zu bewegen. Diese Blöcke müssen in beiden Zeichenketten identisch sein und 0≤extendedEditDistance(σ₁,σ₂)≤max(∣σ₁∣,∣σ₂∣). Die Laufzeitkomplexität beträgt in allen Fällen O(n * m).

Substring

Giorgos Stoilos beschreibt in [Stoilos05] eine weitere Variante, welche auf dem Substring-Metrik beruht und für Bezeichnungs-Matching, wie es beispielsweis beim Ontology-Alignment auftritt, gute Erfolge verspricht.

$Sim(\mathrm{s1},\mathrm{s2})=\mathrm{Comm}(\mathrm{s1},\mathrm{s2})-\mathrm{Diff}(\mathrm{s1},\mathrm{s2})+\mathrm{winkler}(\mathrm{s1},\mathrm{s2})$

Grundsätzlich werden hier beide Zeichenketten iterativ nach den maximal übereinstimmenden Teil-Zeichenketten durchsucht und aus den Strings entfernt. Konkanetierten Zeichenketten können so sehr gut erkannt werden.

$\mathrm{Comm}(\mathrm{s1},\mathrm{s2})=\frac{2\ast \sum _i\mathrm{length}({\mathrm{maxComSubString}}_i)}{\mathrm{length}(s_1)+\mathrm{length}(s_2)}$

Die nicht erkannten Zeichenreste werden im Differenz-Term über die Hamacher-Funktion mit der Originalstringlänge ins Verhältnis gesetzt.

$\mathrm{Diff}(s_{\mathrm{1,}}{s}_2)={\mathrm{uLen}}_{s_1}\times {\mathrm{uLen}}_{s_2}\ast p+(1-p)\ast ({\mathrm{uLen}}_{s_1}+{\mathrm{uLen}}_{s_2}–{\mathrm{uLen}}_{s_1}\ast {\mathrm{uLen}}_{s_2})$

Kompression

Die Nutzung von Kompressionsalgorithmen, um Ähnlichkeiten zwischen Strings zu berechnen, basiert auf deren Informationsgehalt. Die 1965 von A.N. Kolmogorov propagierte Kolmogorov-Komplexität quantifiziert die Zufälligkeit von Zeichenketten und anderen Objekten in einer objektiven und absoluten Art und Weise.

Sie wird für verschiedene Data-Mining Algorithmen, inklusive Clustering und time-seriers-Analysen genutzt, unter anderem wegen ihrer annähernden Parameterfreiheit genutzt. [Keogh04] geht darauf näher ein.

Eine Ähnlichkeitsmessung zwischen zwei Zeichen $s_1$ und $s_2$ kann wie folgt berechnet werden:

Sei $K(s_1)$ die Länge des kürzest möglichen Programms, welches die Zeichenkette $s_1$ an einem Universal-PC (Turing-Maschine) erstellen kann. Die Länge des kürzesten Programms auf $s_2$ unter der Voraussetzung von $s_1$ als unterstützende Eingabe wird mit $K(s_2\mid s_1)$ angegeben.

Die Kolmogorov-Komplexität ist die unterste Grenze aller Informationsmessungs-Algorithmen. Da sie nicht direkt berechnet werden kann, wird diese durch Kompressions.Algorithmen angenähert. Genau genommen ist $K(s_1)$ die beste Kompression, welche auf einen Text $s_1$ angewendet werden kann.

Mit einem gegebenen Algorithmus bezeichnet man $c(s_1)$ als die Größe der gepackten Zeichenkette $s_1$ .

$C(s_1)=\mathrm{len}(\mathrm{compress}(s_1))\approx K(s_1)$

$C(s_2)=\mathrm{len}(\mathrm{compress}(s_2))\approx K(s_2)$

$C(s_1\mid s_2)$ erhalten wir als Kompression, wenn der Lompressor zunächst mit $s_2$ trainiert wird und darauf $s_1$ packt. Falls der Kompressor also (wie LZW) auf einer textuellen Substitution basiert, würde $s_1$ unter Nutzung des Wörterbuchs von $s_2$ gepackt.

Verallgemeinert man dies nun auf die gepackte Version einer Zeichenkette, so ergibt sich

$C(s_{12})=\frac{C(s_1\mid s_2)+C(s_2\mid s_1)}{2}=\frac{\mathrm{len}(\mathrm{compress}(s_1+s_2))+\mathrm{len}(\mathrm{compress}(s_2+s_2))}{2}$

Zu einer Ähnlichkeit normalisiert kann man diese Formel nutzen.

$sim(s_{\mathrm{1,}}{s}_2)=1.0–\frac{C(s_{12})–\min (C(s_1),C(s_2))}{\max (C(s_1),C(s_2))}$

wobei $\mathrm{compress}()$ die Compressionsfunktion darstellt.

Wie bereits in der Einleitung angesprochen, variieren die Mess-Ergebnisse der einzelnen vorgestellten Algorithmen stark, abhängig von der gewählten Einsatz-Domäne.

Anhand dieser Übersicht ist erkennbar, daß die Bag-Distanz stets größere Werte liefern als Levenshtein. Sie kann daher als Vorfilter für Edit-Distance genutzt werden.

Bei Namen ist der Soundex eine schnelle Methode zur Vorsortierung, da Vokale in Namen eine eher untergeordnete Rolle spielen und aufgrund der Verkürzung auf bestimmte Konsonanten eine gute Vorauswahl erreicht wird.

Die „Kompression“ nach stellt eine kombinierte Methode dar, da gesamte Datensätze damit gepackt werden und die Position der einzelnen Bestandteile keine Bedeutung besitzt. Seine Anwendung bringt bei der Packung ganzer Entitäten optimale Ergebnisse, da für ihn hierbei Swapping-Auftritte unbedeutend sind.

SubString-Metriken werden gerne bei der Duplikatefindung innerhalb des Onthology-Alignment genutzt, da dort meist nur die Position miteinander konkatenierter Wortsegmente variiert.

Der JaroWinkler-Algorithmus ist in der Abarbeitung schneller als die Levenshtein'sche Herangehensweise, reagiert allerdings minimal schwächer. In den folgenden Beispielen ist gut erkennbar, daß er Buchstabenfehler am Ende eines Wortes weniger gewichtet als solche, die am Beginn einer Vergleichszeichenkette auftreten. Der klassische Jaro-Algorithmus hingegen zeigt hierbei die gleiche Fehlerrate an.