Wie funktionieren Suchmaschinen?

marketingmixtur_seo_wie_funktionieren_suchmaschinen

Das Herzstück – der Index

Die Suchmaschine pflegt einen Datenbestand an Informationen über einen großen Teil der öffentlich zugänglichen Seiten des World Wide Web. Neben vielen anderen Informationen, die in diesem Datenbestand enthalten sind, ist eine davon von herausragender Bedeutung: Welches Wort befindet sich auf welcher Webseite?

Man kann sich das Ganze konkret so vorstellen, dass die Suchmaschine intern einen Datensatz verwaltet, in dem gespeichert ist, welches Wort auf welcher Website vorkommt.
Gibt man nun ein Wort bei einer Suchmaschine wie Google ein, so schaut sie in diesem Datensatz nach und gibt alle Seiten zurück, auf denen das gesuchte Wort vorkommt.
Mit der Reihenfolge, in der uns die Ergebnisse als Nutzer präsentiert werden, wollen wir uns später beschäftigen. An dieser Stelle wollen wir zunächst der Frage nachgehen, wie der beschriebene Datensatz aufgebaut ist.

Die zugrunde liegende Datenstruktur

Wir haben gesehen, dass es notwendig ist, einen Datensatz zu halten,  der die Information enthält, welches Wort auf welcher Webseite vorkommt. Um uns der Frage zu nähern, welche Datenstruktur sich für die Organisation dieser Informationen eignet, wollen wir mit einem intuitiven Ansatz beginnen und dann zeigen, warum sich andere Datenstrukturen durchgesetzt haben.

Ansatz 1: Die Ja/Nein-Tabelle

Ein intuitiver Ansatz wäre es, eine große (zweidimensionale) Tabelle zu verwenden: In der Senkrechten tragen wir alle Wörter des zugrundeliegenden Wortschatzes ein. In der Horizontalen stehen alle Webseiten. In jeder Zelle der Tabelle wird nun mit eine Ja oder Neine (bzw. 0 oder 1) markiert, ob das Wort auf der Webseite vorkommt oder nicht.

Stellen wir uns vor, das Internet bestünde aus lediglich 1Mio Webseiten mit im Schnitt 1000 Wörtern.
Jedes Wort besteht durchschnittlich aus 6 Buchstaben (entspricht 6 Bytes).
Folglich Hätten wir eine Datenmenge von überschaubaren 5,7GB zu handhaben.

Auf der anderen Seite haben wir einen Wortschatz, der aus 500.000 unterschiedlichen Wörtern besteht.

Wir wissen jetzt die Ausdehnung in der Horizontalen und der Vertikalen. Multipliziert mit einander erhalten wir die Anzahl der Zellen in der Tabelle:

500.000 [Wörter] x 1.000.000 [Webseiten] = 500.000.000.000 [Zellen]

Da wir für die Ja/Nein-Information nur ein Bit Speicher benötigen, brauchen wir insgesamt eine halbe Trillion Bits oder 58,2GB.
Unsere Tabelle ist demnach zehnmal so groß, wie der ursprüngliche Datensatz.
Denkt man sich nun, dass das Internet aus unglaublich viel mehr Dokumenten besteht und auch der Wortschatz (verschiedene Sprachen!) um ein Vielfaches größer ist, so merkt man schnell, dass diese riesige Datenmenge nicht sehr praktikabel ist.


Hinzu kommt ein weiteres Problem, das sich ergibt, wenn man nach Dokumenten sucht, die ein bestimmtes Wort enthalten. Bei der Suche, wird zunächst in der Vertikalen die Zeile mit dem Wort ausfindig gemacht. Anschließend wird die komplette Zeile durchgegangen. Hierbei werden alle Webseiten herausgeschrieben, für die eine Eins hinterlegt ist.
Selbst wenn man unmittelbar zum Wort springen kann (dies wird auch als Random Access bezeichnet), so müssen wir doch stets alle Zellen einer Zeile durchiterieren.

Auch wird bei näherer Betrachtung deutlich, dass die auf diese Weise konstruierte Tabelle zum Großteil aus Nullen (Null entspricht einem „Nein“) besteht. Um genau zu sein, wird nur jede 500ste Zelle eine Eins enthalten.
Das führt uns direkt zu einem wesentlich praktikableren Ansatz:

Ansatz 2: Nur speichern, wenn ein Wort vorkommt

Wir speichern für jedes Wort eine Liste mit Webseiten, auf denen dieses vorkommt. Um genau zu sein geben wir jeder Webseite eine eindeutige ID und speichern diese in einer Liste, die dem jeweiligen Suchwort zugeordnet wird.
Dieser Ansatz hat den offensichtlichen Vorteil, dass wir immer mit einem „Griff“ alle Webseiten zurückgegeben bekommen, die ein bestimmtes Wort enthalten.

Wunderbar – könnte man an dieser Stelle sagen aber so einfach ist es leider nicht! Denn in heutigen Suchmaschinen kann der Nutzer ganze Suchphrasen, bestehend aus mehreren Wörtern eingeben. Wenn wir uns nun alle Webseiten ausgeben lassen wollen, auf denen wirklich alle Suchwörter vorkommen, so sind wir wieder gezwungen über alle Zellen der jeweiligen Wort-Zeile zu iterieren. Das Verfahren wäre damit Zeitaufwändiger als der erste Ansatz, bei dem man bei der Suche nach mehreren Worten eine „Schablone“ mit Nullen und Einsen (für die Suchworte) über die Tabelle schieben könnte.

Die gute Nachricht ist, wenn wir die Listen nach den Website-IDs sortieren, können wir mit geringem Aufwand Webseiten finden, auf denen mehrere Suchworte vorkommen:

Wir müssen jetzt nur von links nach rechts so lange die Listen parallel durchgehen, bis die angegebenen IDs nicht mehr übereinstimmen. So bekommen wir als Rückgabe alle Webseiten, auf denen die zwei (oder mehr) Suchworte vorkommen.

Die Informatiker bezeichnen dieses Verfahren auch als „Inverted Index“. Es stellt die Basis für Suchalgorithmen in großen Datenmengen dar.

Doch auch der „Inverted Index“ hat Nachteile. Zunächst einmal ist es unproblematisch, neue Webseiten und Dokumente in den Index aufzunehmen: Die neue Webseite erhält eine ID, die automatisch hochgezählt wird. Die ID wird nun an alle Wörter-Listen angehängt, wenn das entsprechende Wort auf der Webseite vorkommt.
Was aber, wenn sich der Inhalt einer Website ändert? Angenommen, es wird das Wort „TODO“ auf der Webseite mit ID = 8 hinzugefügt. Dann muss die Liste neu sortiert werden, was an sich schon Rechenaufwand verursacht. Noch problematischer ist allerdings, dass der Sortiervorgang – selbst wenn er ausgelagert wird – den Lesezugriff auf die Liste blockiert.

Anmerkung: Das ist wohl auch ein Grund für die Praxiserfahrung vieler SEOs, dass Änderungen an bestehenden Inhalten von Google nicht unbedingt positiv aufgenommen werden.

Zusammenfassung

Halten wir fest: Wir wissen nun, wie die Suchmaschine intern die Information speichert, welches Wort auf welcher Webseite vorkommt. Im nächsten Abschnitt wollen wir uns der Frage widmen, wie eine Suchmaschine diesen Datenbestand in der Praxis erzeugt und pflegt. Weiter lesen…

Artikel-Übersicht:

Pages: 1 2 3 4 5

You can leave a response, or trackback from your own site.

Leave a Reply