Fuzzy-Suche

Die Fuzzy-Suche oder Fuzzy-String-Suche umfasst in der Informatik eine Klasse von String-Matching-Algorithmen, die eine bestimmte Zeichenkette (engl. string) in einer längeren Zeichenkette oder einem Text suchen bzw. finden sollen.

Typisch für die „unscharfe“ (engl. fuzzy) Suchmethode ist dabei, dass nicht die exakte Zeichenfolge als Suchkriterium zugrunde gelegt werden muss, sondern auch ähnliche Zeichenketten gefunden werden sollen. Ein bekanntes Maß zur Berechnung dieser Ähnlichkeit ist die sogenannte Levenshtein-Distanz; sie gibt an, wieviele Operationen – zum Beispiel Austauschen, Verschieben von Buchstaben in Wörtern – nötig sind, um einen String aus dem anderen herzuleiten: Je weniger Operationen benötigt werden, desto ähnlicher sind beide Strings. Eine andere Möglichkeit beruht auf sogenannten N-Grammen, mittels derer über bestimmte Wahrscheinlichkeiten berechnet wird, welche Buchstaben- oder Zeichenkettenkombination auf eine andere folgen könnte.

Ein weiterer Ansatz gründet nicht direkt auf der grafischen Repräsentation eines Wortes, sondern es wird nach Zeichenfolgen gesucht, die gleich klingen: die phonetische Suche. Ein in diesem Zusammenhang bekanntes Verfahren, das Wörter ihrem Klang nach indiziert, ist für das Englische der Soundex-Algorithmus.

Beide Ansätze erlauben es, gesuchte Zeichenketten auch dann zu finden, wenn zum Beispiel die genaue Schreibweise eines Namens oder Ausdrucks nicht bekannt ist, flektierte Formen eines Wortes gefunden oder auch fehlertolerante Suchergebnisse akzeptiert werden sollen. Verwendet wird die Fuzzy-Suche beispielsweise in Datenbanken, Suchmaschinen oder computerlinguistischen Anwendungen.

Praxisbeispiel

Bei der Suche in Datenbanken können fehlertolerante Suchwerkzeuge unter Anwendung von String-Matching-Algorithmen Tipp- und Rechtschreibfehler ausgleichen. Ähnlichkeiten zwischen dem eingegebenen Suchbegriff und den Einträgen in der Datenbank werden auch ohne hinterlegte Wortlisten ermittelt. Treffer können nach Relevanz und Nähe zum Suchbegriff sortiert ausgegeben werden. Die Suche nach dem Begriff „Levensstein“ würde beispielsweise auch Einträge zu „Levenshtein“ finden. Werden Synonyme-Listen hinterlegt, findet die unscharfe Suche beispielsweise zu dem Begriff „Fernseher“ auch Begriffe wie „Fernsehgerät“.

Die Anwendung aufwändiger String-Matching-Verfahren, wie dem Levenshtein- Algorithmus, geht in der Regel mit einem enormen Berechnungsaufwand einher und führt bei großen Datenmengen zu einer oft hohen zeitlichen Verzögerung. Der Firma Exorbyte ist es nach Eigenaussagen als erstes gelungen, mit dem Levenshtein-Algorithmus String-Abgleiche auf einer Datenbasis von z.B. 2,5 Mio. Daten unter 10 Millisekunden durchzuführen.

Siehe auch

AGREP, Fuzzy-Retrieval, Regulärer Ausdruck, Pattern Matching, Kölner Phonetik