Suchen aber mit Suggest

Vorschlagssuchen sind beliebte Mittel, um Nutzern im Web gezielt Informationen bieten zu können, doch Suche ist nicht gleich Suche. Die einfachste Methode ist eine Suche im Text der indizierten Daten nach der Suchanfrage.

Weiterhin müssen Regeln definiert werden, wie eine Suchanfrage interpretiert werden soll. Nehmen wir an, der Nutzer sendet als Suchanfrage den Text "inteligente Suggest Suche".

Fall 1: Der Nutzer erhält keine Ergebnisse.

Ursache:
Der Suchindex der Suchmaschine enthält den falschen Text, schließlich hat der Verfasser der Information auf seine Rechtschreibung geachtet und schreibt "intelligente" statt "inteligente". Der Suchtext wird zerlegt in einzelne Anfragen, welche im Nachfolgenden per UND verknüpft werden, es wird also nach dem Vorkommen aller eingegeben Wörter im Index der Datenbank gesucht.

Beispiel:
SELECT beschreibung FROM datenbank WHERE beschreibung LIKE '%inteligente%'  AND beschreibung LIKE '%Suggest%' AND beschreibung LIKE '%Suche%'

Diese Suche kommt ohne dem Erzeugen eines aufwändigen Suchindex' aus, es wird nach dem Vorkommen bestimmter Teilwörter innerhalb des Suchtextes gesucht. Diese Form der Suche ist einfach zu implementieren und trifft im Großteil der Anfragen auch relevante Informationen, auch kurze Suchanfragen wie"123" oder "der" sind möglich. Diese Methode unterschlägt jedoch jene Treffer, welche eines der gesuchten Wörter nicht enthält, Schreib-/Tippfehler innerhalb des Anfrage und Suchtextes enthalten. Weiterhin wird keine Unterscheidung nach Einzahl oder Mehrzahl eines Wortes getroffen. Die Reihenfolge und Relevanz der Suche kann ohne zusätzliche Parameter nicht automatisch erfolgen. Ein weiterer Kritikpunkt ist die Geschwindigkeit der Anfrage. Eine kleine Datenbank mit wenigen Inhalten (bis ca. 10.000-20.000 Datensätzen) kann mit solchen Daten noch in akzeptabler Geschwindigkeit antworten. Größere Datenbanken werden hierbei mit jedem Suchwort langsamer, da innerhalb des Suchraumes nach allen Vorkommen und Teilwörtern gesucht werden muss, und das in allen Datensätzen!!!

Fall 2: Der Nutzer erhält undefinierbare Ergebnisse.

Ursache:
Die Suche wird automatisch erweitert um ähnliche und gleichlautende Wörter, zusätzlich wird das Ergebnis in einer nicht nachvollziehbaren Weise sortiert und relevante Informationen verschwinden an das Ende der Ergebnismenge. Die Indexerzeugung und die Suchmethode können (nur schwer) beeinflusst werden und liefern daher eher unvorhersehbare Ergebnisse. Als Beispiel sei hier die MySQL-Volltextsuche genannt. Die Suche und die Indexerzeugung können serverseitig durch eine Konfigurationsdatei eingestellt werden, im Normalfall (auf Shared Hosts) ist diese Einstellung fix und kann nicht vom Kunden geändert werden. Der Index wird transparent erzeugt und von MySQL intern verwaltet. Der Index enthält nur Wörter, die bestimmten Kriterien  entsprechen, wie die 50%-Marke und die Mindestzeichenlänge von 3 Zeichen für ein Wort. Worttrennzeichen können nur durch Anpassung der Konfiguration verändert werden. Vorteil dieser Methode ist, dass eine relevanzabhängige Sortierung erfolgen kann, die Berechnung der Relevanz wird jedoch von MySQL intern geregelt und ist vom Nutzer nicht beeinflussbar.

Fall 3: Der Nutzer erhält zu viele Ergebnisse.

Ursache:
Der Suchtext wurde zerlegt in einzelne Worte, diese wurden per ODER verknüpft. Dies hat zur Folge das Nutzer, welche ihre Suche durch Hinzufügen weiterer Begriffe einschränken möchten, im Grunde das Gegenteil erreichen. Dieses Vorgehen ist im Internet jedoch nur noch selten zu finden, da die angezeigten Ergebnisse dazu führen, dass Nutzer von den Resultaten erschlagen werden. Den einzigen noch einigermaßen plausiblen Anwendungsfall kann man damit erklären, dass der Betreiber in der Datenbank zu wenig Informationen hält, und dem Nutzer wenigstens diese anzeigen möchte, die seiner Suche am nähesten kommen. In diesem Fall sollte man eine Suchfunktion eher vermeiden und überlegen, ob eine andere Informationsstrukturierung angemessener ist.

