WebCrawler (1994): Wie die erste Volltext-Suchmaschine das Web erfasste und indexierte

Einordnung: WebCrawler und das Originalpaper von 1994

WebCrawler ging am 20. April 1994 online und gilt als erste Suchmaschine, mit der Nutzer nach beliebigen Wörtern im Text indexierter Webseiten suchen konnten.^[2] Entwickelt hatte das System Brian Pinkerton, damals Doktorand am Department of Computer Science and Engineering der University of Washington in Seattle.^[1]

Die wichtigste Primärquelle ist Pinkertons Aufsatz „Finding What People Want: Experiences with the WebCrawler“. Er wurde auf der Second International World-Wide Web Conference 1994 vorgestellt und beschreibt Aufbau, Arbeitsweise und Betriebserfahrungen der ersten sechs Monate.^[1] Die ursprüngliche Online-Fassung ist heute nur noch über das Internet Archive erreichbar. Diese Seite fasst die überprüfbaren Inhalte des Papers auf Deutsch zusammen und verweist für jede Angabe auf die Quelle.

Alle Zahlen in diesem Artikel stammen, sofern nicht anders gekennzeichnet, aus dem Paper selbst und beschreiben den Stand von 1994. Sie sind historische Angaben des Entwicklers und keine unabhängigen Messungen.

Das Problem: Ressourcen finden in einem dezentralen Web

Pinkerton beschreibt als Ausgangslage das sogenannte Resource-Discovery-Problem: Im World Wide Web gelangt man von einem Dokument zum nächsten, indem man Hyperlinks folgt. Je größer das Web wird, desto mehr Links muss man verfolgen, bis man ein bestimmtes Dokument findet, und desto unpraktischer wird reines Navigieren.^[1]

Andere Ansätze jener Zeit wie ALIWEB oder Harvest setzten darauf, dass Server-Betreiber Beschreibungen ihrer Inhalte selbst bereitstellen. WebCrawler ging bewusst einen anderen Weg: Er nutzte nur die Infrastruktur, die das Web ohnehin bot, also die Möglichkeit eines Clients, Dokumente von Servern abzurufen. Pinkerton bezeichnet das System deshalb als Web-Roboter.^[1]

Aufbau: vier Komponenten

Das Paper gliedert WebCrawler in vier Softwarekomponenten. Nach dem Abruf eines Dokuments führte das System jeweils drei Schritte aus: Es markierte das Dokument als abgerufen, las die ausgehenden Links (href-Attribute) aus und indexierte den Inhalt. Alle drei Schritte schrieben Daten in eine Datenbank.^[1]

• Suchsteuerung (im Paper „Search Engine“): entscheidet, welche Dokumente als Nächstes abgerufen werden, und lässt nicht indexierbare Dateien wie Bilder, Töne, PostScript oder Binärdaten aus.
• Agenten: rufen Dokumente über die CERN-Bibliothek libWWW ab und unterstützen damit HTTP, FTP und Gopher. Bis zu 15 Agenten liefen parallel in eigenen Prozessen, weil das Warten auf Server und Netz der Engpass war.
• Datenbank: besteht aus einem invertierten Volltextindex und einer Abbildung des Webs als Graph aus Servern, Dokumenten und Links, gespeichert in getrennten B-Bäumen. Änderungen wurden in Transaktionen alle paar hundert Dokumente festgeschrieben.
• Query Server: stellt den WebCrawler-Index als Suchdienst über eine Webseite bereit.

Wie WebCrawler Seiten fand: das Web als Graph

WebCrawler behandelte das Web als großen gerichteten Graphen. Ausgehend von bekannten Dokumenten untersuchte er deren ausgehende Links, folgte einem Link zu einem neuen Dokument und wiederholte den Vorgang. Für die Software bedeutete das Entdecken eines Dokuments, seine Identität zu erfahren, also seine URL.^[1]

Im Indexierungsmodus verwendete WebCrawler eine abgewandelte Breitensuche auf Server-Ebene. Ziel war, dass jeder bekannte Server mit mindestens einem Dokument im Index vertreten ist: Sobald ein neuer Server auftauchte, wurde zuerst ein Dokument von ihm abgerufen und indexiert, bevor die Durchsuchung weiterlief. Auf einem 486-PC mit NEXTSTEP erreichte das System nach Pinkertons Angaben etwa 1.000 Dokumente pro Stunde.^[1]

