Übung 2 - Web Min­ing

Der Up­load ist erneut bis Don­ner­stag, 28.​5.​ offen, um die fehlen­den Daten hochladen zu können.

Die Lan­guage Chal­lenge wurde aufgelöst.

Die Auf­gaben­stel­lung wurde im Bezug auf die zu ver­wen­dende Such­strate­gie präzisiert (12.​05.​).​

Zu den tech­nis­chen Her­aus­forderun­gen beim Auf­bau einer rel­a­tiv großen, glob­alen Such­mas­chine gab es auf dem SUMA 2015 Kongress einen in­ter­es­san­ten Vor­trag: https://​www.​youtube.​com/​watch?v=Yt6­bIl0ZQ2g

1. (3 Punk­te) En­twick­eln Sie auf der Basis der in Übungs­blatt 1, Auf­gabe 4 her­aus­ge­fun­de­nen Statis­tiken über Sprachen ein ein­fach­es Ver­fahren, mit dem es möglich ist, die Sprache eines Textes an­hand der Häufigkeit­en von Buch­staben und Buch­staben­paaren vorherzusagen. 
   Im­ple­men­tieren Sie ein Pro­gramm, das durch Ver­wen­dung Ihres Ver­fahrens in der Lage ist, die Sprache (Deutsch - En­glisch - Spanisch) einer Web-Seite zu ermitteln.​ Das Pro­gramm soll dabei nicht fähig sein, zu lernen.​ Sie sollen Ihr Sprachen­mod­ell sozusagen in die Funk­tion hard­co­den.
   1. Erklären Sie kurz ihr Ver­fahren z.​B.​ auch mit­tels Pseu­docode.
      
   2. Gehen Sie auf /lehre/ss15/web-min­ing/u2languagechallenge.​html  und er­mit­teln Sie die Sprache der 10 dort erhältlichen Webseiten.​ Die er­sten Fünf er­hal­ten nur eine Liste von Buch­staben, die let­zten 5 Buchstabenpaare.​ Schreiben für jeden Text das Ergeb­nis zeilen­weise in eine Datei na­mens challenge.txt im For­mat "Seiten­num­mer Sprache\n". Be­denken Sie für die er­sten 5 Seit­en, daß Ihr Ver­fahren auch funk­tion­ieren soll, falls nur Buch­staben und keine Buch­staben­paare vor­liegen.
2. (5 Punk­te) 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 auf dem gle­ichen Host eine kurze Pause machen lassen,
   • eine ran­domisierte Such-Strate­gie ver­fol­gen, d.​h.​ neue Links wer­den hin­ten in die Queue ein­sortiert, aber der nächste anzus­teuernde Link wird zufällig gewählt,
   • Zähler führen, die die Auf­stel­lung fol­gen­der Statis­tiken er­lauben:
   1. 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 log­a­rith­misch).
   2. 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, ...​).​
   3. Überlegen Sie sich ein ein­fach­es Ver­fahren, um Du­p­likate festzustellen, und beschreiben Sie es.​ Das Ver­fahren sollte dabei z.​B.​ Daten­bank-gener­ierte Seit­en, bei der sich nur kurze Pas­sagen wie Zei­tangaben, Nav­i­ga­tion­sleis­ten, Wer­beein­blendun­gen un­ter­schei­den, als Du­p­likate erkennen.​ Wenden Sie ihr Ver­fahren nachträglich auf die herun­terge­lade­nen Seit­en an und er­mit­teln Sie die An­zahl der ge­fun­de­nen Duplikate.​ Verifizieren Sie Ihr Ver­fahren stich­probe­nar­tig und zeigen Sie ein repräsen­ta­tives Beispiel auf.
   4. Ver­wen­den Sie Ihr Ver­fahren aus der er­sten Teilauf­gabe, um die Sprache der herun­terge­lade­nen Seit­en zu ermitteln.​ Geben Sie die Verteilung über die ge­fun­de­nen Sprachen an.
   5. Schreiben Sie auch eine kurze Zusam­men­fas­sung über Ihre Er­fahrun­gen bzw.​ etwaige Prob­leme mit dieser Auf­gabe.

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.

