Das Internet erlebt in den letzten Jahren ein enormes Wachstum. Vor allem der 'bunte' Teil
des Internets, das World Wide Web erreichte eine phänomenale Popularität.
Es ist leicht, eine Seite im WWW abzurufen, und fast ebenso leicht ist es, ein Seite mit
der Dokumentenbeschreibungssprache HTML
zu gestalten.
Dies hat in den letzten drei Jahren zu einem exponentiellen Wachstum der Anzahl abrufbarer
Seiten geführt. Nach groben Schätzungen existieren im World Wide Web gegenwärtig etwa
50- 120 Millionen Seiten [12].
Das schnelle Wachstum führte zu einer Informationsüberflutung. Suchmaschinen sind ein Ansatz,
die Informationsvielfalt zu indexieren.
Im folgenden wollen wir uns auf die Besprechung von Suchmaschinen im World Wide Web (WWW) beschränken und nicht weiter auf andere Suchdienste des Internets, wie z.B. Archie eingehen.
Der Begriff ``Suchmaschine'' wird von verschiedenen Autoren unterschiedlich umrissen. Der allgemeinste Ansatz versteht unter Suchmaschinen alle Programme, die Informationen manuell oder automatisch indexieren und für anderen Nutzer zugänglich machen.
Die lokale Suche innerhalb eines WWW- Servers war eine der ersten Möglichkeiten, dem Benutzer
die Suche nach relevanten Informationen im WWW zu ermöglichen. Dabei handelt es sich um eine
einfache Stichwortsuche, die auf das Dokumentenverzeichnis des lokalen WWW-Servers zugreift.
Dieses Suchverfahren war schon von den WWW-Entwicklern am CERN durch die
Dokumentenbeschreibungssprache HTML und das WWW-Übertragungsprotokoll
HTTP vorgegeben worden. Das HTML-Element
ISINDEX
kennzeichnet dabei eine Suchmöglichkeit innerhalb des jeweiligen Dokuments.
Die Aufgabe des Browsers ist es, innerhalb des Dokuments ein Eingabefeld für Suchbegriffe
anzubieten. Den Inhalt des Feldes hängt der Browser an die
URL an, die dem Server gesendet wird.
Der Server führt die Suche auf seinem Datenbestand aus und liefert die Ergebnisse als
HTML-Dokument zurück.
Heutig Web-Server beinhalten oft eine so große Anzahl von Dokumenten, daß eine einfache Stichwortsuche oft nur unbefriedigende Ergebnisse liefert. Mit dem HTML-Element FORM besteht die Möglichkeit, komplexere Suchmasken aufzubauen. Die Suchbegriffe, zusammen mit den Feldnamen und Verknüpfungen, werden an den Server gesendet, der Hintergrundprogramme zur Bearbeitung der Anfrage startet. Damit wird neben vielen weiteren Einsatzgebieten auch der Zugriff auf Datenbanken ermöglicht.
Um nicht jeden Server einzeln Abfragen zu müssen, existieren eine ganze Reihe von Systemen, die die von einzelnen Servern bereitgestellten Daten zu einem gemeinsamen Index verbinden. Beispiele für dieses Vorgehen sind die Systeme WAIS und Harvest.
Themenbasierte Zusammenstellungen von Verweisen waren seit Anfang an fester Bestandteil des WWW. Jede Sammlung von Links auf einer HTML-Seite fällt schon unter diese Kategorie, so daß die Grenzen zwischen einer guten Homepage und einem Katalog fließend sind. Festzuhalten ist, daß Auswahl und Zusammenstellung der Verweise immer durch den Menschen vorgenommen wird.
Die Suche in Katalogen basiert auf hierarchischer Navigation in Sachgebieten. Viele Kataloge sind inzwischen so umfangreich, daß eine Stichwortsuche im Gesamtkatalog oder einem bestimmten Themenbereich angeboten wird.
Roboter sind Programme, die entlang von WWW-Hypertextstrukturen Dokumente automatisch verarbeiten und die extrahierten Daten auf einem zentralen Server ablegen. Ihr Aufbau wird in Abschnitt 3 näher besprochen.
Neben den Serverbasierten Suchdiensten werden auch Anstrengungen unternommen, die Suche von einem WWW-Client aus zu automatisieren. Bei Suchserver bestimmt der Anbieter die Suchmöglichkeiten anhand von Suchformularen und der Bereitstellung von Suchoperatoren. Auf die Suche selbst und die Relevanzbeurteilung während der Suche hat der Benutzer keinen Einfluß. Der Hintergedanke der Client-basierten Suche ist, die Suche und vor allem die Relevanzbestimmung während der Suche mehr benutzerkontrolliert zu gestalten.
Anstatt daß der Benutzer selbst durch die Hypertexte navigiert, um so zu relevanten Dokumenten zu gelangen, übernimmt der Client diese Aufgabe und sammelt automatisch die gewünschten Informationen. Deshalb werden Roboter oft auch als ``Agenten'' bezeichnet. Der Nutzer kann Suchtiefe und Art der Relevanzanalyse bestimmen und hat den Vorteil, die Suche mitverfolgen sowie beliebig anhalten und fortsetzen zu können.
Die Arbeitsweise von Client-basierten Agenten unterscheidet sich nur unwesentlich von der Arbeitsweise der Suchroboter, die im Abschnitt 3.1 besprochen werden.
Bei jeder roboterbasierten Suchmaschine lassen sich vier Grundkomponenten finden: Roboter, Indexierer, Datenbank und Benutzerschnittstelle. Bild 1 demonstriert die Zusammenarbeit der Komponenten.
In der Literatur wird meist von drei Grundkomponenten gesprochen. Mit Indexierer meint man dort die Datenbank, die den Index beherbergt und die Software, die den Index erstellt. Oft stellen diese Komponenten tatsächlich eine funktionale Einheit dar, wir besprechen sie jedoch getrennt.
Der Roboter, oft auch Spider, Wanderer oder Crawler genannt, hat die Aufgabe, das World Wide Web zu ``durchwandern'' und Informationen zu sammeln. Die Suche eines Roboters beginnt bei einer vorgegebenen Adresse. Er extrahiert relevante Informationen aus der zu der Adresse gehörenden HTML- Seite und folgt, je nach Voreinstellung, den gefundenen Links. Dies kann sequentiell oder parallel durch Starten weiterer Roboter erfolgen.
Zunächst soll ein häufig angetroffenes Mißverständnis diskutiert werden: Oft werden die Begriffe ``Roboter'' und ``Virus'' nicht klar getrennt. Im Gegensatz zu einem Virus, der seinen Code über das Netz überträgt und in fremde Systeme einschleust, bleibt Roboter, auch wenn er ``Worm'' oder ``Wanderer'' heißt, auf seinem Ursprungsrechner. Wie jeder andere HTTP- Client fordert er per GET- Befehl eine bestimmte Seite an, parst sie und folgt eventuell gefundenen Links, dadurch, daß er die zugehörigen Dokumente wiederum per GET anfordert.
Damit ist die grundlegende Arbeitsweise eines Roboters bereits beschrieben. Die Logik, die ein solcher autonomer Agent besitzen muß, wird an anderer Stelle gebraucht: Man kann das WWW als einen gerichteten Graphen auffassen. Die Knoten sind die jeweiligen Dokumente, die Kanten die Links zwischen den Dokumenten. In diesem Netzgraphen existieren Zyklen und separierte Graphen. Der Roboter braucht also eine Rückkoppelung zur Datenbasis, um zu erkennen, welche Kanten schon durchlaufen wurden. Um in separierte Teilgraphen zu gelangen, bedarf es der Möglichkeit, manuell Startadressen vorzugeben.
Beispielhaft soll eine Client-basierte Suchstrategie namens
Fish-Search betrachtet werden,
die im Programm Mosaic-Fish, einer Erweiterung des NCSA-Browsers Mosaic,
implementiert wurde.
Bei dieser Suchstrategie stellt man sich das Web als ein Gewässer vor. In dieses Gewässer werden an Stellen, von denen bekannt ist, daß sie Nahrung enthalten, einige wenige Fische gesetzt. Fische repräsentieren dabei relevante Dokumente. Die Fische vermehren sich nun und die Nachkömmlinge schwimmen in verschiedene Richtungen auf der Suche nach neuer Nahrung. Diejenigen, die keine neue Nahrung finden, sterben aus (Verweise, die nicht zu neuen relevanten Seiten führen) und diejenigen, die neue Nahrung finden, vermehren sich wieder und suchen weiter nach neuen Nahrungsquellen (Verweise zu relevanten Dokumenten). Fische können auch in verschmutztes Wasser geraten, das je nach Verschmutzungsgrad zum Sterben der Fische führen kann. Assoziiert wird das mit Dokumenten, deren Übertragung zu lange dauert oder zu oft unterbrochen wird.
Experimentelle Untersuchungen [1] der Mosaic-Fish-Entwicklergruppe zum Thema automatische Navigationsstrategien heben ergeben, daß die depth-first Suche am geeignetesten für das Erkennen der Hypertextstruktur ist. Das kommt daher, daß mit dieser Methode die sehr häufig vorkommende Kreuzverweise am schnellsten entdeckt werden und die Suche dort beendet werden kann.
Seit dem existieren des ersten Roboters [5] besteht Kritik an der Idee. Probleme bestehen vor allem in der hohen Netz- und Serverlast, die ein Roboter verursacht. Paralleles, rekursiv fortschreitendes Absuchen aller Links, die z.B. von einer Server- Homepage ausgehen, können leicht zu einer völligen Blockade des Servers oder des angeschlossenen Netzes führen. Zu dieser Last, die schon ein einzelner Agent erzeugen kann, kommen die Roboter weiterer Suchmaschinen. Mindestens zwei dutzend Roboter durchsuchen pausenlos das Web [7]. Insbesondere gegen Client-basierte Roboter läßt sich ein ethischer Einwand vorbringen: Das Resultat der Suche kommt nur einem einzelnen Nutzer zugute, während die Belastungen der Suche viele trifft. Serverbasierte Suchmaschinen stehen da etwas besser da, weil deren Suchergebnisse i.a. weltweit zu Verfügung gestellt werden.
Als Antwort auf die Überhandnahme der Roboterbelastung wurde der ``Standard for Robot Exclusion'' [8] definiert, der den Zugriff auf Web-Server regeln soll. Im Prinzip handelt es sich dabei um eine spezielle Datei im Serververzeichnis, über die Roboter erfahren, welche Dokumente bzw. Teile des Servers gelesen werden dürfen. Zwar unterliegt es dem Gutdünken des Roboterbauers, diesen Standard einzuhalten, jedoch richten sich mittlerweile die meisten Suchdienste danach.
Der Indexierer erhält Dokumente oder ausgewählte Teile davon von den Robotern. Er extrahiert nach bestimmten Strategien relevante Informationen, bestimmt die Termgewichte, erzeugt eine invertierte Liste der auftretenden Terme und ergänzt abschließend die Datenbank. Genaueres zur Indexierung steht im Abschnitt 4.
Die für Suchmaschinen benutzten Datenbanken unterscheiden sich qualitativ nicht von herkömmlichen (relationalen) Datenbanken. Eingetragen sind die gefundenen Schlüsselwörter sowie deren Verweise auf die zugehörigen Dokumente. Die meisten Suchmaschinen speichern lediglich die URLs der Dokumente, manche auch komplette Dokumente. In den meisten Datenbanken sind die Verweise sortiert nach abnehmender (vom Indexierer eingetragenen) Dokumentenrelevanz für den jeweiligen Suchbegriff.
Das Benutzer- Interface zu den Suchmaschinen stellt i.a. ein Web-Browser dar. Die Ergebnismenge wird als eine Liste von ``Treffern'' mit abnehmender Relevanz angezeigt. Manche Suchmaschinen gestatten auch eine native Anfrage an die Datenbank.
Grundsätzlich muß gesagt werden, daß es derzeit für roboterbasierte Suchmaschinen unmöglich ist, qualitativ hochwertige Information von Informationsmüll zu trennen. Das liegt an der Heterogenität des Webs, das es nahezu jedem gestattet, Informationen zu publizieren. Eine automatische Qualitätsbewertung setzt eine hohe Intelligenz des Roboters, des Indexers und des Retrievaltools voraus und ist derzeit nicht zu verwirklichen.
Allerdings gibt es einen Ansatz, mit dem zumindest ein Ranking nach der Beliebtheit einer Webseite vorgenommen werden kann. Bei diesem Verfahren wird die Anzahl der Links gezählt, die auf die zu bewertende Seite zeigen. Zwar ist eine hohen Anzahl von Verweisen nicht unbedingt ein Zeichen hohen Informationsgehalts, jedoch nutzt diese Methode indirekt Ergebnisse menschlicher Bewertung aus.
Betrachten wir im folgenden alle gefundenen Dokumente als gleich gehaltvoll.
Auf welche Arten bestimmen nun die Suchmaschinen die Relevanz von Informationen zu einer gegebenen Suchanfrage?
Noch unabhängig von konkreten Suchanfragen erfolgt eine Auswahl von Informationen
durch die Suchroboter. Manche Roboter erfassen den gesamten Text einer Seite und
überlassen die Analyse dem nachgeschalteten Indexer. Andere extrahieren nur bestimmte
Teile einer HTML- Seite, wie URL, Titel, Überschriften, hervorgehobene Stellen oder
sogenannte META-tags. Die sind spezielle HTML- Elemente, die es dem Autor ermöglichen,
Informationen über sein Dokument, z.B. Schlagworte oder Kurzbeschreibung
für den Betrachter unsichtbar im Dokument unterzubringen.
Manche Suchmaschinen (Flipper)
begrenzen ihren Suchraum auf ein bestimmtes Sprachgebiet. Dazu werden die Dokumente
nach Worten durchsucht, die mit hoher Wahrscheinlichkeit nur in einem Text der jeweiligen
Sprache auftreten.
Der Indexierer erzeugt in der Hauptsache die invertierte Dokumentenliste. Bevor dies geschieht, erfolgt im Allgemeinen eine mehr oder minder komplizierte Relevanzbewertung, die sich auf die Methoden des Information Retrieval stützt.
Zunächst wird versucht, die Bedeutung von Termen anhand Ihrer Position im Text zu ermitteln. Terme im Titel, in Überschriften usw. bekommen einen höheren Rang. Anschließend wird die Worthäufigkeit im Dokument berechnet, bezogen auf den Umfang de Dokuments. Je häufiger ein Wort im Text ist (abzüglich von Stoppworten), desto höher ist sein Rang. Der Rang eines jeden Wortes wird gewichtet mit seiner inversen Dokumentenfrequenz (IDF). Damit mißt man die Häufigkeit eines Wortes im Gesamtdokumentenbestand. Nach [14] hat ein Wort einen umso geringeren Informationsgehalt, je häufiger es im Datenbestand ist.
Die so gesammelten Daten bilden die Ausgangsinformationen für den Indexierer. Nach dem Herausfiltern von Duplikaten wird jetzt die invertierte Datei erzeugt. Jedem Schlüsselwort werden die Verweise auf Dokumente zugeordnet, in denen das Wort auftritt. Zu jeder Referenz wird gleich eingetragen, wie gut das Schlüsselwort das Dokument repräsentiert.
Abhängig von der konkreten Maschine kommen weitere Features hinzu, z.B. Stemming.
Viele Suchmaschinen unterstützen neben der Suche nach einem Schlüsselwort weitere Abfragemodi, die man in zwei Kategorien teilen kann:
Neben der üblichen Verknüpfung von Suchbegriffen durch logisches UND, ODER und oft auch NICHT bieten manche Suchdienste Nachbarschaftsoperatoren an: Diese entsprechen dem logischen UND, mit der Einschränkung, daß nur Worte betrachtet werden, die höchstens n Worte voneinander entfernt auftreten. n ist entweder vorgegeben (10 bei Alta Vista) oder vom Nutzer einstellbar.
Excite erlangte seine Bekanntheit dadurch, daß
Netscape es als Suchmaschine der Wahl mit einem Suchknopf ``fest verdrahtete''.
Exite bietet sowohl einen Katalog als auch eine Suchmaschine an. Daneben gibt es eine
lange Liste von Features, wie News-Tracker, Find-A-Map, Shareware, Email-Directory
und Personen-Finder.
Excite wirbt damit, eine Suche nach Ideen und Konzepten zu ermöglichen. Konkret sieht das so aus, daß neben den konkreten Schlüsselworten einer Suchanfrage auch nach ähnlichen Phrasen gesucht wird. Nach der Selbstdarstellung nutzt Excite Methoden der künstlichen Intelligenz, um aus indizierten Dokumenten neben den Schlagworten auch die dahinterstehenden Konzepte zu extrahieren.
Eine Suchanfrage kann auf sehr vielfältige Weise gestellt werden. Bei Angabe von Suchworten sucht Excite nach Dokumenten, die diese Worte enthalten oder solche, die einen ähnlichen Inhalt aufweisen, wie oben beschrieben. Durch die Angabe eines ``+'' vor dem Suchwort wird erzwungen, daß das Wort im gefundenen Dokument vorkommt, bei Angabe eines ``-'' darf das Wort nicht vorkommen. Weiterhin ist die Formulierung von Anfragen mittels Boolescher Operatoren möglich. Der konzeptbasierte Suchmechanismus wird dann abgeschaltet. Eine Besonderheit ist die Möglichkeit, eine Art Relevance Feedback durchzuführen. Scheint ein gefundenes Dokument besonders relevant zu sein, kann man mit ``More like This'' dieses Dokument als Beispiel für die weitere Suche benutzen und so den Ergebnisraum eingrenzen.
Alta Vista startete im Dezember 1995 und war
längere Zeit die Suchmaschine mit der größten Zahl indizierter Dokumente.
Mit Alta Vista wollte Digital Equipment (DEC) seine neuen Alpha- Server promoten
und legte die Hardware der Suchmaschinen dementsprechend gigantisch aus:
Alta Vista besteht aus fünf vernetzten Alpha- Rechnern mit insgesamt 14 Prozessoren,
7612 MByte RAM und 281 GByte Plattenspeicher. Die Datenbank beherbergt die aus
30 Millionen WWW- Seiten extrahierten Informationen, von denen 6 GByte ständig im
Speicher gehalten werden. Alta Vista erhält täglich etwa 16 Millionen
Anfragen [15].
Neben einfachen Suchanfragen unterstützt Alta Vista ``Advanced Queries'' mit den Logischen Operatoren AND, OR, NOT, NEAR sowie Klammerung beliebig geschachtelt.
Alta Vista extrahiert seine Informationen aus dem gesamten Dokumenteninhalt einschließlich der META- Tags.
InfoSeek Guide fällt zwar nicht durch die Anzahl
indizierter Dokumente auf, dafür aber durch die Relevanz seiner Suchresultate.
InfoSeek Guide indiziert den gesamten Text der besuchten Seiten und unterscheidet zwischen Groß- und Kleinschreibung (was die Suche nach Namen wesentlich erleichtert).
Hervorzuheben ist, das es wie in Excite möglich ist, eine Suchanfrage natürlichsprachlich zu stellen.
