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). Arbeiten Sie die Link-Queue ab nach

• einer Breadth-First-Strategie (neue Links werden hinten in der Queue einsortiert)
• einer Depth-First Strategie (neue Links werden vorne in der Queue einsortiert)

Starten Sie den Crawler an einer Seite Ihrer Wahl, lassen Sie ihn eine Weile (zumindest 1000 Seiten) laufen und führen Sie für beide Varianten 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. Die Anzahl der gefundenen URLs pro Seite (am besten wieder als Kurve wie am ersten Übungsblatt)
3. die Häufigkeit des Auftretens von Hyperlinks (i.e., wie viele Links treten 1-mal auf, wie viele 2-mal, ...)
4. Die Anzahl der unterschiedlichen Hosts, die Sie antreffen

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::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.