Quelltext der Seite Unscharfe Suche

[[Datei:Did you mean andré emotions.png|mini|Wikimedia Suche. Did you mean: andré emotions]]
Die '''unscharfe Suche''', auch '''Fuzzy-Suche''' oder '''Fuzzy-String-Suche''' genannt, umfasst in der [[Informatik]] eine Klasse von [[String-Matching-Algorithmus|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<ref>{{Internetquelle |autor=Jan Petzold |url=https://www.heise.de/developer/artikel/Groessere-Datenmengen-mit-JavaScript-performant-durchsuchen-2574182.html#mobile_detect_force_desktop |titel=Größere Datenmengen mit JavaScript performant durchsuchen |werk=heise Developer |hrsg=Heise Medien GmbH & Co. KG |datum=2015-03-13 |abruf=2020-04-29 |zitat=Ungenaue Suche (Fuzzy): Das Suchergebnis enthält auch Elemente, die dem Suchbegriff ähneln. Sie wird meist in Autocomplete-Feldern oder als Suchvorschlag verwendet (z.&nbsp;B. "Entwckler" findet auch "Entwickler").}}</ref> gefunden werden sollen.<ref>{{Internetquelle |url=https://www.itwissen.info/Fuzzy-Suche-fuzzy-search.html |titel=Fuzzy-Suche |werk=IT-Wissen.info |hrsg=DATACOM Buchverlag GmbH |abruf=2020-04-29 |zitat=Die Fuzzy-Search ist eine unscharfe oder fehlertolerante Suche. Im Gegensatz zu einer exakten Suche werden bei der Fuzzy-Suche auch dann Ergebnisse angezeigt, wenn das Suchwort fehlerhaft eingegeben wurde oder wenn die exakte Schreibweise des Suchwortes nicht bekannt ist.}}</ref> Ein bekanntes Maß zur Berechnung dieser Ähnlichkeit ist die sogenannte ''[[Levenshtein-Distanz]]''; sie gibt an, wie viele Operationen&nbsp;–&nbsp;Löschen, Einfügen und Ersetzen&nbsp;–&nbsp;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.<ref>{{Internetquelle |autor=Sonja Franz |url=https://www.integer-net.de/blog/wie-suchalgorithmen-funktionieren-levenshtein-distanz |titel=Wie Suchalgorithmen funktionieren: Die Levenshtein-Distanz |werk=interger_net |hrsg=integer_net GmbH |datum=2018-02-22 |abruf=2020-04-29| zitat=Die Levenshtein-Distanz beschreibt die minimale Anzahl von Änderungen, die nötig ist, um aus der ersten Zeichenkette die zweite Zeichenkette zu generieren. Als Änderungen gelten Hinzufügen, Entfernen und Austauschen von Zeichen. Sie ist benannt nach dem russischen Mathematiker Vladimir Levenshtein (1935–2017).}}</ref> Eine andere Möglichkeit beruht auf sogenannten [[N-Gramm]]en<ref>{{Internetquelle |autor=Tillmann Wegst |url=http://www.tillmann-wegst.de/fuzzy/ |titel=Stringähnlichkeit |werk=Tillmann Wegst // Software-Entwicklung |datum=2006-01-22 |abruf=2020-04-29 |zitat=N-Gramm-Übereinstimmungen sind ein weiteres und sehr gebräuchliches Maß. Ein N-Gramm ist eine Folge benachbarter Elemente, im Fall von Strings also aufeinanderfolgender Schriftzeichen. "N" bezeichnet die Länge der verwendeten Folgen; üblich sind Trigramme, also N-Gramme mit Länge 3. 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.}}</ref>, 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.<ref>{{Internetquelle |autor=Rob Gravelle |url=https://www.databasejournal.com/features/mysql/mysql-fuzzy-text-searching-using-the-soundex-function.html |titel=MySQL Fuzzy Text Searching Using the SOUNDEX Function |werk=DATABASE Journal |hrsg=QuinStreet Inc. |datum=2015-03-09 |abruf=2020-04-29 |sprache=en |zitat=Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. SOUNDEX codes from different strings can be compared to see how similar the strings sound when spoken.}}</ref>

Beide Ansätze erlauben es, gesuchte Zeichenketten auch dann zu finden, wenn zum Beispiel die genaue Schreibweise eines Namens oder Ausdrucks nicht bekannt ist, [[Flexion|flektierte]] Formen eines Wortes gefunden oder auch fehlertolerante Suchergebnisse akzeptiert werden sollen. Verwendet wird die Fuzzy-Suche beispielsweise in [[Datenbanksystem|Datenbanken]]<ref>{{Internetquelle |autor=Ernst August Wieden |url=http://wwwmatthes.in.tum.de/file/1rxjk9lb7qay3/sebis-Public-Website/Publications/Wied02.pdf |titel=Unscharfe Suche in Datenbanken – konzeptuelle Grundlagen, Systementwurf und prototypische Implementierung |werk=Diplomarbeit |hrsg=Technische Universität Hamburg-Harburg - Arbeitsbereich Softwaresysteme |datum=2002-08 |abruf=2020-04-30 |format=PDF |zitat=Diese Arbeit verfolgt das Ziel, den Abfragemechanismus von Datenbanken intelligenter zu gestalten; dies insbesondere in Hinblick auf den Einsatz von Fuzzy-Logic-Methoden, die bisher vorwiegend Einsatz in der Regelungstechnik finden.}}</ref>, [[Suchmaschine]]n<ref>{{Internetquelle |autor=Stefan Krempl |url=https://www.heise.de/newsticker/meldung/Fuzzy-Logic-erobert-das-Internet-158573.html |titel=Fuzzy Logic erobert das Internet |werk=heise online |hrsg=Heise Medien GmbH & Co. KG |datum=2005-05-04 |abruf=2020-04-30 |zitat="In den kommenden Jahren wird das Internet das wichtigste Anwendungsgebiet von Fuzzy Logic sein", erklärte Lotfi Zadeh in einem Vortrag an der TU Berlin. Der emeritierte Informatikprofessor der University of California in Berkeley geht davon aus, dass sich die teilweise noch recht "dummen" Suchmaschinen in hilfreiche Diener verwandeln, die fix auf alle erdenklichen Fragen eine passende Antwort finden. Dazu müssten sie aber erst die natürliche Sprache der Menschen "verstehen", was am besten mit Fuzzy Logic zu bewerkstelligen sei.}}</ref> oder [[Computerlinguistik|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 „Leven'''ss'''tein“ würde beispielsweise auch Einträge zu „Leven'''sh'''tein“ 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<ref>{{Internetquelle |autor=Benno Nieswand |url=http://www.levenshtein.de/ |titel=Levenshtein-Algorithmus - Wie funktioniert der Levenshtein-Algorithmus...? |werk=Levenshtein |abruf=2020-04-29 |zitat=Obwohl ausgeklügelte Verbesserungen bezüglich der Berechnung grosser Matrizen gemacht wurden, gibt es keine Alternative zu dem meist recht großen Berechnungsaufwand.}}</ref> 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-Algorithmus|Blast]].

== Siehe auch ==
* [[Grep #agrep|AGREP]]
* [[Fuzzy-Retrieval]]
* [[Regulärer Ausdruck]]
* [[Pattern Matching]]
* [[Kölner Phonetik]]
* [[Gestalt Pattern Matching]]

== Einzelnachweise ==
<references />

[[Kategorie:Künstliche Intelligenz]]
[[Kategorie:Information Retrieval]]