Beispiel:
SELECT beschreibung FROM datenbank WHERE beschreibung LIKE '%inteligente%'  OR beschreibung LIKE '%Suggest%' OR beschreibung LIKE '%Suche%'

Fall 4: Der Nutzer erhält relevante Informationen zum gesuchten Suchbegriff

Dies ist der oft gewünschte und selten zu 100% erreichte Fall. Eine Möglichkeit ist das Anlegen eines fehlerkorrigierenden Suchindex'. Diese Methode beruht ebenfalls auf dem Anlegen eines Einzelwortindex, jedoch wurde dieser modifiziert um zusätzlich Tippfehler und Teilwörter zu erkennen. Die Erzeugung des Index ist dabei der aufwändigste Teil der Methode. Zuerst wird der zu indizierende Text in einzelne Wörter zerlegt (Einzelwörter werden anhand von Trennzeichen zerlegt), danach wird jedes einzelne Wort an den Datenbankindex gesendet um zu ermitteln, ob dieses schon vorhanden ist. Ist das zu indizierende Wort noch nicht enthalten, kommt ein Algorithmus zum tragen, der das Wort in Teilwörter und ähnliche Wörter zerlegt.

Am Beispiel des Wortes "Element" können wird dieses Verfahren kurz vorstellen: 

1.
Ermittlung der Wörter mit der Länge 1, danach Ermittlung aller Teilwörter der Länge 2 usw. bis Wörter der Länge Wortlänge-1. Man erhält eine neue Liste von Wörtern, die wie folgt aussehen (doppelte auftretende Wörter können entfernt werden):
E,l,e,m,n,t,El,le,em,me,en,nt,Ele,lem,eme,men,ent,....,Elemen,lement

2.
Buchstaben entfernen für Wörter dessen Länge > 2 Zeichen ist (Schreibfehler mit Weglassung eines einzelnen Zeichens oder mehr), man erhält zusätzliche Wörter wie:
..., nt,et,ee,mn, Eement, Elment, Eleent, Elemnt, Elemet,...

3.
Buchstabendreher simulieren, man erhält folgende zusätzliche Wörter:
....,lEement,Eelment,Elmeent,Eleemnt,Elemnet,Elemetn,...

4.
Abschließende Bereinigung der erhaltenen Suggest Datenbasis, indem Suggesteinträge entfernt werden, welche zu viele Resultate liefern würden, wie Einzelbuchstaben oder kurze Suggest Wörter mit weniger als 3 Buchstaben, deren zugehöriges Orginalwort mehr als 6 Buchstaben enthält.

Da die Menge an zu indizierenden Wörtern mit jedem zusätzlichen Buchstaben des aufzunehemenden Wortes sehr schnell in unhandliche Größenordnungen expandieren kann, sollten lange Wörter leicht modifiziert behandelt werden.

Die  so ermittelten Wörter gelangen in einen Suchindex (mit einer zusätzlichen Gewichtung, diese ist abhängig von der Ähnlichkeit zum Orginalwort), man erhält also einen Suggest / Korrekturindex zu einem Text, dieser wird nur einmal für die in einem Text enthaltenen Wörter erzeugt und kann von anderen Texten referenziert werden. Die Ähnlichkeit eines Wortes zu dem Orginalwort kann durch eine Gewichtung ausgedrückt werden. Nach dieser Gewichtung können nun die Orginaltexte sortiert werden. Die Abfrage der Suggest Tabelle erfolgt mit einfachen "SELECT text FROM ... WHERE suggest='Elemnt'" erfolgen => diese Abfragen können von der verwendeten Datenbank mit korrekt gesetzten Indexspalten sehr schnell verarbeitet werden. So kann über das referenzierte Orginalwort schnell auf den gesuchten Datensatz, der dieses Wort enthält, geschlossen werden. Ähnliche Wörter (also Wörter mit Tippfehler) können über das Originalwort referenziert werden.

Fazit:

Jede Suche besitzt gewisse Vor- und Nachteile und muss auf den konkreten Anwendungsfall abgestimmt werden.

Links und Quellen:
http://dev.mysql.com/doc/refman/5.1/de/fulltext-search.html
http://dev.mysql.com/doc/refman/5.1/de/fulltext-query-expansion.html
http://dev.mysql.com/doc/refman/5.1/de/fulltext-fine-tuning.html
http://dev.mysql.com/doc/refman/5.1/de/fulltext-stopwords.html
http://dev.mysql.com/doc/refman/5.1/de/fulltext-boolean.html
http://dev.mysql.com/doc/refman/5.1/de/plugin-api.html
http://dev.mysql.com/doc/refman/5.1/de/plugin-full-text-plugins.html