Back to top

Suchassistenten - Automatische Vervollständigung, Vorschläge, Suche und mehr

Als Google im Jahr 1999 die erste Version ihrer automatischen Vervollständigung einer Suchmaschine veröffentlichte, war dies eines der am meistdiskutierten Themen beim damaligen Verity Forum. Im Verlauf der Zeit hat sich diese Technologie stark weiterentwickelt und ist weiterhin sehr beliebt. Das Eingabefeld und die Dropdown-Box sind weitestgehend gleich geblieben, allerdings haben sich die Technologien und Strategien, die im Hintergrund verwendet werden, sehr verändert. Ich habe mir die verschiedenen Ansätze angesehen und auch solche Technologien betrachtet, die wir in der Zukunft erwarten können.

Erfolgsfaktoren

suchassistenten.jpgEgal wie gut eine bestimmte Implementierung sein mag, manche Erfolgsfaktoren müssen von allen berücksichtigt werden. Ich möchte zunächst auf diese eingehen bevor ich die Technologien selbst betrachte:

  • Suchassistenten müssen schnell sein: Ein Nutzer kann mehrere Tasten pro Sekunde drücken und die Vorschläge müssen genauso schnell erscheinen – dies erfordert eine gute Netzwerkinfrastruktur, schlanke Protokolle und evtl. Logik um Vorschläge nur dann anzufordern, wenn eine „Tipp-Pause“ erkannt wird.
  • Jedes vorgeschlagene Wort muss auch zu Treffern führen – dies ist insbesondere in Umgebungen wichtig, in denen Zugriffsberechtigungen berücksichtigt werden müssen. Sie würden niemals einem System vertrauen, dass Ihnen rät am Ende der Straße links abzubiegen – und die Straße stellt sich als Sackgasse heraus!
  • Die Datenbank der Assistenten muss mit dem Suchindex synchron sein. Sobald neue Worte oder Ausdrücke in den Index übernommen werden, müssen diese auch als Vorschläge verfügbar sein. Vor zwei Jahren (2015) hätte z.B. niemand geglaubt, Dieselgate wäre ein sinnvoller Vorschlag.
  • Nutzer müssen sofort verstehen warum ein Begriff vorgeschlagen wurde. Das bedeutet, dass alle Wörterbücher, Thesauri und Datenmodelle gut gepflegt sein müssen.
  • Versuchen Sie „Meinten Sie“ („Did You Mean“) zu vermeiden: Obwohl dies eine hervorragende Funktion ist (sowohl mit und ohne automatische Anpassung der Suchbegriffe), sollten die Vorschläge bereits so gut sein, dass sie richtig geschrieben sind und die erwarteten Suchresultate liefern. 

Automatische Vervollständigung

Automatische Vervollständigung (Auto-Complete) war die erste Generation dieser Assistenten. Es wurde einfach der invertierte Index (d.h. die Wortliste) verwendet, um Worte zu finden, die zu den bereits getippten Zeichen passen. Die relevantesten Vorschläge wurden mit Hilfe der Wortfrequenz ausgewählt. Dies war ein großer Fortschritt gegenüber einer Eingabebox, die schlicht Text entgegennimmt: Man muss nicht mehr das vollständige Wort tippen und es ist garantiert, dass für den vorgeschlagenen Begriff Dokumente gefunden werden – zugegeben: in einer Umgebung, in der Zugriffsberechtigungen verwendet werden, trifft dies leider nicht immer zu.

Automatische Vorschläge

Ziemlich bald stellte sich heraus, dass es nicht ausreicht, nur Worte vorzuschlagen, die mit den gleichen Buchstaben beginnen. Benutzer wollten wirkliche Vorschläge, selbst wenn sie die genaue Schreibweise nicht kennen – oder wüssten Sie auf Anhieb wie José Manuel Barrosos1 Nachname richtig geschrieben wird?

Hier kommen unscharfe Vorschläge basierend auf der Levenshtein Distanz oder Teilübereinstimmungen mit Hilfe von N-Grammen ins Spiel. Je nach Konfiguration würde Ihnen während Sie tippen eine Liste inklusive Barroso und Garros2 präsentiert.

In diesem Fall basieren die Vorschläge auf einem speziellen Indexfeld, das allein dazu dient die vorgeschlagenen Begriffe zu kontrollieren. Dieser Ansatz bietet die folgenden Vorteile:

  • Es ist möglich auch Phrasen (Zitate) statt nur einzelner Worte vorzuschlagen.
  • Kategorien, die in einem weiteren Indexfeld abgelegt wurden, können auch vorgeschlagen werden.
  • Vorhanden Suchmaschinenfunktionen wie Synonyme und Thesauri können mitgenutzt werden.
  • Zugriffsberechtigungen können berücksichtigt werden.

Automatische Suche

In manchen Datenquellen, meist mit sehr kleinen Dokumenten, ist eine automatische Suche effizienter als Vorschläge zu machen. Besonders beim Blättern in Produktkatalogen ist die Suche im Index fast genauso schnell wie die Erstellung von Vorschlägen.