Neben dem Aufbau des Index gab es einen Echtzeit-Suchmodus. Dabei startete WebCrawler mit den passendsten Treffern aus dem Index und folgte gezielt deren Links. Um zwischen mehreren Links zu wählen, verglich er den Linktext (Ankertext) mit der Suchanfrage. Das Prinzip, von ähnlichen Dokumenten aus weiterzusuchen, ging auf die Fish-Search von De Bra und Post zurück. Diese Echtzeitsuche stand der Öffentlichkeit nicht zur Verfügung.^[1]

Wie der Index funktionierte: Volltext und Vektorraummodell

Der Volltextindex basierte auf dem IndexingKit von NEXTSTEP und war invertiert: Die Suche nach einem Wort lieferte direkt eine Liste der Dokumente, die dieses Wort enthalten. Anfragen wurden nach dem Vektorraummodell von Gerard Salton bearbeitet.^[1]

Vor der Indexierung zerlegte ein lexikalischer Analysator Titel und Text eines Dokuments in Wörter. Häufige Füllwörter wurden über eine Stoppliste ausgeschlossen. Jedes Wort erhielt ein Gewicht: seine Häufigkeit im Dokument geteilt durch seine Häufigkeit in einem Referenzbestand. Wörter, die in einem Dokument oft, sonst aber selten vorkommen, wurden am höchsten gewichtet.^[1]

Die Relevanz eines Treffers ergab sich aus der Summe der Produkte aus Wortgewicht im Dokument und Wortgewicht in der Anfrage, geteilt durch die Zahl der Anfragewörter. Die Ergebnisliste zeigte Titel und URL, sortiert nach Relevanz und normiert auf 1.000 für den besten Treffer.^[1]

Kennzahlen aus dem Paper (Stand 1994)

Die folgenden Werte nennt Pinkerton für den damaligen Betrieb. Sie zeigen, in welcher Größenordnung sich das Web und seine Durchsuchung 1994 bewegten.^[1]

Erkenntnisse aus dem Betrieb

Pinkerton fasst seine Erfahrungen in mehreren Lehren zusammen. Grundlage waren der direkte Kontakt mit Nutzern und eine Online-Umfrage mit rund 500 Teilnehmenden.^[1]

• Volltextindexierung ist notwendig: Konkurrierende Dienste wie JumpStation und WWWW werteten nur Titel und Ankertexte aus, nur der RBSE Spider indexierte ebenfalls Inhalte. Da etwa jedes fünfte Dokument keinen Titel hatte und Titel den Inhalt oft schlecht wiedergeben, hätte ein reiner Titelindex viel ausgelassen.
• Nicht die Trefferzahl, sondern die Genauigkeit ist das Problem: Es wurden genug relevante Dokumente gefunden (Recall), aber zu viele unpassende (Precision). Ein Grund waren sehr kurze Anfragen mit durchschnittlich 1,5 Wörtern.
• Breitensuche auf Server-Ebene ergibt einen brauchbaren Index und verteilt die Last: Bei einem Lauf über das gesamte Web sah ein einzelner Server im ungünstigsten Fall alle paar Stunden einen Zugriff.
• Roboter sind trotz Ineffizienz sinnvoll: Der Index spart Nutzern lange Klickwege. Pinkerton schätzt, dass sich die Bandbreite für das Indexieren nach etwa acht Tagen amortisiert.
• Die Steuerung durch Server-Betreiber hilft: Pinkerton verweist auf den Vorschlag von Martijn Koster (im Paper als Martin Koster geschrieben), über eine Datei robots.txt festzulegen, welche Dokumente Roboter abrufen sollen.

Was davon bis heute gilt

Das Grundprinzip, das Pinkerton 1994 beschreibt, prägt Websuchmaschinen bis heute: Ein Crawler ruft Seiten über ihre URL ab, liest die Links aus, um weitere Seiten zu entdecken, und ein Indexer erfasst die Inhalte so, dass Anfragen schnell beantwortet werden können. Auch die Gewichtung von Wörtern nach ihrer Häufigkeit im Dokument und im Gesamtbestand ist ein Grundgedanke des Information Retrieval geblieben.

Der Vorschlag zur Datei robots.txt, auf den das Paper verweist, wurde 2022 von der IETF als RFC 9309 standardisiert.^[3] Damit ist eines der Steuerungsmittel, die WebCrawler 1994 schon nutzte, heute formal beschrieben.

Für die Geschichte der Suchmaschinenoptimierung ist das Paper ein frühes Dokument dafür, dass Suchmaschinen Inhalte selbst abrufen, auswerten und indexieren. Wie Google Seiten heute in den Index aufnimmt, erklärt der Artikel zur Google-Indexierung.