Stringähnlichkeit

Die Aufgabe Methoden der Ähnlichkeitsbestimmung • Editierabstand • Hamming • N-Gramme • Lose Digramme

Die Methoden im Vergleich • Demonstration • Beurteilung Einsatzformen • Korrigieren • Melden • Suchen

Vorbereitung • Vor-Fuzzyfizierung • Indizierung Systemarchitektur Und Ihre Aufgabenstellung?

Die Berechnung der Ähnlichkeit zweier Zeichenketten (Strings) spielt in vielerlei Anwendungen eine Rolle, etwa bei der

Stringmuster (Patterns) mit Wildcards oder definiert durch reguläre Ausdrücke sind für solche Verwendungen nicht ideal, insofern sie stets konkrete Aussagen über die Struktur einer Zeichenkette machen.
Sie definieren Muster, die sich aus festen (konstanten, intoleranten) und offenen (variablen, toleranten) Teilen zusammensetzen und melden entsprechend genau dann eine Übereinstimmung, wenn die angetroffenen Varianten ihre Variation in der Art und an der Stelle haben, wie bzw. wo das Muster sie vorsieht.
Dagegen kommt es zu keiner Übereinstimmung, wenn eine Variante just in jener Kleinigkeit abweicht, die das Muster als fix vorausgesetzt hat.

Das ist natürlich in vielen Fällen genau das Gewünschte, aber bei einer Reihe von Aufgabenstellungen lautet die Anforderung anders, und zwar:

In diesem Fall geht es also darum, eine ganz unspezifische Ähnlichkeit zu erkennen und höchstens noch einen Grad von Ähnlichkeit zu berücksichtigen.

Wie wird diese unspezifische Ähnlichkeit bestimmt? Liegt sie "im Auge des Betrachters"? Zumindest lassen sich unterschiedliche Kriterien anlegen und entsprechend auch unterschiedliche Verfahren definieren, um zu Aussagen über den Grad der Übereinstimmung zwischen zwei Zeichenketten zu kommen:

Der Editierabstand ist definiert als die kleinste Menge elementarer Operationen, mit denen ein bestimmter String in einen bestimmten anderen String verändert werden kann.

Als elementar gelten dabei Einfügen und Löschen einzelner Schriftzeichen. (In manchen Implementierungen wird auch das Ersetzen eines Schriftzeichens als elementar betrachtet. Der Algorithmus, den ich im folgenden benutze, tut das nicht: für ihn ist Ersetzen die Kombination aus Löschen und Einfügen.)

Aus dem Editierabstand, der den Unterschied zwischen den Strings ausdrückt, kann der Wert für deren Ähnlichkeit abgeleitet werden.

Die Hamming-Distanz summiert einfach die Anzahl von Ungleichheiten auf korrespondierenden Dimensionen zweier Objekte auf. Im Fall von Strings werden die Schriftzeichen an den einander entsprechenden Positionen verglichen.

N-Gramm-Übereinstimmungen sind ein weiteres und sehr gebräuchliches Maß. Ein N-Gramm ist eine Folge benachbarter Elemente, im Fall von Strings also aufeinanderfolgender Schriftzeichen. "N" bezeichnet die Länge der verwendeten Folgen; üblich sind Trigramme, also N-Gramme mit Länge 3.

Zur Ähnlichkeitsbestimmung werden zwei Strings in die in ihnen enthaltenen N-Gramme zerlegt, und die Größe der Schnittmenge der beiden N-Gramm-Mengen liefert den Wert für die Ähnlichkeit der Strings.

Lose Digramme sind eine von mir entwickelte Spielart von N-Grammen mit Länge 2, bei der die für N-Gramme normalerweise geltende Restriktion, wonach es sich um kontinuierliche Folgen von Elementen handeln muß, gelockert ist.

Eine Reihe von Parametern bestimmen den Grad der "Losheit" und beeinflussen darüber das Maß, in dem Störungen der Stringgleichheit (eingefügte Buchstaben, Buchstabendreher usw.) toleriert werden, und entsprechend die Differenziertheit des Ähnlichkeitswerts (Stichwort graceful degradation).

In der nachfolgenden Tabelle sind für den Vergleich eines Strings mit sieben anderen Strings die Ähnlichkeitswerte eingetragen, wie sie von den genannten Verfahren bestimmt werden.
Die Kommazahlen und Hintergrundfarben drücken den Grad der Ähnlichkeit aus:  1.0  bedeutet Gleichheit,  0.0  völlige Unähnlichkeit.

Alle acht Strings können Sie verändern, um die verschiedenen Verfahren auf ihre Stärken und Schwächen zu untersuchen!

Anm.: Dieser und die nachfolgenden Demonstratoren benötigen JavaScript und das Java-Plugin. Falls Sie das Java-Plugin nicht installiert haben: Bei http://java.com/ bekommen Sie die aktuelle Version.

Einen guten Eindruck von insbesondere der Differenzierungsleistung der Verfahren gibt auch die folgende Darstellung.

