Unscharfe Suche
# Unscharfe Suche

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

Typisch für die „unscharfe“ (englisch 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, wie viele Operationen – Löschen, Einfügen und Ersetzen – 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 für die Englische Sprache, das Wörter ihrem Klang nach indiziert, ist 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.

## Praxisbeispiele

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 Synonym-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.

Beispielsweise in der Bioinformatik, werden Gensequenzen mit Gendatenbanken abgeglichen. Eine bekannte Sammlung von Algorithmen hierfür ist Blast.

