Programmieraufgabe 2 (Crawler)
|
|
 |
Informationssysteme
Sommersemester 2005
From: Donnerstag, 28.04.2005
Upload deadline: Donnerstag, 19.05.2005 09:15 MEZ
|
Ziel dieser Programmieraufgabe ist es, einen einfachen Crawler zu implementieren.
Der Crawler startet auf der vorgegebenen Menge der URLs und durchsucht das Web.
Die Aufgabe des Crawlers besteht darin, die durch Links referenzierten Dokumente herunterzuladen und zu parsen.
Die extrahierten Links werden benutzt, um den Crawl fortzusetzen. Der Crawler benutzt intern eine
URL-Queue, in der die gesammelten Links sortiert werden. Der Queue sollte die "Breite-Zuerst" Strategie implementieren, d.h.
der Crawler soll zuerst direkte Nachfolger der Startdokumente (Tiefe=1), dann deren Nachfolger (Tiefe=2) etc.
verarbeiten. Die Suche soll fortgesetzt werden, bis die maximale eingestellte Tiefe erreicht ist und es keine
weiteren Links zum Crawlen mehr gibt.
Der Crawler verwendet den ISParser (Aufgabe 1), um die Inhalte der HTML-Dokumente (Links, Woerter und deren Stammformen) zu extrahieren.
Die extrahierten Inhhalte der gecrawlten Dokumente sollen intern in Form von Objekten mit Interface ISDokumentInterface
verwaltet werden. Die Speicherung dieser Inhalte findet (noch) nicht statt - das wird zum Ziel unserer
naechsten Aufgabe. Lediglich die extrahierten Links werden benutzt, um die URL-Queue zu fuellen (anschliessend werden Objekte
ISDokument 'verworfen', spaeter sollen deren Inhalte in die Datenbank gespeichert werden).
Jede URL darf nur einmal besucht werden, die Duplikate einer bereits besuchten URL sollten beim Crawl ignoriert werden.
Der Crawler soll in einem separaten Einzel-Thread parallel zum aufrufenden Programm laufen. Der Aufrufer sollte in der Lage
sein, den Crawler jederzeit zu starten, zu stoppen oder zurueckzusetzen.
Zur Vereinfachung der Aufgabe machen wir folgende Annahmen:
- es ist ausreichend, den Crawler in einem separaten Einzel-Thread (ohne Multithreading) zu implementieren.
- es werden nur HTML-Dokumente verarbeitet, andere Datentypen (PDF, DOC etc.) koennen ignoriert werden.
- es wird angenommen, dass alle gecrawlten Dokumente in Englisch verfasst sind und insofern vom Porter Stemmer
verarbeitet werden können
- bei der Kontrolle der besuchten URLs beschraenken wir uns auf den Vergleich der URL-Strings (z.B. http://www.yahoo.de
und http://de.yahoo.com sind fuer unseren Crawler zwei verschiedene Links, obwohl sie in Wirklichkeit zum gleichen HTML-Dokument
fuehren)
- der Crawler verwendet nur HTTP zum Download der Dokumente. Weitere Protokolle (z.B. FTP) koennen ignoriert werden.
Der Crawler besteht aus folgenden Komponenten:
- Die Crawler-Klasse ISCrawler (interface ISCrawlerInterface),
der eine URL-Queue und den Parser zur Verarbeitung der HTML-Inhalte enthaelt.
- Objekte ISDokumentInterface, die zur Zwischenspeicherung der extrahierten Inhalte benutzt werden,
- Linksammlung zum Testen der Implementierung
Zu den Funktionen der Klasse ISCrawler gehoeren insbesondere
- Starten, Stoppen und Zuruecksetzen des Crawlers;
- Hinzufuegen neuer Links zu der URL-Queue;
- Ueberpruefung, ob die gegebene URL bereits besucht wurde
- Download und Verarbeitung der Web-Dokumente
Die Funktionen des Crawlers sind durch Interface ISCrawlerInterface vorgegeben.
Die Klasse ISCrawler (interface ISCrawlerInterface) ist verbindlich, der Rest
(insbesondere die Architektur der URL-Queue, die Realisierung der "Breite-Zuerst" Suchstrategie und die
Buchfuehrung ueber bereits besuchte Links) steht Ihnen frei.
Sammlung der Links
Eine manuell vorbereitete Liste
enthaelt mehrere Links zu den Themen Information retrieval und Data Mining. Einige Links sind 'fehlerhaft'
(nicht existierende Seiten, Weiterleitungen, Timeouts), um die Stabilitaet des Crawlers zu testen.
Der Crawler kann fuer Testzwecke diese Seite als ein Startdokument verwenden.
Tips
- Die Java-Standardbibliotheken (java.net.*) sind ausreichend, um den einfachen Crawler zu realisieren.
Erweiterte Features (eigene Kontrolle der blockierenden Operationen wie Netzwerk-Timeouts, mehrfacher HTTP-Redirects,
Unterstuetzung der Cookies und Robot Exclusion Regeln) sind optional. Der Crawler sollte allerdings den
vorgegebenen Mindestumfang an Funktionalitaet erfuellen und stabil laufen.
- Zur Konvertierung der 'relativen' extrahierten Links in die absolute Form verwendet man den URL-Konstruktor
new URL (base_url, link), wo base_url ist die URL der aktuellen Seite und
link ist der (relative oder absolute) Link, der aus dieser Seite extrahiert wurde.
Fuer link-URLs im 'absoluten' Format wird base_url einfach ignoriert.
- Der Crawler sollte nur HTTP-Links verfolgen. Der Protokolltyp einer URL
kann mit der Funktion getProtocol() des URL-Objektes abgefragt werden. Fuer uns interessant sind nur
URLs mit "http", alles andere (z.B. mailto, ftp..) sollte ignoriert werden.
- der Crawler sollte nur HTML und ggf. noch Textdokumente verarbeiten. Den Typ des aktuellen dokuments kann man nach dem
Oeffnen einer HttpURLConnection mit der Funktion getContentType() abfragen. Fuer uns interessante Werte sind
"text/html", "text/plain" und null ("text/html" ist default-Wert). Alles andere kann
ignoriert werden.
- Zur Ausfuehrung in einem separaten Thread soll der Crawler das Java-Interface Runnable implementieren und die Startmethode
run() enthalten. Der Start eines neuen Threads der Runnable-Klasse erfolgt in Java mit new Thread (meine_runnable_klasse).start().
Dieser Aufruf startet die Methode run() der Runnable-Klasse in einem neuen Thread parallel zum Aufrufer.
Weitere Informationsquellen zum Nachlesen
- Mercator: A Scalable, Extensible Web Crawler
- Performance Limitations of the Java Core Libraries
- Design and Implementation of a High-Performance Distributed Web Crawler
- Some interesting Web statistics (Google)