Eine Suche, die Tippfehler verzeiht: wie Fehlertoleranz wirklich funktioniert

Das Problem, genau beschrieben

Wer nach „Kolibir“ sucht, meint mit ziemlicher Sicherheit „Kolibri“. Ein Suchfeld, das für diese Eingabe kein Ergebnis liefert, ist nicht aus gutem Grund streng: Es scheitert genau an dem, wofür es da ist, nämlich zu finden, was die Person meinte, und nicht nur, was sie getippt hat. Tippfehlertoleranz ist der Sammelbegriff für die Mechanismen, die diese Lücke schließen. Es klingt nach einer einzigen Funktion. In Wirklichkeit sind es mindestens zwei verschiedene Mechanismen, mit unterschiedlichen Kosten und unterschiedlichen Arten zu scheitern, und genau weil man sie verwechselt, machen die meisten naiven Umsetzungen Fehler.

Der Grundbaustein: die Editierdistanz

Fast alle Mechanismen zur Tippfehlertoleranz beruhen, egal in welcher Suchmaschine, auf demselben Grundgedanken: der Editierdistanz zwischen zwei Zeichenketten, meist der Levenshtein-Distanz. Sie zählt die Mindestzahl an Einfügungen, Löschungen oder Ersetzungen einzelner Zeichen, die nötig sind, um die eine Zeichenkette in die andere zu verwandeln. „Hemt“ ist eine Ersetzung von „Hemd“ entfernt. „Hmed“ statt „Hemd“, mit zwei vertauschten benachbarten Buchstaben, ist eine Transposition: zwei Edits nach der klassischen Definition von Levenshtein, nur eines in der Variante von Damerau-Levenshtein, die das Vertauschen als einen einzigen Edit zählt. Die Zahl allein entscheidet nichts; entscheidend ist, was das System daraus macht.

Ein Detail muss man von Anfang an klären: Eine Distanz von einem oder zwei Edits ist bei einem langen Wort großzügig und bei einem kurzen Wort gefährlich. Zwei Edits an einem Wort mit zehn Buchstaben verändern es kaum. Zwei Edits an einem Wort mit drei Buchstaben können daraus ein völlig anderes Wort machen: „Rad“ und „Rat“ sind einen Edit voneinander entfernt, „Rad“ und „Bad“ aber auch, ebenso „Rad“ und „Rand“. Ein System mit Fehlertoleranz, das unabhängig von der Wortlänge denselben Distanzschwellenwert anwendet, „korrigiert“ am Ende fröhlich kurze, ganz verschiedene Wörter ineinander. Die ehrliche Lösung ist ein Schwellenwert, der mit der Länge wächst: keine Korrektur bei sehr kurzen Wörtern, ein erlaubter Edit ab einigen Buchstaben, zwei Edits erst dann, wenn das Wort lang genug ist, um nach zwei Änderungen noch erkennbar zu bleiben.

Zwei verschiedene Mechanismen, oft zu einer Funktion vermengt

„Tippfehlertoleranz“ bezeichnet meist eines von zwei tatsächlich verschiedenen Dingen, und welches ein System anbietet, ändert, was es kann und was nicht.

1. Fuzzy-Abgleich zum Zeitpunkt der Abfrage

Elasticsearch, OpenSearch und ähnliche Suchmaschinen können eine fuzzy-Abfrage ausführen (oder den Parameter fuzziness einer match-Abfrage verwenden), die den gesuchten Begriff zum Zeitpunkt der Abfrage anhand der Editierdistanz mit den indexierten Begriffen vergleicht, ohne vorher wissen zu müssen, welche Fehler überhaupt vorkommen. Das funktioniert, weil die Suchmaschine bereits einen invertierten Index aller im Katalog vorhandenen Begriffe besitzt; eine Fuzzy-Abfrage läuft im Kern auf „finde die indexierten Begriffe, die höchstens N Edits von diesem entfernt sind, und sortiere die Treffer nach ihrer Nähe“ hinaus. Sie braucht keinen eigenen Pflegeschritt und lässt nach: Eine leicht falsche Eingabe reiht die nächstliegenden indexierten Begriffe trotzdem ganz oben ein. Ihre wahren Kosten zeigen sich bei einem Feld mit hoher Kardinalität oder einem sehr großen Vokabular, wo die Berechnung der Editierdistanz über eine große Menge von Kandidaten aufwendiger ist als eine Suche nach dem exakten Begriff; deshalb wird der Fuzzy-Abgleich meist selektiv eingesetzt (auf das Haupt-Freitextfeld, nicht auf jedes Schlüsselwortfeld) und nicht standardmäßig überall.

2. Wörterbuchkorrektur, nur dann angewandt, wenn sie nötig ist

Ein System ohne Suchmaschine, die Fuzzy-Treffer von Haus aus bewerten kann, zum Beispiel eine einfache SQL-basierte Suche, muss den Mechanismus selbst bauen: ein Wörterbuch gültiger Begriffe, aus den Produkt- und Markennamen des Katalogs aufgebaut, mit dem ein Suchbegriff, der nichts gefunden hat, verglichen wird, um das echte nächstliegende Wort zu finden. Das Wörterbuch wird üblicherweise über Zeichen-Trigramme (Fragmente aus drei Buchstaben) indexiert, statt Buchstabe für Buchstabe mit jedem Wort verglichen zu werden: einerseits, weil ein Trigramm-Index die Liste der Kandidaten auf die plausibel naheliegenden Wörter verkleinert, bevor die exakte Editierdistanz auf einer viel kleineren Menge berechnet wird, andererseits, weil er keine externe Suchmaschine verlangt.

Das Detail, das diesen Ansatz in der Praxis günstig macht, statt ihn zur Performance-Falle werden zu lassen, ist der Zeitpunkt, an dem die Wörterbuchsuche läuft. Müsste jede Suche die Kosten einer Wörterbuchabfrage tragen, würde die Fehlertoleranz alle Abfragen verlangsamen, auch die richtig getippten, die ohnehin schon Treffer fanden. Die Abfrage hat nur dann einen Grund zu laufen, wenn die exakte Suche leer zurückgekommen ist: Eine korrekte Eingabe berührt sie nie, und nur der Fall ohne Treffer zahlt den Aufpreis. An einem echten Katalog gemessen, brauchten eine richtig geschriebene Eingabe und eine falsch geschriebene, die die Wörterbuchabfrage auslöst, in beiden Fällen dieselbe, geringe Zeit (beide zwischen 0,16 und 0,19 Sekunden auf genau dieser Installation): Der Wörterbuchpfad verursacht nur bei Suchen Kosten, die sonst gar nichts geliefert hätten.

Das Wörterbuch braucht außerdem eine Pflege, die eine Fuzzy-Abfrage nicht braucht: Es muss neue Wörter lernen, wenn der Katalog wächst, und die Wörter von Produkten vergessen, die es nicht mehr gibt, sonst veraltet es langsam und beginnt, Korrekturen zu aufgegebenen Produkten vorzuschlagen. Ein Wörterbuch, das nach Plan neu aufgebaut wird (zum Beispiel jede Woche, dazu eine Ergänzung auf Abruf, wenn eine Suche ohne Treffer zum ersten Mal ein Wort braucht, das es noch nicht kennt), bleibt auf den Katalog abgestimmt, ohne bei jeder Abfrage neu aufgebaut zu werden.

Wo die einfache Version scheitert

