Hin und wieder möchte ich Kollegen und Gesprächspartnern erklären, wie eine Suchmaschine ganz prinzipiell funktioniert und was der Vorteil (oder besser die Unterschiede) zwischen einer indexbasierten Suchmaschine und einer Datenbanksuche sind.

Ich beginne dann häufig damit, die fundamentalen Unterschiede zwischen beiden Systemen zu erläutern. Leider merke ich oft nicht sofort, dass mein Gegenüber längst abgeschaltet hat, während ich mich in Details über Queries, Indexfeldern, Navigatoren, linguistische Analysen und vieles verwirrendes mehr verliere. Dazu kommt, dass ich in der Regel versuche die Anfrageseite mit einzubeziehen. Aber mal ganz ehrlich: Gesucht haben wir alle schon im Internet und wir konnten uns auch in aller Regel erklären, wieso wir bestimmte Ergebnisse erhalten haben und wenn wir auch einfach nur gedacht haben: “In diesem Text stehen genau die Wörter drin, die ich eingegeben habe”. Das soll mir als Vorbildung für meine Leser eigentlich reichen, denn die gängigen Suchmaschinen müssen letztlich den Informationsbedarf des Nutzers stillen, ohne von ihm zwingend ein fundiertes Hintergrundwissen über ihre Funktionsweise abzuverlangen.

Deshalb werde ich mich in diesem Posting darauf beschränken, die einfachste Form eines sogenannten invertierten Indexes zu erklären, da dieses Konstrukt der eigentliche Trick ist, der eine indexbasierte Suchmaschine so schnell und leistungsfähig macht. Ihr werdet dann selbst sehr schnell darauf kommen, warum für den Anwendungsfall “Suche” die Bereitstellung eines Indexes die beste Möglichkeit darstellt, um die Grundbedürfnisse des Benutzers zu befriedigen. Diese Bedürfnisse sind:

• Die Ergebnisse müssen für mich relevant und von guter Qualität sein (kein SPAM!)
• Die Ergebnisse müssen sofort erscheinen
• Die Ergebnisse müssen vollständig sein

Wie funktioniert also nun ein invertierter Index? Im Grunde ähnlich wie das Schlagwortverzeichnis in einem Buch, das für genau den selben Zweck gedacht ist: Ich suche die Stelle im Buch, in der ein bestimmtes Wort behandelt wird, in dem ich es in einem vorbereiteten, alphabetisch sortierten Index nachschlage.

Der Unterschied zu einer Suchmaschine ist, dass in einem Schlagwortverzeichnis nur auf die einzelnen Seiten des selben Buches verwiesen wird. In Suchmaschinen wird dagegen auf einzelne Dokumente verlinkt. Anders ausgedrückt: Ein großes, zentrales Verzeichnis aller Bücher verweist auf einzelne Bücher (Dokumente) innerhalb des Bestandes. Diese Strategie macht das Auffinden (Retrieval) von Dokumenten so schnell und stellt gleichzeitig sicher, dass Suchanfragen gegen den Index immer in etwa der gleichen Geschwindigkeit abgearbeitet werden können. Bei einer Volltextsuche in einer relationalen Datenbank ist diese Eigenschaft nicht gegeben, da sie für diesen Anwendungsfall aufgrund ihrer Struktur schlicht nicht spezialisiert genug ist.

Wie sieht der Index nun konkret aus? Um bei der Analogie des altbekannten Schlagwortverzeichnisses zu bleiben, werden dort nur die Wörter aufgeführt, die eine gewisse Bedeutung für den Fließtext des Buches haben. Eine Suchmaschine merkt sich im einfachsten Fall alle sinntragenden und bedeutungsstarken Wörter einer Dokumentensammlung und schreibt sie in den Index. Alle nicht sinntragenden Wörter (sogenannte Stoppwörter in der Fachsprache des Information Retrieval) werden dabei aussortiert, da niemand nach ihnen suchen würde und sie in nahezu jedem Dokument häufig und mit sehr hoher Wiederholungsrate vorkommen.

Beispiele für Stoppwörter sind:

Der, die, das, von, in, oder, und, an, ein, eine, einer, aber auch die Interpunktion zwischen Wörtern und Sätzen wie etwa Punkt, Komma, Bindestrich, etc.

