Approximate string matching

rdf:langString Unscharfe Suche

rdf:langString 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.