Während Sie tippen könnte in einer Buchhandlung eine reduzierte Trefferliste dargestellt werden. Sie besteht lediglich aus dem Buchtitel, einer kurzen Beschreibung und möglicherweise einem kleinen Bild des Einbands. Sobald Sie das Buch gefunden haben, nach dem Sie gesucht hatten, können Sie direkt die Detailseite auswählen ohne vorher die vollständige Trefferliste anzeigen zu müssen. Selbstverständlich haben Sie dennoch die Möglichkeit die Trefferliste anzuzeigen – um Bücher, die dem gesuchten ähneln (und natürlich Ihren Suchbegriffen entsprechen), anzusehen.

Die nächste Generation: Automatische ???

Nun, was können wir in der Zukunft erwarten? Manche Techniken der nächsten Generation können bereits heute ausprobiert werden:

  • Microsoft SharePoint lernt von Eingaben der Nutzer und deren Rückmeldung. Wenn Dokumente in der Trefferliste für einen bestimmten Suchbegriff mehrfach angeklickt wurden, wird dieser Suchbegriff in die Liste der möglichen Vorschläge übernommen.
  • Google.com zeichnet sogar jeden einzelnen Tastendruck auf. Damit sollen Tippfehler antizipiert und die beste Korrektur automatisch vorgeschlagen werden. Dies geht sogar so weit, dass alle weltweit verwendeten Tastenbelegungen berücksichtigt werden, um abzuschätzen, welche Taste eigentlich gedrückt werden sollte.
  • Personalisierung: Google und SharePoint bieten jedem Nutzer individuelle Vorschläge an (vorausgesetzt, dass sie am System angemeldet sind). Während einem Techniker vorrangig technische Begriffe vorgeschlagen werden, wird das System Nutzern, die viel online einkaufen, eher Produktnamen vorschlagen.
  • Maschinelles Lernen: Verschiedene Logdateien werden von Suchmaschinen indiziert, korreliert und analysiert. Dabei werden Klickpfade, versteckte Beziehungen (wie Zahlenmuster von Seriennummern zu Produktnamen), etc. entdeckt. Alternative Suchvorschläge werden daher mit Hilfe kollektiver Intelligenz erstellt.

Seitdem viel Rechenleistung zu niedrigen Preisen verfügbar ist, haben neurale Netze und maschinelles Lernen neue Aufmerksamkeit erregt. Anstelle passender Worte können jetzt auch ähnliche Konzepte vorgeschlagen werden. Nach einer Eingabe von Mai könnten die Vorschläge die Begriffe Monat, Frühling oder sogar Sängerin3 enthalten.

Viele neue Ansätze werden derzeit diskutiert und entwickelt – einer der vielversprechenden ist Word2Vec (entwickelt von Google im Jahre 20134, basierend auf Forschungsergebnissen, die bereits 19865 vorlagen). Hier wird ein maschinelles Lernmodell dazu trainiert, Worte hervorzusagen, welche ein Wort oder ein Objekt6 umgeben: Jedes Wort/Objekt wird aufgrund dieser Nachbarschaft durch einen multidimensionalen Vektor repräsentiert. Und es kommt noch besser: Die Berechnung dieser Vektoren ist mit relativ vernünftigem Zeitaufwand möglich.

Hierzu noch eine kleine Anmerkung: Mit Hilfe dieser Vektordarstellung ist es möglich, mathematische Berechnungen mit Konzepten durchzuführen. Man könnte z.B. von König den Mann abziehen, Frau dazu addieren – und die Königin wäre das Ergebnis! Interessanterweise ist die Vektordistanz zweier Objektklassen, z.B. Land und Hauptstadt, meist immer die gleiche. Das heißt, wenn man weiß, das Paris die Hauptstadt von Frankreich ist, kann man diese Distanz für Kanada verwenden und erhält als Ergebnis Ottawa (was tatsächlich Kanadas Hauptstadt ist).

Zusammenfassung

Suchbegriffe werden noch sehr lange vorgeschlagen werden, auch wenn diese Funktion schon seit fast 20 Jahren angeboten wird. Erwarten Sie keine Revolution in der Benutzeroberfläche – aber sie werden von den Vorschlägen, die Sie in Zukunft erhalten werden, überrascht und fasziniert sein!

- Konrad


1Der frühere Präsident der Europäischen Union
2Roland Garros: Französischer Flugpionier
3Vanessa Mai, Sängerin
4Chen, Corrado, Dean and Mikolov: Efficient Estimation of Word Representations in Vector Space
5Hinton, McClelland, Rumelhart: Distributed representations
6Benötigt Natural Language Processing um Objekte wie Formel Eins oder Tower Bridge zu erkennen.

0

Wir freuen uns, bekannt zu geben, dass wir jetzt Teil von Accenture sind! Lesen Sie die Ankündigung hier.