SQL Suche nach Ähnlichkeit

[Regina Schlauklug]

Mit den Funktionen, die Datenbanken zur Verfügung stellen, habe ich überwiegend schlechte Erfahrungen gemacht. Schlimmer noch als zu viele unpassende Vorschläge war, dass oft genug gar keine kamen, obwohl welche hätten kommen müssen. Sprich: Was ich als ähnlich empfand, war oft genug nicht das, was auch die Datenbank für ähnlich hielt. Sich durch einen Wurst an Vorschlägen wühlen zu müssen, ist unbequem, Einträge doppelt und dreifach anzulegen, weil die passenden Vorschläge nicht kamen, ist hingegen ein Problem.

Schlussendlich bin ich dann auf N-Gramme umgestiegen. Die Daten werden in Zwei- bis Drei-Buchstaben-Stücke zerlegt (Sophie -> so, sop, oph, phi, hie, ie) und diese in einer separaten Tabelle gespeichert.
Das Suchwort wird auf die gleiche Weise zerlegt. Die Stücke des Suchwortes werden in dem Datenstückwust gezählt und mit ihren Daten aufsummiert. Je höher die Summe eines Datums, d.h. je mehr Treffer ein Datum erzielt, desto besser passt es zum Suchwort.

Die Datenhaltung ist natürlich etwas aufwändiger, aber das Ergebnis gemessen am simplen Prinzip meines Erachtens bisweilen erstaunlich – und allemal besser als soundex(), levenshtein() & Co.

Beispiel:

Suchwort sof   -> so sof of
         sofi  -> so sof ofi fi
         sofia -> so sof ofi fia ia
         sofie -> so sof ofi fie ie

                                  sof  sofi  sofia  sofie
Sophie -> so sop oph phi hie ie    1     1     1      2
Sofie  -> so sof ofi fie ie        2     3     1      5
Sophia -> so sop oph phi hia ia    1     1     2      1

Das Ganze lässt sich natürlich noch verfeinern, manche verwenden Stücke à bis zu vier Buchstaben, manche zählen Worttrennungen oder Anfangs- und Endebezeichner mit und sogar höherwertig. Ob der Aufwand den Nutzen rechtfertigt, hängt sicher vom Einsatzzweck ab. Sinnig dürfte als Erstes eine Normalisierung der Daten sein; im Beispiel oben habe ich nur Kleinbuchstaben verwendet, das Entfernen von Satzzeichen bzw. Ersetzen durch ein Leerzeichen kann auch merklich helfen.