Dieser Artikel beschreibt in für Computerlaien hoffentlich verständlicher Sprache, wie Google & Co. in weniger als einer Sekunde Milliarden Web-Dokumente durchsuchen können.
Eine Volltextsuchmaschine führt drei grundlegende Vorgänge durch:
Der erste Schritt verschafft der Suchmaschine die nötigen Rohdaten, die Analyse bereitet diese auf und die so gewonnenen Erkenntnisse werden für die Beantwortung von Anfragen im dritten Teil verwendet.
Die der Suchmaschine zugrundeliegende Datenbank hält eine Reihe von Adressen von Dateien vor (URLs, Uniform Resource Locators), deren Dokumente gelesen werden sollen. Die Adressen stammen aus folgenden Quellen:
Eine Reihe von Rechnern lädt nun mit diesen Adressen rund um die Uhr Dateien herunter und speichert sie in einer Datenbank. Die Adressliste wird dann jeweils auf den neuesten Stand gebracht. Entweder wird vermerkt, daß die Datei erfolgreich übertragen wurde, oder ein Problem wird notiert, wenn etwa der Server nicht erreichbar ist. Bei einem Redirect, also einer permanenten Umleitung, wird die Adressliste auf den neuesten Stand gebracht. Nach einer gewissen Anzahl von Fehlversuchen entfernt die Suchmaschine eine Adresse aus ihrer Liste.
Die im ersten Abschnitt geholten Dateien werden nun ausgewertet. Ein dem Format der Datei (also meist HTML, reiner Text oder PDF) entsprechender Parser zerlegt sie in ihre Einzelteile, also Metadaten wie Autor, Titel u. s. w. sowie den eigentlichen Text der Seite als Sequenz von Wörtern.
Dabei wird oft auch beachtet, ob ein Wort besonders groß geschrieben oder fett ist, ob es Teil einer Überschrift oder eines Querverweises auf ein anderes Dokument ist.
Alle Wörter werden nun in einem „invertierten Index“ abgelegt. Dieser Index speichert für alle Wörter, die in mindestens einem Dokument vorgekommen sind, Paare von Dokumenten-Nummer und Position des Worts in diesem Dokument.
Angenommen, die Datei http://www.example.org/musterdokument.html wird vom Crawler erstmalig geholt und bekommt die Identifikationsnummer 97. Diese Datei enthalte nun nur den Satz How do you do?. Daraus erzeugt der Parser die Paare (how, 1), (do, 2), (you, 3), (do, 4). Jedes Wort wird also mit seiner Position im Dokument kombiniert. Ein mehrfaches Vorkommen einzelner Begriffe ist dabei möglich (hier bei do). Der Index wird jetzt für die drei Wörter „how", „do" und „you" auf den neuesten Stand gebracht, indem Wertepaare (Dokumenten-ID, Wortposition) hinzugefügt werden:
do ... existierende Paare für do (97, 2) (97, 4) how ... existierende Paare für how (97, 1) you ... existierende Paare für you (97, 3)
Tatsächlich werden noch weitere Informationen gespeichert, wie eben die bereits angesprochenen Metadaten oder die Formatierung der Wörter. Diejenigen Begriffe, mit denen auf ein anderes Dokument verwiesen wird tauchen eventuell ebenfalls im Index für dieses Dokument auf. Allerdings sind diese Details nicht nur von Suchmaschine zu Suchmaschine unterschiedlich, sie sind darüber hinaus undokumentiert. Die Betreiber der Suchmaschinen wollen sich nicht in die Karten sehen lassen.
In der Praxis werden nicht nur für einzelne Wörter sondern auch für Phrasen Indexpaare angelegt. Also etwa so:
do you (97, 2) how do (97, 1) you do (97, 3)
Das kostet mehr Speicherplatz und Arbeit, um diese zusätzlichen Listen auf dem neuesten Stand zu halten, bringt aber naturgemäß eine vereinfachte Abfrage, immerhin muß man nur in einer Liste nachschauen, statt zwei aufwendig mit Vergleichen zu durchlaufen.
Je nach Suchmaschine werden gewisse Begriffe gar nicht erst in den Index aufgenommen, sogenannte Stopwörter. Das sind sehr häufig vorkommende Wörter wie „the" im Englischen oder „ein" im Deutschen. Da sie in fast jedem Dokument der jeweiligen Sprache auftreten, wird ihnen keine Bedeutung zugemessen. Der Index wird durch das Weglassen außerdem deutlich kleiner. Trotzdem verzichten immer weniger Suchmaschinen auf Stopwörter. Für gewisse Anfragen sind sie eben doch von Interesse. Paradebeispiel ist der Shakespeare-Satz „To be or not to be". Er besteht ausschließlich aus Stopwörtern, kann also nur gefunden werden, wenn sie in den Index aufgenommen worden sind.
Ein weiterer Vorbearbeitungsschritt ist das sogenannte Stemming. Dabei werden Begriffe auf ihren Wortstamm zurückgeführt. So werden „schöne", „schöner", „schönen" u. s. w. alle auf „schön" vereinfacht. Einerseits kann man so auch ähnliche Begriffe finden, andrerseits verliert man eine gewisse Genauigkeit. Sehr hilfreich ist die Ungenauigkeit im Zusammenhang mit falsch geschriebenen Wörtern. Ob aus mangelndem Wissen oder Flüchtigkeit, sehr viele Anfragen sind fehlerhaft. Hier hilft dem Suchenden eine gewisse Toleranz enorm. (Bei Google hat man mal eine Weile die Suchanfragen zur Sängerin Britney Spears gezählt. Interessanter als die absoluten Zahlen sind dabei die vielfältigen Variationen der Schreibweise.)
Ein verwandtes Konzept bildet auch Synonyme aufeinander ab. Wer dann z. B. nach „stark" sucht, findet eventuell auch „kräftig".
Schließlich wird auch die Sprache des Dokuments ermittelt, um Suchanfragen entsprechend einschränken zu können.
Was passiert nun, wenn man auf einer Suchmaschinen-Website ein paar Begriffe eingibt und diese Suchanfrage über den entsprechenden Button abschickt? Einer der verschiedenen Rechner im entsprechenden Datenzentrum bekommt die Begriffe und macht sich nun daran, im Index die am besten passenden Dokumente zu finden. Als Beispielanfrage sei die Anfrage Johann Sebastian Bach gegeben.
Wie bereits im vorherigen Abschnitt beschrieben besteht der Index u. a. aus Listen von Paaren (Dokumentennummer, Wortposition). Für jedes Wort, das mindestens einmal in den untersuchten Dokumenten vorgekommen ist, existiert eine solche Liste. Je häufiger ein bestimmtes Wort vorkommt, desto länger ist auch die entsprechende Liste.
Es wird nun bei der Abarbeitung der Anfrage nach Dokumentennummern gesucht, die in den Listen jedes einzelnen Suchbegriffs, der in der Anfrage vorkommt, auftreten. Die Menge aller Dokumente wird also im Beispielfall eingeschränkt auf diejenigen, deren Identifikationsnummer sowohl in der Liste für „Johann" als auch in der Liste für „Sebastian" als auch in der für „Bach" vorkommt.
Je nach Seltenheit der Begriffe hat man somit bereits fast alle (oder sogar alle) Dokumente ausgeschlossen. Genauso gut können die Begriffe aber auch so allgemein gebräuchlich sein, daß noch nicht viel weggefallen ist.
Wurde bei der Anfrage die exakte Phrase "Johann Sebastian Bach" verlangt, also die drei Wörter in dieser Reihenfolge, entfernt man weitere potentielle Ergebniskandidaten. Nämlich solche, in denen zwar alle Begriffe vorkommen, aber nicht in dieser Reihenfolge (etwa ein Dokument, das aus dem Satz „Johann und Sebastian gingen am Bach entlang." besteht). Um Phrasen finden zu können, ist man auf die Wortpositionen in den Indexlisten angewiesen. Existiert in der Liste für „Johann" ein Paar (Dokument 1446, Position 12), so muß es in der Liste für „Sebastian" ein Paar (Dokument 1446, Position 13) und in der für „Bach" ein Paar (Dokument 1446, Position 14) geben, damit die Positionen 12 bis 14 in Dokument 1446 einen Treffer darstellen.
Sind alle passenden Dokumente ermittelt, werden sie gemäß ihrer Relevanz sortiert, damit der Benutzer die besten Treffer zuerst sieht. Kommen die Begriffe besonders häufig in einem Dokument vor, sind sie im Titel oder in Überschriften des Dokuments vorhanden, wird mit ihnen in anderen Dokumenten auf dieses Dokument verwiesen, sind sie besonders fett oder groß geschrieben oder treten sie auch in der Adresse der Seite auf (im Domainnamen, im Verzeichnis oder Dateinamen), so kommt das ihrem Rang innerhalb der Ergebnisliste zugute.
Ein weiterer Faktor ist die allgemeine Wertigkeit, die einer bestimmten Seite von der Suchmaschine zugemessen wird. Bei Google ist dies der sogenannte PageRank, eine Zahl zwischen 0 und 10, die die allgemeine Popularität der Seite angeben soll. Allerdings darf ein solcher Wert nicht allein ausschlaggebend werden, sonst würden bei jeder Anfrage immer dieselben Topseiten angezeigt, solange sie nur die Begriffe enthalten.
Sind nun die passendsten Seiten ermittelt, wird die Ergebnisseite für den Benutzer erzeugt und an seinen Browser geschickt.
Die Ergebnisseite enthält meist für zehn bis zwanzig Dokumente den Titel sowie Adresse und Textauszüge des Dokuments, in denen die Suchbegriffe bereits fett oder andersfarbig markiert sind.
Falls vorhanden, können passende Kategorien aus Katalogen hinzugenommen werden, im Beispielfall könnte dies etwa Musik > Komponisten > Deutschland > B > Bach, Johann Sebastian sein.
Viele Suchmaschinen blenden anfragenspezifische Werbung ein. Statt irgendeines Banners wird so im Beispiel für das Angebot eines Online-Musikshops geworben, der Klassik-CDs verkauft.
Oft wird anhand der IP-Adresse des Suchenden die ungefähre Region (zumindest das Land) ermittelt, aus der er kommt, und die Auswahl der Werbung davon abhängig gemacht. Somit bekommt dann ein Deutscher eine Anzeige für ein Bachfestival in Leipzig zu sehen, nicht aber ein Australier. Auch die im Browser eingestellte Sprache ist ein Kriterium, unterschiedliche Werbung einzublenden.
Manche Suchmaschinen geben auf der Ergebnisseite nicht die eigentlichen Adressen der Seiten an, die sie als Suchergebnisse präsentieren, sondern sich selbst samt einem speziellen Code, der für die Seite steht. Ruft der Benutzer einen solchen Link auf, leitet die Suchmaschine ihn sofort an die eigentliche Seite weiter. Somit hat sie aber registriert, was er ausgewählt hat und kann diese Information möglicherweise zukünftig in die Auswahl der Ergebnisse einbeziehen.
Dieser Text ist auch Teil der FAQ der Newsgroup de.comm.infosystems.suchmaschinen auf http://www.ososo.de/suchmaschinen-faq/.