Lexikon

Web-Roboter

Die Größe des World Wide Webs macht die Suche nach Informationen zu einem bestimmten Thema sehr schwer. Allein durch manuelles Durchsuchen von Web-Seiten mit einem Browser ist eine umfassende Informationssuche nicht möglich. Man hat eine bessere Chance die gewünschte Information zu finden, wenn man die Dienste von Suchmaschinen wie Altavista in Anspruch nimmt. Diese verwalten in der Regel einen Index, der Stichwörter mit Web-Seiten verbindet. Eine Anfragesprache ermöglicht eine gezielte Suche in diesem Index.

Die Indizes werden meistens automatisch aufgebaut. Programme, die diese Aufgabe übernehmen, gehören zur Gruppe der Web-Roboter.

Web-Roboter kommunizieren automatisch, d.h. ohne menschliche Steuerung, mit Web-Servern. Sie können Web-Seiten laden, diese analysieren und aufgrund dieser Analyse über das weitere Vorgehen entscheiden. Web-Roboter automatisieren den manuellen Umgang eines Menschen mit einem Web-Browser. Im Gegensatz zu klassischen Robotern arbeiten sie nicht in einer physikalischen Welt, sondern ihre Umgebung ist das Internet. Die wichtigsten Anwendungsfelder sind:

  • Aufbau von Indizes für Suchdienste,
  • Überwachung von Änderungen von Web-Seiten,
  • intelligente Informationsbeschaffung.

Web-Roboter werden auch Web Crawler oder Web Wanderer genannt. Sie gehören zur Kategorie der intelligenten Agenten, auch Softbots (software robots) genannt. Dies sind autonom agierende Softwareeinheiten, die Informationen aufnehmen und verarbeiten, wobei sie standardisiert mit ihrer Umgebung einschließlich anderer Agenten interagieren.

Je nach Ausprägung treffen Web-Roboter autonom Entscheidungen basierend auf ihren Wahrnehmungen, den Antworten der Web-Server. Die Kommunikation mit ihrer Umgebung basiert auf dem Protokoll HTTP. Zur Repräsentation des wichtigsten Objektes der Kommunikation, den Web-Seiten, wird die Sprache HTML verwendet. Web-Roboter arbeiten in einer unbekannten, sich ständig ändernden Umgebung: Web-Server können temporär nicht erreichbar sein, Web-Seiten ändern sich schnell, instabile Verbindungen.

Aus diesem Grund müssen Web-Roboter robuste Systeme sein und unter diesen Randbedingungen korrekt arbeiten. Die Grundlage für das Auffinden neuer Dokumente bildet die Hypertextstruktur des Webs. Diese macht das Web zu einem gerichteten Graphen, wobei die Verweise die Kanten bilden. Um bei der Suche nach neuen Dokumenten systematisch vorzugehen, werden die aus der Graphentheorie bekannten Suchverfahren wie Breiten- oder beschränkte Tiefensuche verwendet. Häufig werden von einer Web-Seite aus startend, rekursiv alle Verweise verfolgt. Dies setzt voraus, daß der Roboter alle relevanten URLs aus dem HTML-Quelltext isolieren kann. Zur Analyse von Web-Seiten werden HTML-Parser eingesetzt, die je nach Aufgabenstellung den Quelltext mehr oder weniger detailliert analysieren.

Web-Roboter zum Aufbau von Indizes für Suchdienste verwenden häufig die Breitensuche. Ausgehend von einer oder mehreren URLs durchsuchen sie das Web und extrahieren nach verschiedenen Verfahren Wörter, welche in die Indizes eingefügt werden. Dabei werden sowohl statistische Methoden wie Worthäufigkeiten und inverse Dokumentenhäufigkeiten als auch probabilistische Methoden eingesetzt. Viele Roboter untersuchen die Dokumente vollständig, andere nur Titel und Überschriften. Zur Unterstützung komplexer Anfragen werden neben Indizes auch die Anfänge der Dokumente (z.B. die ersten 100 Wörter) abgespeichert.

Da das Laden und Analysieren von Seiten aufwendig ist, wird nicht jede gefundene URL weiter verfolgt. Statt dessen verwenden Web-Roboter Heuristiken, um URLs von informationsreichen Web-Seiten herauszufiltern. Der Web-Roboter des Suchdienstes Lycos bevorzugt z.B. URLs mit kurzen Pfadangaben, da die zugehörigen Dokumente häufig Home-Pages sind und viele aussagekräftige Verweise auf andere Seiten haben.

