EinfIV-1415-05 - Universität zu Köln

 Documents

 16 views
of 51
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Einführung in die Informationsverarbeitung Teil Thaller Stunde V: Zusammengefügte Bausteine: Google Manfred Thaller, Universität zu Köln Köln 4. Dezember…
Share
Transcript
Einführung in die Informationsverarbeitung Teil Thaller Stunde V: Zusammengefügte Bausteine: Google Manfred Thaller, Universität zu Köln Köln 4. Dezember 2014 Googlesuche „Köln“ - 2014 Googlesuche „Köln“ - 2013 Googlesuche „Köln“ - 2012 Googlesuche „Köln“ - 2011 Googlesuche „Köln“ - 2010 Googlesuche „Köln“ - 2009 Googlesuche „Köln“ - 2008 Google - ein „System“ Crawler Speicher URL Server Anker URL Auflösung Indizierer Repository „Barrels“ Links Lexikon Doc Index Sortieren PageRank Suchen „Ur Google“ Sergey Brin and Lawrence Page: The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proceedings of the seventh World Wide Web Conference (WWW7), Brisbane 1998, also in a special issue of the Journal Computer Networks and ISDN Systems, Volume 30, issues 1-7. http://infolab.stanford.edu/~backrub/google.html Vgl.: http://www.google.com/technology/pigeonrank.html 10 Formalia / Trivia Entwickler: Sergey Brin, Lawrence Page. Name: "Google" Verballhornung von "Googol" ( = 10 100). System verteilt auf viele kooperierende Rechner: Google operates what is probably the world's largest Linux cluster that puts many supercomputing centers to shame. 11 URL Server Crawler URL Server Startet mit Anfangs URL. Liest weitere URLs aus einem Dokumenten-Index. Doc Schickt URLs an Crawler um Seiten zu Index holen. Wichtig: Art der Suche im WWW (Tiefen v. Breitensuche). 12 Crawler Crawler Speicher Holen Web-Seiten. Speichern individuelle Seiten in Speicher-Subsystem. Mehrere Crawler! "Robots Exclusion Protocol" - "Wohlverhalten" 13 Indizierer I Liest Seiten aus dem Repository und dekomprimiert sie. "Parsed" jedes Dokument und verwandelt es in "Treffer", bestehend •aus der Wortform. •der Position innerhalb des Indizierer Repository Dokuments. •einer relativen Fontgröße. •Anzeige der Großschreibung. Treffer sind "fancy" (in URL, Überschrift, Anker Text oder Meta- Tag) oder "plain" (alle anderen Fälle). 14 Indizierer II Verteilt Treffer in "barrels", wobei ein sortierter Index entsteht. Anker Indizierer „Barrels“ Extrahiert Links und speichert Lexikon sie {Start URL, Ziel URL, Text} in Anker Datei. Erzeugt Lexikon Datei. 15 Problem: WordIds = Wortidentifikationsnummern Entstehen, indem die Wortformen sortiert und durchnummeriert werden. Rückverweis: Algorithmen: Laufzeit Beispiel: Sequentielles Suchen 1 Clio 2 Melpomene Suchzeit jedes Namens entspricht 3 Terpsichore Rang in der Liste. 4 Thalia 5 Euterpe 6 Erato Durchschnittliche Suchzeit: n / 2. 7 Urania 8 Polyhymnia Laufzeit steigt mit der zu 9 Kalliope durchsuchenden Anzahl Algorithmen: Laufzeit Beispiel: Binäres Suchen 1 Clio 2 Erato Laufzeit: ? 3 Euterpe 4 Kalliope 5 Melpomene 6 Polyhymnia 7 Terpsichore 8 Thalia 9 Urania Algorithmen: Laufzeit Beispiel: Binäres Suchen – „Thalia“ 1 Clio „Melpomene“ gleich – größer – 2 Erato kleiner „Thalia“? 3 Euterpe „Terpsichore“ gleich – größer – 4 Kalliope kleiner „Thalia“? 5 Melpomene 6 Polyhymnia „Thalia“ gleich – größer – kleiner 7 Terpsichore „Thalia“? 8 Thalia 9 Urania Algorithmen: Laufzeit Beispiel: Binäres Suchen 1 Clio 2 Erato Laufzeit steigt mit Logarithmus der 3 Euterpe zu durchsuchenden Anzahl. 4 Kalliope 5 Melpomene 6 Polyhymnia 7 Terpsichore 8 Thalia 9 Urania Algorithmen: Laufzeit N=1 N=10 N=100 N=1000 1. linear. 1 10 100 1000 2. logarithmisch. 1 3 7 10 3. exponentiell. 1 103 1030 10300 Relevanz? Verteilt Treffer in "barrels", wobei ein sortierter Index entsteht. Anker Indizierer „Barrels“ Extrahiert Links und speichert Lexikon sie {Start URL, Ziel URL, Text} in Anker Datei. Erzeugt Lexikon Datei. 22 Relevanz: ? WordIds = Woridentifikationsnummern Entstehen, indem die Wortformen sortiert und durchnummeriert werden. Erinnerung Crawler Speicher URL Server Anker URL Auflösung Indizierer Repository „Barrels“ Links Lexikon Doc Index Sortieren PageRank Suchen URL Auflösung I Anker URL Auflösung „Barrels“ Links Doc Index 25 URL Auflösung II Liest Anker Datei. Verwandelt relative URLs in absolute. Verwandelt absolute URLs in Dokumenten IDs. Fügt Anker Text in einen vorwärts gerichteten Index ein, zusammen mit den Dokumenten IDs auf die der Anker zeigt. Erzeugt eine Link Datenbank, die Paare von Dokumenten IDs enthält. (Wird für die Errechnung der PageRanks verwendet!) 26 Sortierung Verwandelt einen Index der Dokumenten Ids in einen "invertierten Index", sortiert nach Wort Ids. "Short barrel" - invertierter Index von Treffern in Titel- und Ankertags. "Full barel" - invertierter Index der Bodytags. Enthält Offsets der „Barrels“ Dokumentenposition für jede Wort Id. Sortieren (Nachbarschaftsberechnung / Positionsanzeige.) 27 Page Rank I Kann beschrieben werden als Modell des Verhaltens von Benutzern. Geht von einem "Zufallssurfer" aus, der von einer bestimmten Seite ausgeht und auf Links clickt. Er / Sie geht nie zurück und wird schließlich weitere Zufallsseite auswählen. Der "PageRank" ist die Wahrscheinlichkeit (p), dass der Surfer eine bestimmte Seite besucht. Die Wahrscheinlichkeit, dass BenutzerIn auf Links einer Zufallsseite landet ist 1-p. PageRank 28 Page Rank II Wir nehmen an: •Auf Seite A zeigen die Seiten T1 ... Tn (zitieren sie also). •C(A) ist die Anzahl der Links, die von Seite A ausgehen. •d ist ein empirischer / arbiträrer Dämpfungsfaktor zwischen 0 und 1 (in Google 0.85?). Dann gilt: PR(A) = (1-d) + d ( PR(T1) / C (T1) + ... + PR(Tn)/C(Tn) ) PageRanks stellen eine Wahrscheinlichkeitsverteilung dar; die Summe der PageRanks aller Seiten im Web ist also 1.0. 29 Page Rank III Hoher PageRank kann anzeigen: Dass sehr viele Seiten auf eine Seite zeigen ... ... oder dass eine relativ kleine Anzahl von Seiten mit hohem PageRank auf diese Seite zeigen. 30 Erinnerung Crawler Speicher URL Server Anker URL Auflösung Indizierer Repository „Barrels“ Links Lexikon Doc Index Sortieren PageRank Suchen Repository Voller (HTML) Text jeder Webseite. Seiten werden komprimiert gespeichert (ZLIB). Format: •Dokumenten Id. •Dokumentenlänge. •URL des Dokuments. •Inhalt des Dokuments. 32 Anker Beschreibung der Verweise in den Seiten {Start URL, Ziel URL, Text} Laut Google oft genauere Beschreibung der Seiten, als die Seiten selbst. Können auch nicht-Texte berücksichtigen. Problem: Tote Links ... 33 Links Datenbank aller Paare von Dokumenten Ids. Basis aller PageRank Berechnungen. 34 Doc Index Datenbank aller verarbeiteten Dokumente (Web Seiten) Organisiert als ISAM Datei. (Indexed sequential access mode.) Geordnet nach DokumentenId. Jeder Eintrag enthält: •Status des Dokuments. •Prüfsumme des Dokuments. •Statistiken zum Dokument. Angabe ob Seite von Crawlern schon durchsucht wurde. Sonst Verweis auf Liste abzuarbeitender URLs. 35 Lexikon 36 Zur Erinnerung: „Zeiger“ Diagrammatische Darstellung: A B „Zeiger“: Ein Speicherinhalt eines Rechners verweist auf einen anderen. Datenstruktur im Speicher Speicher als „karierte Zeile“ 0 1 2 3 4 5 6 7 8 9 10 11 Datenstruktur im Speicher Zahl „14123“ in Bytes 0 bis 1 Zahl „22445“ in Bytes 10 bis 11 14123 22445 0 1 2 3 4 5 6 7 8 9 10 11 Datenstruktur im Speicher Zeichen „a“ in Byte 0 Zeichen „q“ in Byte 11 a q 0 1 2 3 4 5 6 7 8 9 10 11 Datenstruktur im Speicher Zeiger in Bytes 0 bis 1 verweist auf Speicherblock, enthaltend „xy“, beginnend in Byte 10 10 x y 0 1 2 3 4 5 6 7 8 9 10 11 Zeiger graphisch Zeiger in Bytes 0 bis 1 verweist auf Speicherblock, enthaltend „xy“, beginnend in Byte 10. x y 0 1 2 3 4 5 6 7 8 9 10 11 Zeiger graphisch Zeiger verweist von einem Datenblock auf einen anderen. * ergo: Lexikon 44 Barrels I Datenbank des Inhalts aller verarbeiteten Dokumente (Web Seiten) Beginnt mit einem Index von Dokumenten Ids, wird danach zu einem Index der Wort IDs sortiert. Die Suchmaschine sucht zuerst in den "short barrels" nach Treffern (Titel und Anker), erst danach in den "full barrels". 45 Barrels II 46 Google - ein „System“ Crawler Speicher URL Server Anker URL Auflösung Indizierer Repository „Barrels“ Links Lexikon Doc Index Sortieren PageRank Suchen Suche I Besonderheiten der Googlesuche: Google analysiert nicht nur die Wortformen, sondern auch ihren (auch graphischen) Kontext. Jede Trefferliste enthält Informationen über die Position, den Schrifttyp und die Großschreibung. Zudem wird zwischen "fancy" und "plain" unterschieden - und der PageRank wird berücksichtigt. Ausgewogenheit zwischen diesen Faktoren. 48 Suche II – Abfragebearbeitung 1. Abfrage "parsen". 2. Worte in WortIds verwandeln. 3. "Short barrel" auf Anfang der Dokumentenliste für jedes Wort der Abfrage positionieren. 4. Dokumentenliste durchsuchen, bis es Dokument gibt, dass alle Suchterme enthält. 5. Rang dieses Dokuments berechnen, relativ zu den anderen, die die Bedingungen erfüllen. 6. Wenn wir mit der Bearbeitung der "short barrels" fertig sind, wiederhole Schritt 3 ff. sinngemäß für die "full barrels". 7. Wenn wir noch nicht am Ende der Dokumentenliste sind, gehe zu Schritt 4. 8. Gefundene Dokumente nach Rang sortieren und n beste mitteilen. 49 Suche III – Ranking, Einzelwort 1. Trefferliste erstellen. 2. Jedem Treffer Typ {Überschrift, Anker, URL, Großer Font, Kleiner Font ...}, mit spezifischem Typwert, zuweisen. 3. Vector der Typen-Gewichte in der Reihenfolge der Typen erzeugen. 4. Typen zählen und Häufigkeiten in Häufigkeitsgewichtungen verwandeln. 5. Häufigkeitsgewichtung normalisieren, am Anfang linear, dann abnehmend. 6. Gewichtungsrang entspricht dem Skalarprodukt aus dem Vektor der Typengewichte mit dem Vektor der Häufigkeitsgewichte. 7. Kombination aus Gewichtungsrang und PageRank ergibt endgültigen Rang des Dokuments. 50 Danke für heute! 51
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks