2. Übungsblatt - Web Mining

Schreiben Sie einen einfachen Crawler. Die in der Vorlesung behandelten Verfahren zur Optimierung brauchen Sie dabei nicht zu berücksichtigen. Sie sollten jedoch sicherstellen, daß Sie (a) keine URLs doppelt besuchen (d.h. Sie sollten URLs kanoniseren) und (b) die Server nicht zu sehr in Anspruch nehmen (Sie könnten z.B. nach jedem Request eine kurze Pause einlegen (in Perl mit dem Kommando sleep n, wobei n die Anzahl der Sekunden ist). Es bleibt Ihnen überlassen, nach welcher Strategie Sie die Link-Queue abarbeiten (Breadth-First, Depth-First, nach Anzahl der Verweise auf einen Link, Random Selection, etc.)

Starten Sie den Crawler an einer Seite Ihrer Wahl, lassen Sie ihn eine Weile laufen und führen Sie folgende Statistiken:

1. Die Anzahl der gefundenen URLs vs. die Anzahl der neuen URLs (i.e., URLs, die noch nicht in der Queue gefunden wurden)
2. Eine Statistik über die Anzahl der gefundenen URLs pro Seite (am besten wieder als Kurve wie am ersten Übungsblatt)
3. Eine Statistik über die Häufigkeit des Auftretens von Hyperlinkes (i.e., wie viele Links treten 1-mal auf, wie viele 2-mal, ...)
4. Die Anzahl der URLs pro Site, bzw. wieviel Prozent des Crawls Sie an ein und demselben Host verbringen.
5. Eine Statistik über die Rechenzeit, d.h. wie viel Zeit Sie in welchem Teil des Programms verbringen.

Schreiben Sie auch eine kurze Zusammenfassung über Ihre Erfahrungen bzw. etwaige Probleme mit dieser Aufgabe.

Perl Tips: Zur Programmierung in Perl empfehlen sich folgende Module: LWP::Simple zum einfachen Laden einer Web-Seite, HTML::LinkExtor zum Extrahieren von Hyperlinks aus einer Seite, URI zur Kanonisierung von URLs, Benchmark zum Stoppen der Laufzeit. Diese Module sind bereits vorhanden (z.B. bei ActivePerl), bzw. werden installiert, wenn Sie Bundle::LWP installieren. Perl-Module installieren Sie am einfachsten mit perl -MCPAN -e shell und dann mit install modul-name.

NOTE: Vergessen Sie nicht, daß Sie den Crawler auch eine Zeit lang laufen lassen müssen, d.h. beginnen Sie rechtzeitig!

Schätzen Sie mit der in der Vorlesung kennengelernten Methode die Größe des Webs anhand des Such-Overlaps zweier Suchmaschinen ab (die zugrundeliegende Query sollte eine überschaubare aber nicht zu kleine Anzahl von Treffern retournieren).

Perl Tips: In Perl kann diese Aufgabe am einfachsten mit einem wenige Zeilen langen Programm gelöst werden, das das Modul WWW::Search bzw. seine Sub-Klassen für einzelne Suchmaschinen (z.B. WWW::Search::Lycos oder WWW::Search::AltaVista) verwendet. Sie müssen aber nicht Perl verwenden, auch Lösungen in anderen Sprachen oder sogar Hand erstellte Lösungen sind zulässig.

NOTE:Für eine korrekte Abschätzung brauchen Sie auch eine Abschätzung der Größe des Index der verwendeten Suchmaschine. Solche Informationen finden sich oft auf der Homepage der Suchmaschine, einiges auch auf http://searchenginewatch.com.