• Ein fester Schwellenwert der Editierdistanz für Wörter jeder Länge, wie oben gesehen: Eine großzügige Korrektur bei kurzen Wörtern verwandelt verschiedene Wörter ineinander.
• Eine Eingabe korrigieren, die schon Treffer hat. Wird eine Suche, die bereits Produkte gefunden hat, zusätzlich auf einen anderen, beliebteren Begriff „korrigiert“, kann der Kunde von dem weggeführt werden, was er wirklich getippt hat, und zu dem geschickt werden, was die Suchmaschine für nah und beliebt hält. Die Korrektur gehört hinter eine echte Suche ohne Treffer, nicht als dauerhaftes Umschreiben jeder Eingabe im Hintergrund.
• Eine Korrektur, die stillschweigend anspringt, obwohl sie es nicht sollte. Auf einer Seite mit Facettennavigation kann eine Filterauswahl zu Recht null Treffer ergeben (ein Kunde hat eine Kombination aus Größe und Farbe gewählt, die niemand vorrätig hat). Das ist kein Rechtschreibproblem, und eine Fehlertoleranz-Schicht, die den Unterschied nicht erkennt, versucht, einen einwandfrei geschriebenen Begriff zu „korrigieren“, weil die Filter und nicht das Wort die Seite geleert haben.
• Sich darauf verlassen, dass der Fuzzy-Abgleich auch richtige Facetten sicherstellt. Dafür zu sorgen, dass eine falsch geschriebene Eingabe trotzdem Produkte findet, ist ein anderes Problem, als korrekt zu zählen, wie viele Produkte zu jedem Filterwert passen. Eine fehlertolerante Suchmaschine, die für „Kolibir“ Ergebnisse findet, berechnet die Facettenzahlen bedenkenlos für genau diesen Fuzzy-Treffer; geht ein nachgelagertes Element (etwa eine Autovervollständigung mit „beliebten Suchanfragen“) davon aus, dass „mindestens ein Produkt gefunden“ bedeutet „das war ein echter, richtig geschriebener Begriff“, veröffentlicht es die Tippfehler des Shops bereitwillig bei jedem Besucher. Gerade weil die tolerante Suchmaschine ihre Arbeit gut macht, passiert dieser Fehler an anderer Stelle desselben Systems so leicht.
• Schweigen statt Transparenz. Eine Suche, die den getippten Begriff stillschweigend durch einen anderen ersetzt, ohne anzuzeigen, dass eine Ersetzung stattgefunden hat, lässt den Kunden rätseln, warum die Ergebnisse nicht ganz zu dem passen, wonach er gesucht hat. Eine sichtbare, ehrliche Zeile, „Keine Ergebnisse für X. Hier sind die Ergebnisse für Y“, kostet einen Satz und erspart diese Verwirrung vollständig.

Eine kurze Checkliste

• Passen Sie die erlaubte Editierdistanz an die Wortlänge an; wenden Sie nicht denselben Schwellenwert auf ein Wort mit drei Buchstaben und eines mit zwölf an.
• Korrigieren Sie nur nach einer echten Suche ohne Treffer, niemals durch stilles Umschreiben einer Eingabe, die bereits etwas gefunden hatte.
• Unterscheiden Sie „das Wort war falsch geschrieben“ von „die Filter haben die Seite geleert“: Beides verlangt eine andere Behandlung, und wer sie verwechselt, erzeugt einen Korrekturversuch, wo keiner hingehörte.
• Wenn Sie ein eigenes Wörterbuch pflegen, statt sich auf das eingebaute Fuzzy-Scoring einer Suchmaschine zu stützen, halten Sie es aktuell: Bauen Sie es nach Plan neu auf und lassen Sie es vom Katalog lernen, wenn dieser sich ändert, sonst schlägt es bald Wörter vor, die es nicht mehr gibt.
• Sagen Sie dem Kunden, wenn eine Ersetzung stattgefunden hat. Lassen Sie einen „erfolgreichen“ Fuzzy-Treffer nicht verdecken, dass das, was er getippt hat, und das, was er bekommen hat, nicht dasselbe Wort sind.

Kurz gesagt

Tippfehlertoleranz ist kein Schalter für an oder aus: Es ist die Wahl zwischen zwei verschiedenen Mechanismen, dem nativen Fuzzy-Abgleich der Suchmaschine zum Zeitpunkt der Abfrage oder einem gepflegten Wörterbuch, das nur bei einer echten Suche ohne Treffer befragt wird, jeder mit eigenen Kosten und einer eigenen Art, sich unbemerkt zu irren. Die beiden Fehler, auf die Sie achten sollten, sind, Wörter zu korrigieren, die gar nicht falsch geschrieben waren, und sich darauf zu verlassen, dass ein Fuzzy-Abgleich Fragen beantwortet, für die er nicht gebaut wurde, etwa eine exakte Facettenzählung. Wir lösen das in cll_essearch, unserem Modul für Suche und Facettennavigation für PrestaShop, sowohl mit dem nativen Fuzzy-Abgleich von Elasticsearch als auch mit unserem eigenen Trigramm-Wörterbuch für Shops, die die native Suche der Datenbank nutzen, falls Sie sehen möchten, wie diese Unterscheidung in einem echten Onlineshop umgesetzt wird.

Elasticsearch Suche und Facettierte NavigationBlitzschnelle, tippfehlertolerante Suche mit moderner facettierter Navigation im modalen Filterpanel, mit der…99,99 €Produkt ansehen