UX & Usability 22.2.2018

Wie Suchalgorithmen funktionieren: Die Levenshtein-Distanz

Eine gute Produktsuche in Online-Shops ist bei Schreibfehlern nachsichtig, sie findet trotz eines Vertippers die passenden Produkte, Kategorien oder sonstige Inhalte. Dahinter steckt ein Algorithmus, der den Suchbegriff mit den durchsuchbaren Begriffen oder Zeichenketten abgleicht. Die Unterschiede zwischen dem Suchbegriff und den Zeichenketten, beispielsweise dem Produktnamen, werden dabei mit der Levenshtein-Distanz gemessen.

Die Levenshtein-Distanz erklärt

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).

Beispiel

Die Levenshtein-Distanz zwischen den Begriffen "Levenshtein" und "Lewenstein" beträgt 2.

0. Lewenstein
1. Levenstein (ersetze v durch w)
2. Levenshtein (füge h ein)

Zwei identische Begriffe, wie zum Beispiel die Teekesselchen Schimmel und Schimmel, haben die Levenshtein-Distanz von 0.

Levenshtein-Distanz und Fuzzy Search

Die Konfiguration einer Produktsuche im Commerce-Bereich nutzt üblicherweise nicht den Begriff der Levenshtein-Distanz, sondern gibt Möglichkeiten zur Einstellung der unscharfen Suche ("Fuzzy Search"). Dabei geht es dann um die Sensibilität dieser unscharfen Suche. Je sensibler sie ist, desto geringer darf die Levenshtein-Distanz sein, damit unterschiedliche Begriffe noch als Übereinstimmung anerkannt werden.

Beispielsweise gab es in IntegerNet_Solr die Konfigurationseinstellung der Sensibilität der unscharfen Suche. Bei einem Wert von 1 ist die Sensibilität der Suche so hoch, dass keine unscharfe Suche durchgeführt wird. Der niedrigste Wert, den wir erlauben, ist 0. Bei diesem Wert ist die Sensibilität der unscharfen Suche so gering, dass praktisch jedes Produkt für jeden Suchbegriff als passend angesehen würde. Aus Sicht eines Kunden im Online-Shop ist das natürlich nicht der Fall.
Deshalb ist in der Regel eine Sensibilität zwischen 0,7 und 0,9 empfehlenswert.

Generell gilt: Je höher die Sensibilität der Suche, desto geringer ist die tolerierte Levenshtein-Distanz. Je geringer die Sensibilität der Suche, desto höher ist die tolerierte Levenshtein-Distanz.

Unscharfe Suche in Magento

Die Standardsuche von Magento kann keine unscharfe Suche durchführen. Sie sucht den Produktkatalog ausschließlich nach 100% mit dem Suchbegriff übereinstimmenden Zeichenketten ab. Sind keine 100%igen Übereinstimmungen zu finden, wird eine leere Suchergebnisseite angezeigt. Für Nutzer des Online-Shops ist das keine Hilfe.
Aus diesem Grund sind Extensions und Services für die Suche eine sinnvolle Ergänzung im Shop. Sie reduzieren das Frustpotential der Katalogsuche und helfen Kunden dabei, die gewünschten Produkte zu finden.

Die Grenzen der unscharfen Suche

Soll für einen Suchbegriff ein Produkt gefunden werden, in dessen Attributen dieser Begriff überhaupt nicht vorkommt, kann man zwar die unscharfe Suche so unsensibel konfigurieren, dass sie auch dieses Produkt als Ergebnis anzeigt. Jedoch führt man damit die Produktsuche durch zu viele unpassende Ergebnisse ad absurdum.
Für einen solchen Fall sind Synonyme das Mittel der Wahl. Doch dazu mehr in einem anderen Artikel.