3.​ (2 Punk­te) Wen­den Sie Ihren Crawler ein weit­eres Mal an mit der (oder die) gle­ichen Start­seite(n). Pri­or­isieren Sie dies­mal die Seit­en in der Queue nach der Zugehörigkeit zu einer Sprache.​ Wählen Sie eine Sprache aus, auf der Sie den Crawl fokussieren wollen, und be­nutzen Sie Ihr Tool aus Auf­gabe 1 um die Kon­fi­denz der Zuord­nung zu einer Sprache für die gecrawl­ten Seit­en zu bestimmen.​ Sortieren Sie die Liste der of­fe­nen URLs nach der Kon­fi­denz der Seite, auf denen Sie die URL ge­fun­den haben (Besten­suche).
Lassen Sie sich wieder die His­togramme wie in Teilauf­gabe 2.1 und 2.2 aus­geben und ver­gle­ichen Sie mit diesen.​ Betracht­en Sie ins­beson­dere auch die Verteilung über die ge­fun­de­nen Sprachen.

4.​ (2 Punk­te) Schätzen Sie mit der in der Vor­lesung ken­nen­gel­ern­ten Meth­ode die Größe des Webs einer von Ihnen aus­ge­sucht­en Sprache 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). Er­scheint Ihnen die Größe plau­si­bel, ins­beson­dere im Ver­gle­ich zu der unter www.​​worldwidewebsize.​​com geschätzten Gesamt­größe des Webs?

Für eine ko­r­rek­te Abschätzung brauchen Sie auch eine Abschätzung der Größe des sprach­spez­i­fis­chen Index der ver­wen­de­ten Suchmaschine.​ Überlegen Sie sich auch hierfür eine geeignete Meth­ode und beschreiben Sie diese (Vor langer Zeit war es z.​​B.​​ möglich, in Google nach "* *" zu suchen.​).​​

Hin­weise

• Be­denken Sie, daß ein Crawl eine beträchliche Zeit in Anspruch nehmen kann, die Sie auch nicht di­rekt bee­in­flussen können.​ Es ist auch nicht ungewöhn­lich, daß Sie z.​B.​ aufgrund von Prob­le­men und Fehler­bere­ini­gun­gen mehrere Anläufe benötigen.​ Starten Sie de­shalb Ihren er­sten Crawl rechtzeit­ig.
• Beispiele für Du­p­likate auf­grund von Daten­bank-gener­iert­er Seit­en sind z.​B.​ /lehre/ar­beit­en vs. /re­sources/eu­rlex/lehre/ar­beit­en und Aufrufe von /bib­tex/top­ics/sin­gle/31 oder auch /bib­tex/top­ics zu un­ter­schiedlichen Zeit­punk­ten (un­ter­schiedliche pro­cess­ing time). /bib­tex/top­ics/sin­gle/173 und /bib­tex/au­thors/show/3259 sind allerd­ings keine Du­p­likate mehr.​ Bedenken Sie bei Ihrem Ver­fahren auch, daß Sie im schlimm­sten Fall mit allen bere­its gecrawl­ten Seit­en ver­gle­ichen müssen.
• Bei den gängig­sten Such­maschi­nen können Sie üblicher­weise die Sprache für die re­tournierten Web­seit­en fes­tle­gen.
  

Hil­fre­iche Mod­ule:

Hil­fre­iche Mod­ule oder Pro­gramme zum Laden von Web-Seit­en sind z.​B.​ LWP:​:Sim­ple (Perl), url­lib (Python), zum Ex­trahieren von Hy­per­links HTML::LinkEx­tor (Perl), SGML­Pars­er (Beispiel), html­da­ta (Python), Kanon­isieren von URLs URI (Perl), url­pars­er (Python), und generell zum Parsen von Web-Seit­en und Ex­trahieren von Text Beau­ti­ful­Soup, htm­l2­text (Python), HTMLDocument.​getText(), html pars­er, Cobra (Java), html2text.​pl (Perl). Soll­ten Sie mit diesen Tools oder mit selb­st er­stell­ten Parsern Schwierigkeit­en haben, an den Text zu kom­men, so können Sie auch etwas ro­bus­tere ex­terne Pro­gramme ver­suchen wie htm­l2­text oder die textbasierten Web­brows­er links, w3m und linx, die sie zum Ren­dern ver­wen­den können um an­schließend die gener­ierte rohe Tex­taus­gabe zu parsen.