Terry Pratchett’s famose Erkenntnis “Man findet immer dort besonders viel Chaos, wo man nach Ordnung sucht. Das Chaos besiegt die Ordnung, weil es besser organisiert ist.” wird also (bevor sie in den Index geschrieben wird) anhand einer vorher festgelegten Stoppwortliste so verändert:

“Man findet immer dort besonders viel Chaos, wo man nach Ordnung sucht. Das Chaos besiegt die Ordnung, weil es besser organisiert ist.”

Wenn die Suchmaschine nun damit beginnt einen invertierten Index zu erstellen, wird sehr schnell eine regelrechte Erbsenzählermentalität dieser Systeme sichtbar: Die Software pflügt durch die Textsammlung (=Textkorpus) und merkt sich für jedes Wort in welchen Dokumenten es vorkommt und mit welcher Frequenz. Die Stoppworte werden dabei wie beschrieben ignoriert. Dafür nutzt die Suchmaschine die vorher festgelegte Stoppwortliste und ggfs. zusätzliche statistische und heuristische Verfahren, um z. B. keyword stuffing zu erkennen und entsprechend zu behandeln. Komplette Texte werden selten im Index einer Suchmaschine abgelegt. Eine Suchmaschine ist nur auf das Finden von Texten hin optimiert. Das eigentliche Dokument gehört eigentlich in eine Datei oder eine dafür optimierte Datenbank. Prinzipiell ist das Abspeichern eines Volltextes im Index aber natürlich möglich und unter Umständen auch sinnvoll. Gängig ist zum Beispiel das Abspeichern eines kleinen Teasers, der direkt neben dem Verweis auf das eigentliche Dokument platziert werden kann und eine Vorschau auf den Volltext des Dokuments bietet. Google tut genau das, wenn es bei den Suchergebnissen einen kleinen Textausschnitt der verlinkten Webseite anzeigt. Sehr spezialisierte Systeme stützen sich außerdem auf fortschrittliche Verfahren aus dem Natural Language Processing (NLP), um weitere Optimierungen vorzunehmen und Metadaten zu den einzelnen Einträgen zu speichern, die das spätere Retrieval (also das Auffinden der Texte) noch weiter verbessern können.

Das Ergebnis für eines von Terry Pratchett’s Büchern sieht dann z. B. so aus:

Rincewind = [(doc=1, freq=7), (doc=2, freq=0), (doc=3, freq=0)]

Zauberer = [(doc=1, freq=12), (doc=2, freq=5), (doc=3, freq=1)]

Vetinari = [(doc=1, freq=1), (doc=2, freq=2), (doc=3, freq=1)]

Diese Struktur ist im Grunde der Kern jedes invertierten Indexes. Hier merkt sich die Suchmaschine die sinntragenden Wörter und in welchen Dokumenten sie zu finden sind, und wie oft.

Im Beispiel kommt etwa der Name eines stadtbekannten Pechvogels “Rincewind” nur in Dokument 1 mit hoher Frequenz vor. Außerdem tritt die Berufsbezeichnung “Zauberer” häufig auf. Mit etwas Wissen über Terry Pratchett’s Bücher kann ich schon sagen: Es handelt sich um ein Buch in dem von einem Zauberer namens Rincewind relativ häufig die Rede ist. In Dokument 2 dagegen, taucht Rincewind offensichtlich gar nicht auf. Anhand der Frequenz von “Zauberer” können wir aber erkennen, dass es trotzdem auch in diesem Dokument um den genannten Berufsstand geht. Außerdem wird ein gewisser Lord “Vetinari” immerhin doppelt so häufig wie im ersten Dokument erwähnt. Das sagt uns, dass dieses Dokument für den Suchbegriff “Zauberer” sehr relevant sein muss. Auf jeden Fall deutlich relevanter als in Dokument 3, wo die “Zauberer” nur einmal erwähnt werden. Rincewind dagegen spielt auch hier keine tragende Rolle. Der aufmerksame Leser kann  jetzt natürlich bemerken:

“Hey, vielleicht besteht das Dokument 3 nur aus einem Zitat und das Dokument 1 ist dagegen eine ganze Geschichte! Für mich ist aber vielleicht gerade dieser eine Satz (das Zitat, das ich gerade suche) sehr relevant!”