Web-Roboter können auch für sehr komplexe Aufgaben eingesetzt werden und haben sich zu einem interessanten Anwendungsgebiet der KI entwickelt. Es gibt mittlerweile viele Anwendungen im Web, welche automatisiert werden können:

  • Preisvergleiche von Produkten verschiedener Händler,
  • Überwachung von dynamischen Datenquellen,
  • gezielte Informationsbeschaffung.

Diese Aufgaben bilden eine größere Herausforderung für Web-Roboter als Suchdienste und es gibt bisher nur wenige Prototypen. Die Analyse von Dokumenten kann sich nicht allein auf die von HTML vorgegebenen Auszeichnungselemente stützen. Bei den bisher realisierten intelligenten Web-Robotern kommen folgende Techniken zum Einsatz:

  • Einschränkung der Menge potentiell relevanter Seiten durch Verwendung verschiedener Informationsquellen: Email-Server, Archive von News-Gruppen, Datenbanken von Bibliotheken und Suchdienste.
  • Heuristiken zur Erzeugung von URLs von Home-Pages (z.B. wird turau@informatik.fh-wiesbaden.de zu 
    www.informatik.fh-wiesbaden.de/~turau) .
  • Analyse von kleinen Bereichen von HTML-Dokumenten unter Verwendung einfacher Grammatiken.

Der Roboter Ahoy! bestimmt die URLs von Home-Pages von Personen aufgrund von Namen. Mit Hilfe externer Quellen wird versucht, die E-mail-Adresse zu bestimmen, um daraus mittels Heuristiken Rückschlüsse auf Kandidaten für URLs zu ziehen. Durch eine Analyse des Titels dieser Dokumente werden dann potentielle Home-Pages herausgefiltert. Der eigentliche Inhalt der Seiten wird nicht analysiert.

Webfind versucht die URLs wissenschaftlicher Arbeiten aufgrund von Wörtern aus dem Titel herauszufinden. Als primäre Informationsquelle dienen Bibliotheksdatenbanken. Aus ihnen werden Angaben über Autoren und deren Institutionen extrahiert. Ausgehend von Home-Pages der Autoren oder Institutionen wird rekursiv nach dem Dokument gesucht. Analysiert werden dabei nur kleine Ausschnitte der HTML-Dokumente: zwei Zeilen vor und nach Hyperlinks.

Einige Roboter beschränken sich auf die Analyse von Dokumenten mit einer einfachen logischen Struktur. Dazu werden Grammatiken von Dokumenttypen erstellt und mit Hilfe von Mustervergleichen einzelne sinntragende Elemente identifiziert. FAQ-Miner und FAQ-Finder sind Web-Roboter zur Informationsbeschaffung aus FAQ-Dokumenten. Durch einen Vergleich mit einer einfachen Grammatik dieser Dokumente werden Frage-Antwort Paare extrahiert. Mit Hilfe von statistischen Verfahren und semantischen Netzen werden dann zur Benutzeranfrage ähnliche Fragen in FAQ-Dokumenten bestimmt.

Der Web-Roboter ShopBot arbeitet ebenfalls mit einer Grammatik für Dokumententeile. Er nimmt Preisvergleiche unter Verkaufsangeboten im Web vor. Dabei wird die homogene Gestaltung von Web-Seiten von Online-Händlern ausgenutzt. Diese bieten oft Suchformulare zur Anforderung artikelspezifischer Daten. ShopBot analysiert nur <FORM> Tags. Das Besondere an ShopBot ist die Verwendung eines Lernalgorithmus zur Analyse dieser Formulare. Nach Abschluß der Lernphase werden Preisanfragen durch parallele Auswertung der bestimmten Suchformulare durchgeführt. Die URLs von Händlern werden ShopBot vorgegeben.

Die beschriebenen Web-Roboter sind noch sehr spezialisierte Systeme. Die Entwicklung praktisch verwendbarer Web-Roboter ist eine große Chance, KI-Technologien im größeren Umfang einzusetzen. Das Web ist eine enorme Informationsquelle, welche im Gegensatz zu vielen anderen Quellen elektronisch vorliegt, eine schwache Strukturierung trägt und permanent erweitert und aktualisiert wird.

Die bisher beschriebenen Web-Roboter sind nicht mobil. Sie kommunizieren zwar mit Web-Servern, welche geographisch verteilt sind, das eigentliche Programm läuft jedoch auf einem Rechner ab. Mobile Agenten haben die Fähigkeit, unter Bewahrung eines internen Zustandes auf andere Rechner zu migrieren. Um in einer heterogenen Umgebung zu operieren, muß ihr Code plattformunabhängig sein. Hierzu werden häufig Scriptsprachen wie Telescript oder auch Java verwendet. Dies erfordert einen entsprechenden Interpreter auf jedem Rechner, der besucht werden soll. Es gibt bisher nur wenige Probleme, welche wirklich die Mobilität von Agenten erfordern. J. Ousterhout, der Autor von Tcl, nannte mobile Agenten „a solution in search of a problem". Viele der diskutierten Anwendungen, wie z.B. Online-Auktionen, werfen zudem auch noch viele ungelöste Sicherheitsfragen auf: Wie kann ein Agent vor Manipulationen durch einen Hostrechner und umgekehrt geschützt werden.

