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:
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:
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.
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.
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).
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.
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.
0.87 | richtnach |
0.83 | nachicht |
0.8 | nahcrihct |
0.78 | nachsicht |
0.73 | lachnicht, narricht |
0.54 | lichtan |
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.
Gerste |
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:
Al Capone !!! |
Mutter Teresa ??? |
In der folgenden Darstellung wird der Text nach dem Grad der Übereinstimmung mit dem Suchstring farblich markiert:
Position | Linker Kontext | Match | Rechter Kontext | Ähnlichkeit |
48...53 | avel lebte, um die Mitte des s | echze | hnten Jahrhunderts, ein Roßhän | 0.51 |
150...155 | ines Schulmeisters, einer der | recht | schaffensten zugleich und ents | 1.0 |
190...195 | fensten zugleich und entsetzli | chste | n Menschen seiner Zeit. - Dies | 0.5 |
471...476 | h durch sein Gewerbe ruhig ern | ährte | ; die Kinder, die ihm sein Wei | 0.5 |
536...541 | b schenkte, erzog er, in der F | urcht | Gottes, zur Arbeitsamkeit und | 0.67 |
581...586 | ur Arbeitsamkeit und Treue; ni | cht e | iner war unter seinen Nachbarn | 0.58 |
629...635 | r seinen Nachbarn, der sich ni | cht se | iner Wohltätigkeit, oder seine | 0.52 |
669...674 | Wohltätigkeit, oder seiner Ge | recht | igkeit erfreut hätte; kurz, di | 1.0 |
776...781 | ssen, wenn er in einer Tugend | nicht | ausgeschweift hätte. Das Rech | 0.5 |
807...812 | icht ausgeschweift hätte. Das | Recht | gefühl aber machte ihn zum Räu | 1.0 |
825...830 | hätte. Das Rechtgefühl aber m | achte | ihn zum Räuber und Mörder. | 0.58 |
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.