Hier wird eine Liste von Strings nach absteigender Ähnlichkeit mit einem anderen String sortiert. In der ersten Spalte sind die Vergleichswerte aufgeführt, in der zweiten der oder die String/s mit diesem Wert. Strings, die dieselbe Ähnlichkeit mit dem Vergleichsstring haben, stehen in derselben Zeile.

Wenn Sie den Vergleich mit unterschiedlichen Verfahren ausführen, wird an der Zahl der Zeilen und auch am Farbverlauf gut erkennbar, wie differenziert die Verfahren ihr Maß jeweils anlegen.

Die demonstrierten Verfahren haben unterschiedliche Stärken und Schwächen:

Editierabstand liefert ein sehr differenziertes Maß. Buchstabenverschiebungen, -einfügungen und -löschungen werden als kleine Störungen registriert und führen zu abgestuften Ähnlichkeitswerten.
Allerdings wird bei Verschiebungen die Verschiebungsdistanz nicht berücksichtigt, so daß weiträumige Umstellungen einzelner Buchstaben den Ähnlichkeitswert nicht so mindern, wie es menschlichem Ähnlichkeitsempfinden entsprechen würde.

Hamming liefert hohe Ähnlichkeitswerte für Strings, deren Teile positionsgleich korrespondieren. Ist im einen String weit vorn ein abweichendes Schriftzeichen eingefügt, bricht die Korrespondenz hart ab, ungeachtet aller nachfolgenden "schrägen" Übereinstimmungen. Hamming ist deshalb ein wenig tolerantes Maß, das unserem Ähnlichkeitsempfinden nicht gut entspricht.

N-Gramme liefern ein recht gutes Maß bei Strings, die wir als sehr ähnlich empfinden. Bei bestimmten Störungen, wie etwa Buchstabendrehern, reagieren N-Gramme aber stärker, als es nach menschlichem Empfinden angemessen erscheint. N-Gramme reagieren auch auf Störungen im Stringinneren empfindlicher als auf Störungen an den Rändern. Das gilt umso mehr, ein je größerer Wert für n verwendet wird.

Lose Digramme liefern sehr fein abgestufte Ähnlichkeitswerte. Auffällig ist die große Toleranz bei Buchstabendrehern und auch bei der Umstellung größerer Blöcke.

Einige Hinweise auf mögliche Anwendungsweisen für Verfahren der Ähnlichkeitsbestimmung:

In diesem Fall wird eine Eingabe durch ein Element aus einer Liste mit kanonischen Vorgaben ersetzt. Das kann entweder so aussehen, daß die Eingabe grundsätzlich durch die ihr nächstliegende Vorgabe ersetzt wird, oder daß das nur dann geschieht, wenn die Ähnlichkeit ein bestimmtes Mindestmaß hat:

In diesem Fall geht es darum, Eingaben zu erkennen, die einem Eintrag in einer gegebenen Liste hinreichend nah sind.

In der positiven Variante soll gemeldet werden, wenn eine Eingabe auf einen der vorgegebenen Einträge passt, z.B. wenn sie dem Namen eines bekannten Übeltäters verdächtig nahekommt:

Auch das Umgekehrte ist denkbar:
In der negativen Variante liefert das System eine Meldung, wenn die Eingabe auf keinen der vorgegebenen Einträge passt:

Methoden der Ähnlichkeitsberechnung erlauben nicht nur den 1:1-Vergleich zweier Zeichenketten, sondern auch die Suche einer Zeichenkette in umfangreichen Texten.

In der folgenden Darstellung wird der Text nach dem Grad der Übereinstimmung mit dem Suchstring farblich markiert:

Eine alternative Darstellung (in der Art einer sog. KWIC(=keyword in context)-Liste) zeigt die Treffer mit ihrer Position im Text, dem Grad der Ähnlichkeit und etwas Kontext an.
(Damit die Trefferzahl im Rahmen bleibt, wurde als Mindestähnlichkeit ein Wert von 0.5 festgelegt. Außerdem wird von mehreren ausreichend guten Matches, die einander überschneiden, nur der beste als Treffer gewertet.):

Die verschiedenen denkbaren Nutzungsformen unterscheiden sich z.T. in ihrer Dynamik:

1. Es gibt feststehende Strings, mit denen immer neue Strings verglichen werden (Szenario: "Prüfen und Melden", positiv oder negativ)
2. Es gibt feststehende Strings, mit denen in immer neuen Texten gesucht wird (Szenario: "Suchprofil anwenden")
3. Es gibt feststehende Texte, in denen mit immer neuen Strings gesucht wird (Szenario: "Info Retrieval")
4. Alles ist offen, das System wird ständig mit neuen Strings konfrontiert.

Im 1. und 2. Fall bietet es sich an, die immer wieder in Vergleiche einbezogenen Strings zu fuzzyfizieren und in diesem Zustand dauerhaft vorzuhalten.

