2. Übungsblatt - Web Mining
Suchmaschinen
Abgabetermin: Sonntag, 16.5.2010-
Schreiben Sie einen einfachen Crawler. Die in der Vorlesung behandelten Verfahren zur Optimierung brauchen Sie dabei nicht zu berücksichtigen. Der Crawler sollte
- keine URLs doppelt besuchen, d.h. Sie sollten URLs kanonisieren
- die Server nicht zu sehr in Anspruch nehmen, z.B. könnten Sie den Bot nach jedem Request eine kurze Pause machen lassen.
Beim Abarbeiten der Link-Queue sollte er die
- Breadth-First-Strategie (neue Links werden hinten in der Queue einsortiert)
- Depth-First Strategie (neue Links werden vorne in der Queue einsortiert)
anwenden können und Zähler führen, die die Aufstellung folgender Statistiken erlauben:
- Vergleichen Sie die Anzahl der URLs einer Seite mit der Anzahl derjenigen, die davon neu sind, d.h. nicht schon mal gefunden wurden. Entscheiden sie selbst wie sie diesen Vegleich erstellen (z.B. anhand eines Streudiagramm mit einen Punkt pro Seite oder doppelten Balkendiagramms mit einer geeigneten x-Achse, etc.).
- Erstellen Sie ein Histogramm über die Anzahl der URLs pro Seite (wie beim ersten Übungsblatt mit den Worthäufigkeiten, auch logarithmisch)
- Erstellen Sie ein Histogramm mit den Häufigkeiten des Auftretens von Hyperlinks (d.h., wie viele Links treten 1-mal auf, wie viele 2-mal, ...)
- Ermitteln Sie die Anzahl der unterschiedlichen Host Names, die Sie antreffen.
Starten Sie den Crawler an einer Seite Ihrer Wahl, lassen Sie ihn eine Weile (zumindest 1000 Seiten) laufen und erstellen Sie die genannten Statistiken jeweils für beide Suchstrategien.
Schreiben Sie auch eine kurze Zusammenfassung über Ihre Erfahrungen bzw. etwaige Probleme mit dieser Aufgabe.
-
Schätzen Sie mit der in der Vorlesung kennengelernten Methode die Größe des Webs anhand des Such-Overlaps zweier Suchmaschinen ab (die zugrundeliegenden Queries sollten eine überschaubare aber nicht zu kleine Anzahl von Treffern retournieren).
Hinweis: Für eine korrekte Abschätzung brauchen Sie auch eine Abschätzung der Größe des Index der verwendeten Suchmaschine. Solche Informationen finden sich manchmal auf der Homepage der Suchmaschine, einiges auch auf blog.searchenginewatch.com, doch leider werden solche Daten immer seltener publiziert. Sie können versuchen, die Resultate der Suchmaschine selbst zu verwenden um die Index-Größe abzuschätzen. Vor einiger Zeit war es z.B. möglich, in Google nach "* *" zu suchen. Vielleicht fallen Ihnen dazu selber Ideen ein. Beachten Sie dabei aber auch, daß Suchmaschinen ihre Trefferanzahl oft aufblähen beispielsweise durch Duplikate in den Resultaten. Weitere hilfreiche Informationen finden sich auf www.worldwidewebsize.com. Sie können auch die dort angegebenen Schätzwerte verwenden. Vergleichen Sie dann Ihre Schätzwerte für die Größe des Webs mit den dort angegebenen.
Hilfreiche Module:
Zweck | Perl | Python |
---|---|---|
Laden einer Web-Seite | LWP::Simple | urllib |
Extrahieren von Hyperlinks | HTML::LinkExtor | SGMLParser (Beispiel),
htmldata |
Queueing | collections.deque | |
Kanonisierung von URLs | URI | urlparser |
Queries an Suchmaschinen | WWW::Search::AltaVista etc. | web_search |