Fuzzy Search
Unscharfe Suche (Fuzzy Search) ist eine Suchtechnik, die Schreibvarianten toleriert und über Editierdistanz, N-Gramme oder phonetische Algorithmen ungefähre Treffer zuordnet.
Zweck
Auch bei Tippfehlern oder Varianten in der Benutzereingabe relevante Ergebnisse liefern und so das Sucherlebnis verbessern.
Mechanismus
Gängige Verfahren: Schwellwert-Matching über Levenshtein-Distanz, invertierte N-Gramm-Indizes, BK-tree-Beschleunigung, phonetisches Matching mit Soundex/Metaphone und der Bitap-Algorithmus. Implementierungen bieten u. a. fuse.js und die Elasticsearch-Fuzzy-Abfrage.
Anwendungsfälle
- Rechtschreibkorrektur in Suchmaschinen
- Autovervollständigung in der Kommandozeile
- Unscharfe Datenbankabfragen
- Codesuche (fehlertolerant)
Beispiele
- Eingabe
recieve → receiveOutputMatches receive (distance 2)Spelling correction
Häufige Fehler
- Overly loose thresholds cause too many false matches
- Adjust thresholds dynamically based on word length
Verwandte Begriffe
Levenshtein Distance
Die Levenshtein-Distanz ist die minimale Anzahl an Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, die nötig sind, um zwei Zeichenketten identisch zu machen. GLOSSAR
Soundex
Soundex ist ein phonetischer Algorithmus, der englische Namen nach Aussprache als einen Buchstaben plus drei Ziffern kodiert und ähnlich klingenden Namen denselben Code gibt; er dient der unscharfen Personennamensuche. GLOSSAR
N-gram
Ein N-Gramm ist eine Folge von N aufeinanderfolgenden Einheiten (Zeichen oder Wörter), aus einem Text gewonnen, verwendet in Sprachmodellen, Ähnlichkeit und Textanalyse. GLOSSAR
Edit Distance
Die Editierdistanz ist die minimale Anzahl einzeichenlicher Editieroperationen (Einfügen, Löschen, Ersetzen), um eine Zeichenkette in eine andere umzuwandeln; die Levenshtein-Distanz ist ihre häufigste Form. GLOSSAR