Web-Roboter sind nicht auf jedem Server willkommen. Sie belasten das Netzwerk, behindern richtige Besucher und verfälschen Zugriffshäufigkeiten. So möchten die Betreiber von Suchdiensten sogenannte Metasuch-Roboter von ihren Web-Servern fernhalten. Unvorsichtig erstellte Web-Roboter können versehentlich komplexe CGI-Skripte starten. Sich täglich ändernde Web-Seiten sollten nicht indiziert werden. Der Robot Exclusion Standard gibt Administratoren von Web-Servern eine Möglichkeit, die Bereiche anzuzeigen, welche von Robotern gemieden werden sollten. Eine einfach strukturierte Textdatei mit dem Namen robots.txt im Wurzelverzeichnis des Servers gibt Auskunft, welche Seiten für welche Web-Roboter nicht zugänglich sind. Es gehört zum guten Stil des Internets, diese Konvention einzuhalten. Der Standard hat seit seiner Einführung 1994 breite Anerkennung gefunden und es ist ein Internet Draft der IETF in Arbeit. Bei einer 1997 durchgeführten Untersuchung wurde auf 2.4% aller Web-Server eine solche Datei vorgefunden.

Es gibt Bibliotheken zum Erstellen von Web-Robotern. Die Bibliothek LWP ist in Perl 5 geschrieben und basiert auf der Bibliothek libwww von R. Fielding. LWP enthält Klassen zum Parsen von HTML-Dokumenten und zur Handhabung von URLs, mit deren Hilfe Web-Roboter erstellt werden können. Eine gute Quelle für Information über Web-Roboter sind die Web Robot Pages von M. Koster.

Literatur

  1. Burke, R., Hammond, K., Kulyukin, V., Lytinen, S., Tomuro, N. and Schoenberg, S., Question Answering from Frequently Asked Question Files: Experiences with the FAQ Finder System, TR-97-05, Univ. of Chicago, 1997.
  2. Doorenbos, R., Etzioni, 0., and Weld, D., A Scalable Comparison-Shopping Agent for the World-Wide Web, Proc. ACM Conf. Autonomous Agents, 1997.
  3. Etzioni, 0., Moving Up the Information Food Chain: Deploying Softbots on the World Wide Web, Proc. 14th Nat. Conf. On AI,1996.
  4. Gudivada, V., Raghavan, V., Grosky, W., and Kasanagottu, R., Information Retrieval on the World Wide Web", IEEE Internet Computing, Vol. 1, No. 5, 58-68, 1997.
  5. Hsu, J. and Yih, W.,„Template-Based Information Mining from HTML Documents, 14th Nat. Conf. on AI, 256262, 1997.
  6. Kiniry, J. and Zimmerman, A., A Hands-on look at Java Mobile Agents, IEEE Internet Computing, Vol. 1, 21-30, 1997.
  7. Koster, M., A Method for Web Robots Control, Network Working Group Internet Draft, 
    http://info.webcrawler.com/mak/projects/robots/norobots-rfc.html, 1996.
  8. Koster, M., The Web Robots Pages, 
    http://info.webcrawler.com/mak/projects/robots/robots.html
  9. Monge, A. and Elkan, C., WebFind: Automatic Retrieval of Scientific Papers over the World Wide Web, AAAI Fall Symp. On AI Applications in Knowledge Navigation and Retrieval, 1995.
  10. Shakes, J., Langheinrich, M. and Etzioni O., Dynamic Reference Sifting: A Case Study In The Homepage Domain, Proc. of the 6th Int. WWW Conf., 189-200,1997.
  11. Turau, V., Eine empirische Analyse von HTML-Dokumenten im WWW, Technischer Report 0198, FH Wiesbaden,1998 
    http://www.informatik.fh-wiesbaden.de/~turau/ewa/ewa.html.
  12. Wong, C., Web Client Programming with Perl, O'Reilly, 1997. 
    Eingegangen am 02.04.1998

Autor und Copyright

Volker Turau
Fachbereich Informatik
FH Wiesbaden
Kurt-Schumacher-Ring 18
65197 Wiesbaden
turau@informatik.fh-wiesbaden.de

© 1998 Informatik Spektrum, Springer-Verlag Berlin Heidelberg