2.​ Übungs­blatt - Web Min­ing

Suchmaschinen

Abgabetermin: Sonntag, 16.5.2010
  1. Schreiben Sie einen ein­fachen Crawler.​ Die in der Vor­lesung be­han­del­ten Ver­fahren zur Op­ti­mierung brauchen Sie dabei nicht zu berücksichtigen.​ Der Crawler sollte

    • keine URLs dop­pelt be­suchen, d.​h.​ Sie soll­ten URLs kanon­isieren
    • die Serv­er nicht zu sehr in Anspruch nehmen, z.​B.​ könnten Sie den Bot nach jedem Re­quest eine kurze Pause machen lassen.

    Beim Abar­beit­en der Link-Queue sollte er die

    • Breadth-First-Strate­gie (neue Links wer­den hin­ten in der Queue ein­sortiert)
    • Depth-First Strate­gie (neue Links wer­den vorne in der Queue ein­sortiert)

    an­wen­den können und Zähler führen, die die Auf­stel­lung fol­gen­der Statis­tiken er­lauben:

    1. Ver­gle­ichen Sie die An­zahl der URLs einer Seite mit der An­zahl derjenigen, die davon neu sind, d.​h.​ nicht schon mal ge­fun­den wurden.​ Entschei­den sie selb­st wie sie diesen Ve­g­le­ich er­stellen (z.​B.​ anhand eines Streudi­a­gramm mit einen Punkt pro Seite oder dop­pel­ten Balk­endi­a­gramms mit einer geeign­eten x-Achse, etc.​).​
    2. Er­stellen Sie ein His­togramm über die An­zahl der URLs pro Seite (wie beim er­sten Übungs­blatt mit den Worthäufigkeit­en, auch logarithmisch)
    3. Er­stellen Sie ein His­togramm mit den Häufigkeit­en des Auftretens von Hy­per­links (d.​h.,​ wie viele Links treten 1-mal auf, wie viele 2-mal, ...​)
    4. Er­mit­teln Sie die An­zahl der un­ter­schiedlichen Host­ Names, die Sie antr­e­f­fen.

    Starten Sie den Crawler an einer Seite Ihrer Wahl, lassen Sie ihn eine Weile (zu­min­d­est 1000 Seit­en) laufen und er­stellen Sie die genan­nten Statis­tiken jew­eils für beide Such­strate­gien.

    Schreiben Sie auch eine kurze Zusam­men­fas­sung über Ihre Er­fahrun­gen bzw.​ etwaige Prob­leme mit dieser Auf­gabe.

  2. Schätzen Sie mit der in der Vor­lesung ken­nen­gel­ern­ten Meth­ode die Größe des Webs an­hand des Such-Over­laps zweier Such­maschi­nen ab (die zu­grun­deliegen­den Queries soll­ten eine überschaubare aber nicht zu kleine An­zahl von Tr­e­f­fern re­tournieren).

    Hin­weis: Für eine ko­r­rek­te Abschätzung brauchen Sie auch eine Abschätzung der Größe des Index der ver­wen­de­ten Suchmaschine.​ Solche In­for­ma­tio­nen find­en sich manch­mal auf der Home­page der Such­mas­chine, einiges auch auf blog.​searchenginewatch.​com, doch lei­der wer­den solche Daten immer sel­tener publiziert.​ Sie können ver­suchen, die Re­sul­tate der Such­mas­chine selb­st zu ver­wen­den um die In­dex-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. Beacht­en Sie dabei aber auch, daß Such­maschi­nen ihre Tr­e­f­fer­an­zahl oft aufblähen beispiel­sweise durch Du­p­likate in den Resultaten.​ Weit­ere hil­fre­iche In­for­ma­tio­nen find­en 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.

Hil­fre­iche Mod­ule:

Zweck Perl Python
Laden einer Web-Seite LWP::Sim­ple url­lib
Ex­trahieren von Hy­per­links HTML::LinkEx­tor SGML­Pars­er (Beispiel),
html­da­ta
Queue­ing
collections.​deque
Kanon­isierung von URLs URI url­pars­er
Queries an Such­maschi­nen WWW::Search::Al­taVista etc. we­b_search
Die meis­ten der genan­nten Perl-Mod­ule sind im Modul Bun­dle::LWP en­thal­ten.
Kontakt

small ke-icon

Knowledge Engineering Group

Fachbereich Informatik
TU Darmstadt

S2|02 D203
Hochschulstrasse 10

D-64289 Darmstadt

Sekretariat:
Telefon-Symbol+49 6151 16-21811
Fax-Symbol +49 6151 16-21812
E-Mail-Symbol info@ke.tu-darmstadt.de

 
A A A | Drucken | Impressum | Sitemap | Suche | Mobile Version
zum Seitenanfangzum Seitenanfang