Dieser Einwand ist natürlich absolut richtig. Deshalb wurden in der Vergangenheit diverse Normierungsverfahren entwickelt, um das Problem der unterschiedlichen Dokumentlänge zu lösen. Außerdem schließen sich an unser recht einfaches Modell eines invertierten Indexes noch eine Vielzahl weitere Fragestellungen an. Dazu gehört zum Beispiel das Ranking-Problem, das die Frage stellt, in welcher Reihenfolge die gefundenen Dokumente überhaupt in der Ergebnisliste (Search Engine Result Page; SERP) ausgegeben werden sollen. Auch für die Klärung der Frage wie gut eine Ergebnisliste ist, gibt es diverse Verfahren und die entsprechenenden Fachbegriffe hierzu lauten Recall und Precision. Der Recall misst die Vollständigkeit der angezeigten Treffermenge. Einfach gesagt: Wieviele Dokumentverweise wurden durch meine Suchanfrage gegen den invertierten Index gefunden? Wenn die Suchanfrage restlos alle Dokumente zurückliefert, ist der Recall 100% . Die Precision im Suchergebnis ist dann aber extrem schlecht, denn die Precision misst wie exakt die gefundenen Dokumente zur Suchanfrage passen und letztlich kommt es genau darauf an. Im Grunde werden immer die Wörter in der Suchanfrage des Benutzers mit den Wörtern im invertierten Index verglichen.

Ganz einfach gesagt: Je mehr Wörter meiner Suchanfrage gehäuft in einem Dokument vorkommen, desto relevanter ist es für mich und sollte deshalb in der SERP weit oben stehen.

Wer tiefer in diese Thematik einsteigen will, und daran interessiert ist wie von unserem invertierten Index ausgehend erweitertes Information Retrieval funktioniert, dem sei die Wikipedia und natürlich die darin zitierte Fachliteratur empfohlen. Die Index-Struktur lässt sich dabei beliebig aufbohren. Es kann zum Beispiel sinnvoll sein, sich zu merken, an welcher Stelle das Wort zu finden ist und in welchem Kontext es steht. Dadurch kann die Suchmaschine dann erkennen, welche Wörter häufig miteinander in Verbindung stehen und in welchem Teil eines Textes sie vorkommen. Oft wird auch eine Reduktion auf die Stammform des Wortes vorgenommen (Lemmatisierung). Im Englischen funktioniert das zufriedenstellend. Für diesen Zweck gibt es sogenannte Stemming-Algorithmen, wie etwa den Porter-Stemmer. Die deutsche Sprache dagegen ist geradezu mit Flexionsformen “verseucht” und Wörter lassen sich nur sehr eingeschränkt mit Algorithmen auf ihre Stammformen reduzieren. Hier sind Wörterbuch-basierte Ansätze sinnvoller (manuelle Pflege und stetige Weiterentwicklung vorausgesetzt).

Ich möchte an dieser Stelle nicht auf die Verfahren der Stammformreduktion selbst eingehen. Wichtig ist zu verstehen, dass in einem invertierten Index, der nur die Stammformen von Wörtern speichert, etwa das Wort “treffen” mit der Frequenz “3″ für ein Dokument hinterlegt wird, das eigentlich so aussieht:

“Er traf seinen Erzfeind [...]“, “[...] hatte es sich gut getroffen, dass [...]” und “Man könnte sich ja mal wieder irgendwo auf eine Tasse Kaffee treffen“.

Hier haben wir drei Flexionsformen des Wortes “treffen”, aber im Index wird nur die Grundform gespeichert. Bei einer Suchanfrage wird ebenfalls diese Reduktion auf die Stammform durchgeführt und danach erst im invertierten Index nach dem Wort “treffen” gesucht:

Eingabe des Nutzers: “bruder” AND “getroffen”

Tatsächliche Suchanfrage nach der Lemmatisierung: “bruder” AND “treffen”

Wie man sehen kann ist die Lemmatisierung eine Möglichkeit mit der man den Index sowohl klein halten kann, als auch die Abhängigkeit von der Vielzahl von Flexionsformen in unserer Sprache auflöst.

Ich hoffe dieser kleine Artikel hilft dabei sich vorzustellen wie eine Suchmaschine funktioniert und wieso sie so verflixt schnell ihre Ergebnisse liefert. Über Kommentare und Anregungen würde ich mich sehr freuen.