Fuzzy Suche

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


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Fuzzy — Fuzzy, nach dem englischen Wort für unscharf, verschwommen, kann sich auf Folgendes beziehen: Fuzzy Klassifikator Fuzzy C Means Fuzzy Logik Fuzzy Bit Fuzzy Regler Fuzzy Retrieval Fuzzy Suche Fuzzy Lokalisierung = unscharfe Lokalisierung Weitere… …   Deutsch Wikipedia

  • Fuzzy-Logik — Fuzzylogik (engl. fuzzy ‚verschwommen‘, fuzzy logic, fuzzy theory ‚verschwommene Logik‘ bzw. ‚verschwommene Theorie‘) ist eine Theorie, welche vor allem für die Modellierung von Unsicherheiten und Unschärfen von umgangssprachlichen Beschreibungen …   Deutsch Wikipedia

  • Fuzzy-Menge — Fuzzylogik (engl. fuzzy ‚verschwommen‘, fuzzy logic, fuzzy theory ‚verschwommene Logik‘ bzw. ‚verschwommene Theorie‘) ist eine Theorie, welche vor allem für die Modellierung von Unsicherheiten und Unschärfen von umgangssprachlichen Beschreibungen …   Deutsch Wikipedia

  • Fuzzy-Retrieval — Das Fuzzy Information Retrieval hat sich seit den 70er Jahren entwickelt. Hier benennt Fuzzy Information Retrieval ein Information Retrieval, das auf der Fuzzy Logik basiert. Inhaltsverzeichnis 1 Das Fuzzy IR Modell 2 Erweiterte Fuzzy IR Modelle… …   Deutsch Wikipedia

  • Fuzzy Logic — Fuzzylogik (engl. fuzzy ‚verschwommen‘, fuzzy logic, fuzzy theory ‚verschwommene Logik‘ bzw. ‚verschwommene Theorie‘) ist eine Theorie, welche vor allem für die Modellierung von Unsicherheiten und Unschärfen von umgangssprachlichen Beschreibungen …   Deutsch Wikipedia

  • Fuzzy Logik — Fuzzylogik (engl. fuzzy ‚verschwommen‘, fuzzy logic, fuzzy theory ‚verschwommene Logik‘ bzw. ‚verschwommene Theorie‘) ist eine Theorie, welche vor allem für die Modellierung von Unsicherheiten und Unschärfen von umgangssprachlichen Beschreibungen …   Deutsch Wikipedia

  • Fuzzy logic — Fuzzylogik (engl. fuzzy ‚verschwommen‘, fuzzy logic, fuzzy theory ‚verschwommene Logik‘ bzw. ‚verschwommene Theorie‘) ist eine Theorie, welche vor allem für die Modellierung von Unsicherheiten und Unschärfen von umgangssprachlichen Beschreibungen …   Deutsch Wikipedia

  • Fuzzy Retrieval — Das Fuzzy Information Retrieval hat sich seit den 70er Jahren entwickelt. Hier benennt Fuzzy Information Retrieval ein Information Retrieval, das auf der Fuzzy Logik basiert. Inhaltsverzeichnis 1 Das Fuzzy IR Modell 2 Erweiterte Fuzzy IR Modelle… …   Deutsch Wikipedia

  • Unscharfe 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”