Fuzzyfizierung ist allerdings nicht bei jedem Vergleichsverfahren möglich. Möglich ist sie bei den N-Gramm- und Lose-Digramm-Verfahren.

Im 1. Fall und wenn es sich um eine sehr große Zahl von Strings handelt, aus denen schnell das oder die zu einem gegebenen String ähnlichste/n ermittelt werden muß/müssen, kann sich (zusätzlich) der Aufbau eines Fuzzy-Index lohnen.

Es gibt verschiedene Konstruktionsweisen für einen Fuzzy-Index, die nicht alle mit jedem Vergleichsverfahren kombinierbar sind.

Ein Typus von Indizierung stützt sich darauf, daß die Fuzzyfizierung in der Zerlegung der Strings in ihre Eigenschaften und die Ähnlichkeitsbestimmung im Vergleich von Eigenschaftsmengen besteht. In diesem Fall werden die EIgenschaften mit ihren Vorkommen verzeigert.
Dieses Verfahren ist nicht anwendbar, wenn das Vergleichsverfahren auf einem anderen Prinzip als dem Vergleich von Eigenschaftsmengen besteht.

Eine andere Möglichkeit bietet das Clustering, bei dem Strings nach ihrer Ähnlichkeit in Gruppen gefasst werden. Beim Zugriff wird über den Vergleich des Zugriffsstrings mit den Gruppenzentren die nächstliegende Gruppe aufgesucht, und weitere Vergleiche können sich dann auf die Gruppenmitglieder beschränken.
Clustering-Methoden lassen sich mit allen Vergleichsverfahren kombinieren.

Ich habe mit der Referenz-Objekt-Methode eine Alternative entwickelt, die ebenfalls mit allen Vergleichsverfahren arbeiten kann.
Sie benötigt lediglich ein Vergleichsverfahren, aber keine Kenntnis von den jeweiligen Objekten und ihrem Aufbau, und nutzt Ähnlichkeiten einer zweiten Stufe, um einen eindimensionalen Index aufzubauen, mit dem sich der Suchraum beim Zugriff wesentlich verkleinern läßt.
Die Methode ist einsatzfähig und zeigt ansprechende Performance. Ein fundiertes Urteil über ihren relativen Wert gegenüber konkurrierenden Verfahren setzt weitere Untersuchungen und Praxistests voraus.

Lokale Integration: Direkte Einbindung des Moduls in ein Java-Programm, sei es eine Applikation, ein Servlet oder ein Applet.

Client/Server-Kopplung: Lockere Anbindung über einen entfernten Dienst: Die Ähnlichkeitsbestimmung arbeitet als separater Service und wird über eine Internet- Verbindung genutzt.
Die Kommunikation kann dabei mit Java-internen Mitteln oder programmiersprachübergreifend mit z.B. CORBA abgewickelt werden. (Mittelfristig ist auch denkbar, den Dienst als Web Service bereitzustellen.)

Integration in eine Web-Applikation: Das Fuzzy-Modul würde dabei entweder an ein Servlet gekoppelt (direkt oder in einem separaten Server) oder wie auf dieser Demoseite in ein Applet integriert. Resultate (z.B. Suchergebnisse) würden in diesem Fall typischerweise HTML-formatiert geliefert.

Synchrone Arbeitsweise: In manchen Fällen, wie z.B. bei der Suche, möchte ein Benutzer in jedem Fall und unmittelbar eine Antwort erhalten. Der Benutzer erteilt einen Auftrag an das Fuzzy-Modul, wartet, bis der Auftrag abgearbeitet ist, und nimmt dann das Ergebnis sofort entgegen.

Asynchrone Arbeitsweise: In anderen Fällen wird nicht mit einem interessanten Ergebnis gerechnet und deshalb die Abarbeitung des Auftrags auch nicht abgewartet. Das gilt z.B., wenn laufend große Mengen von Daten auf verdächtige Namen geprüft werden müssen, aber nur selten ein relevanter Fund gemacht wird. Das System könnte dann so eingerichtet werden, daß es im Fall der Fälle eine Meldung per E-Mail schickt, in eine Report-Datei oder eine Datenbank schreibt oder auch einen anderen Dienst benachrichtigt.

Berichtsformatierung: Resultate können in beliebiger Form übergeben werden, als einfacher Text, XML-formatiert, HTML-formatiert, in Form spezieller Java-Objekte (angepaßt an die Systemumgebung, möglicherweise Java-serialisiert), usw.

Datenintegration: Die Datenbasis, gegen die die Vergleiche ausgeführt werden sollen, kann aus Dateien gelesen werden, einfacher Text oder XML-formatiert sein, aus einer Datenbank stammen oder auch aus einer anderen Quelle mit eigener Form.

Wahl der Verfahren: Das Vergleichsverfahren kann passend zur jeweiligen Aufgabenstellung frei gewählt und parametrisiert werden.

Ich widme mich gern Ihrer speziellen Situation und Für mehr Information nehmen Sie bitte Kontakt mit mir auf!