Suchverfahren von Internetbrowsern

Inhaltsverzeichnis

Abbildungsverzeichnis

Einleitung

I. Stolpersteine für Suchmaschinen

II. Grundtypen der WWW Suchdienste
II.I Webkataloge
II.II (Indexbasierte) Suchmaschinen
II.III Meta Suchmaschinen
II.IV Payed Listing Suchmaschinen

III. Suchverfahren

IV. Gewichtungsverfahren im Einzelnen
IV.I Relative Worthäufigkeit
IV.II Inverse Dokumentenhäufigkeit
IV.III PageRank
IV.IV Vektorraummodell
IV.V WISERank
IV.VI Cluster Verfahren
IV.VI ExpertRank

V. Google Maske - GoMa

VI. Feldversuche
VI.I Mit Eigenschaften von URL's: Tiefe, Länge, Position des Suchwortes
VI.II Mit HTML spezifisches: Description-, und Titeltag
VI.III Webseiteninhalt: Suchworthäufigkeit
VI.IV PageRank spezifisch: Back Links

Literaturangabe

Abbildungsverzeichnis

Abb 3.1 Komponenten eines Webrobot-Systems, Quelle: Michael Glöggler, Suchmaschinen im Internet.

Abb. 5.1 GoMa, Quelle: GoMa

Abb. 6.1 Rangposition auf Linktiefe. Quelle: GoMa

Abb. 6.2 Rangpositionen auf Linklänge, Quelle:GoMa

Abb. 6.3 Absolute des Suchwortes innerhalb des URLs, Quelle:GoMa

Abb. 6.4 Absolute Position des Suchwortes innerhalb des Descriptiontags auf Rangpositionen, Quelle:GoMa

Abb. 6.5 Position des Suchwortes innerhalb des Titeltags auf Rangpositionen, Quelle:GoMa

Abb. 6.6 Suchwort Vorkommen auf Rangpositionen, Quelle:GoMa Abb. 6.6 Back Links auf Rangpositionen, Quelle:GoMa

Einleitung

In dieser Hausarbeit werde ich verschiedene Arten von Webbrowser sowie unterschiedliche Such-, und Gewichtungsverfahren vorstellen. Verschiedene Methoden um die Relevanz von Dokumenten im Internet zu berechnen und die daraus resultierende Reihenfolge von Ergebnissen werden diskutiert. Ein Schwerpunkt bildet PageRank, das Gewichtungsverfahren welches zum ersten-mal von Google eingeführt worden ist und heutzutage in anderen Browsern auch in ähnlicherweise zum Einsatz kommt. Am Ende wird eine Google Maske vorgestellt mit der man die Ergebnisse einer Anfrage speichern, und in einem weiteren Schritt diese Ergebnisse graphisch darstellen kann. Im Folgenden wird das Wort Suchmaschine nur dann verwendet wenn es sich tatsächlich um eine eigentliche Indexbasierte Suchmaschine handelt. Ansonsten wird der Begriff Webbrowser oder Suchdienst benutzt.

I. Stolpersteine für Suchmaschinen

Die Internet Suchdienste müssen mit vielen Hindernissen fertig werden. Eine dieser Hindernisse ist das so genannte “Invisible Web”. Dies ist der Teil des Internets der von keinem normalen Browser indexiert wird. Dabei handelt es sich um dynamische Internet Seiten wie sie z.B. von Datenbankensystemen wie Oracle automatisch erzeugt und nur als Antwort von Abfragen erstellt werden. Es gibt kaum ein anderes Medium was so dynamisch und so schnell wächst wie das Internet. Die Anzahl der im Internet existierenden Dokumente wird auf 11,5 Milliarden¹ geschätzt. Davon sind nach eigenen Aussagen mehr als 8 Milliarden² in Google indiziert. Die Dokumentenanzahl wächst rasant und wird als Trend angesehen, d.h. dass es sich in Zukunft in ähnlicherweise weiter entwickeln wird. Wie kann ein Internet Browser auf neue bzw. gerade aktualisierte Dokumente reagieren? Damit ein Dokument überhaupt gefunden wird, muss es abhängig von der Natur des jeweiligen Suchdienstes, entweder angemeldet sein oder eine Software muss es “entdecken”. Damit das Dokument von der Software gefunden werden kann muss es verlinkt sein. Bei manchen Webbrowserarten werden nichtVerlinkte Dokumente gar nicht in dem Ergebnis einer Suche auftauchen. Bei Google z.B. wird eine Unverlinkte Seite in keiner Suche zu finden sein. Der Grund dafür ist dass Google hauptsächlich mit der Linkstruktur arbeitet. Wo es aber keinen Link auf eine Seite gibt, kann auch kein Relevanzberechnungsverfahren zum Einsatz kommen.

Im WWW gibt es nicht wenige Stellen wo Allgemeine Suchdienste³ mit Software Tools zur Erschließung des Internets(WebRobots) gar nicht daran kommen. Dazu gehören Benutzereingaben generierte Dokumente und Zugangs geschützte Bereiche. Dann gibt es auch Technologien die es unmöglich machen dass WebRobots damit arbeiten können, zum Beispiel eine Seite die nur Graphiken enthält, oder genauer gesagt dass der Text und die Links sich auch in Graphiken befinden.

II Grundtypen der WWW-Suchdienste:

Die im Internet gängigen verschiedenen Suchdienste werden in 4 Grundtypen unterteilt. Als Unterscheidungskriterium dienen: die Art wie sie ihren Datenbestand erzeugen, ihn verwalten und wie sie ein URL eine Gewichtung als antwort auf eine Suchanfrage geben.

II.I Webkataloge (Katalogbasierte Suchmaschinen)

Bei einem Webkatalog handelt es sich um einen Suchdienst dessen Datenbestand von menschlichen Redakteuren zusammengestellt wird, welche einen thematisch gegliederten Suchkatalog zusammenstellen. Web-Seiten werden dazu manuell geprüft redaktionell bewertet und verworfen oder für Aufnahme in den Katalog akzeptiert. Die Suche erfolgt dann durch blättern im Suchkatalog. Dieser Vorgang ist sehr aufwendig und kostenintensiv. Die intellektuelle Bewertung der Webseiten durch Menschen bewirkt eine Erhöhung der Qualität der Suchergebnisse. Der große Nachteil von Webkatalogen ist, dass sie auf einen relativ kleinen Datenbestand zurückgreift da Webseiten nur erscheinen nachdem sie angemeldet werden. Dadurch verlieren wir viele Treffer die unter Umständen wichtig sind. In anderen Wörtern, sinkt bei den Webkatalogen die Vollständigkeit (recall) während die Genauigkeit (Precision) steigt. Ein anderer Nachteil von Webkatalogen ist die Aktualität. In einem so dynamischen Medium wie das WWW, ist es sehr wichtig, dass aktualisierte Seiten auch geprüft werden. Es würde wenig Sinn machen dass man Seiten besucht die seit Jahren nicht mehr aktualisiert worden sind und bei welchen die Links in nicht existierende Seiten führen. Ein Webkatalog verfügt über keine Software die durch das Internet durchgeht (Webrobot⁴ ) um neue Webseiten zu erschließen. Sollte der Eigentümer eines Internetportales sich dafür interessieren in einem Webkatalog aufzutauchen, muss er einen entsprechenden Antrag bei den einzelnen Webkatalogen erstellen. Dieser wird zusammen mit dem Inhalt der Webseite von Redakteuren analisiert, und dann fällt die Entscheidung ob und zu welcher Kategorie diese neue Webseite hinzugefügt wird. Die in Deutschland bekanntesten Webkataloge sind web.de und yahoo.com.

II.II (Indexbasierte) Suchmaschinen

Suchmaschinen unterscheiden sich grundsätzlich gegen Webkataloge in dem die Hauptfunktionen vollautomatisch funktionieren.

Die vier Kernfunktionen von Suchmaschinen sind:

1. Datenbeschaffung.

Die Datenbeschaffung erfolgt durch den Einsatz von speziellen, autonom arbeitendenSoftware-Werkzeugen sog. WebRobots. Diese können automatisch neue Webseiten und Dokumente im WWW ausfindig machen. Bereits im Datenbestand vorhandene Dokumente werden periodisch auf Konsistenz bzw. Veränderungen überprüft.

2. Dokumentenananalyse und -bewertung.

Die Dokumentenananalyse und -bewertung wird durch vollständige automatisierte Softwaretools so genannte Information Retrieval Systeme die eine Analyse und inhaltliche Bewertung von Dokumenten vornehmen.

3. Aufbau und Verwaltung von Datenstrukturen.

Dafür werden auch automatische Softwaretools eingesetzt die über die Aufnahme und den Inhaltlichen Schwerpunkt eines Dokuments entscheiden. Information Retrieval Systeme ermitteln inhaltliche Schwerpunkte der untersuchten Dokumente und legen die analysierten Dokumente entsprechend der relevanten Kategorien (Schlüsselworte) innerhalb einer Datenbank ab. Einzelnen Dokumenten wird entsprechend ihrer Relevanz bzgl. der darin behandelten Themen eine Gewichtung zugewiesen. Verfahren zur Erstellung eines durchsuchbaren Datenbestandes werden als Indexierung bezeichnet.

4. Suchanfrage mit der Berechnung von Relevanzwerten.

Bei Suchanfragen reichen Relevanzbewertungverfahren aus um eine genügend große Anzahl von Relevanten Dokumenten zurück zu geben.

Der große Vorteil von Suchmaschinen ist dass die automatische Datenbeschaffung einen sehr aktuellen und vollständigen Datenbestand ermöglicht. Dafür ist die Zielgenauigkeit abhängig von den zur Relevanzbewertung eingesetzten Algorithmen. Im Rahmen dieser Arbeit habe ich festgestellt dass bei Google diese Algorithmen zu verschiedenen Ergebnissen führen können wenn auch die Anfragen dieselben sind. Auch die Anzahl der Ergebnisse variiert um bis zu 20%. Die automatische Relevanzbewertung führt zu qualitativ minderwertigeren Ergebnissen. Die bekanntesten Suchmaschinen im deutschsprachigem Raum sind: Google, Altavista und Lycos.

II.III Meta-Suchmaschinen

Metasuchmaschinen geben die Anfrage an verschiedene Webkataloge und Suchmaschinen weiter worauf hin die Ergebnisse in einem einheitlichen Format angezeigt werden. Die bekannteste Suchmaschine dieser Kategorie ist MetaCrawler. MetaCrawler bezieht bei der Suche die Ergebnisse von Führenden Suchunternehmen mit ein, darunter: Google, FAST, Overture, About, Ask Jeeves, FindWhat, LookSmart, Inktomi und SearchHippo. Eine andere Metamaschine ist MetaGer. Bei dieser kann der Benutzer sogar selbst bestimmen an welche andere Webkataloge und Suchmaschinen, die eigene Anfrage gesendet wird.

Ablauf einer Suchabfrage bei einer Meta-Suchmaschine⁵:

1. Annahme einer Suchabfrage über eigene Benutzer-Schnittstelle
2. Generierung von Suchabfragen für die abzufragenden Suchdienste
3. Versenden der Suchabfragen via HTTP
4. Warten und Sammeln der Zurückgelieferten Suchergebnisse
5. Analyse der Suchergebnisse, Eliminierung von Duplikaten, Bilden einer Rangreihenfolge der Suchergebnisse
6. Darstellung der zusammengeführten Suchergebnisse

II.IV Payed Placement-Suchmaschinen

Hierbei handelt es sich um gekaufte Rangpositionen, die bei manchen Suchmaschinen und Webkataloge an einem dafür vorgesehenen Platz auftauchen. Im Grunde genommen beruhen diese Maschinen auf dem Verkauf von Positionen gegen Bezahlung. Rangpositionen haben keine festen Preise. Diese werden in einem Höchstgebot verfahren festgelegt. Das Kriterium hierfür ist der so genannte Price-Per-Click (PPC). Jeder Anbieter kennt die Höhe des PPC den die Wettbewerber an die Suchmaschine Zahlen. Es ist möglich zu entscheiden ob man die erste Position haben will in dem man einfach einen Höheren PPC zahlt als alle anderen Konkurrenten. Bei Google funktioniert es nicht ganz nach diesem Prinzip. Die Rangposition ergibt sich aus einer Kombination des PPC und der Anzahl von erfolgten Klicks (Click-Through-Rate). Sollten man die erste Position besitzen und die Anzahl von erfolgten Clicks nicht hoch genug sein, wird dies dazu führen, dass man weiter unten in der Reihenfolge landet.

III. Suchverfahren

Die Art und Weise wie Suchmaschinen und Webkataloge sich mit neuen Seiten anreichern ist gerade der Hauptunterscheidungspunkt zwischen den beiden. Während Bei Webkatalogen menschliche Intelligenz aktiv die Hauptarbeit übernimmt, setzten Suchmaschinen Webrobots ein. Diese sind Zuständig für die konstante Erschließung von neuen oder veränderten Dokumenten im Internet. Sie besuchen alle Dokumente in Abständen um zu überprüfen ob sie noch existieren und ob sie verändert worden sind. Falls im letzteren Fall ein neuer Link gefunden wird, wird diese gespeichert und für die Aufnahmen in den Datenbestand erfasst. Um einen automatischen Aufbau und Pflege des Datenbestandes einer Suchmaschine sowie der Beantwortung von Relevanz orientierten Suchanfragen sicherzustellen, werden folgende Module Verwendet: Webrobot System, Information Retrival System und Query-Processor. Damit eine Webseite im Ergebnis einer Suchmaschine auftaucht, muss sie zuerst gefunden werden. Dies ist die Aufgabe vom Webrobot. Er besucht seine schon bekannten Webseiten um zu überprüfen, ob sie noch funktionieren und aktuell sind. Sollte er dabei einen Verweis auf eine unbekannten Webseite finden, speichert er das neue URL um es irgendwann zu besuchen. Jede Domain hat die Möglichkeit diesen Robots mitzuteilen ob seine Besuche für die Erschließung der Domain erwünscht sind oder nicht. Dies wird in jeder HTML Seite unter einem Metatag namens Robots oder in eine Datei im Root-verzeichnis Namens “Robots.txt” eingestellt. Nur nicht alle Robots halten sich daran an das was ihnen gesagt wird. Ein Webrobot System teilt sich in folgenden Komponenten: Gatherer, Loader, URL Datenbank und Checker. Der Gatherer bekommt URL's, besucht sie und speichert die Dokumente. Der Loader holt die URL's von der Datenbank und organisiert die auszuführenden Aufträge. Die URL Datenbank verwaltet die gespeicherten URL's. Der Checker wendet unterschiedliche Filter an.

Abbildung in dieser Leseprobe nicht enthalten

Abb 3.1 Komponenten eines Webrobot-Systems, Quelle: Michael Glöggler, Suchmaschinen im Internet.

Das Information Retrival System durchsucht die vom Webrobot System gespeicherte Text Dateien, nach verwendbare Informationen die für die Relevanz Berechnung wichtig sein könnten. Der Query Processor ist der Teil des ganzen Systems der die Dokumente im Bestand durchsucht und sie in eine relevante Reihenfolge zurückgibt.

IV. Gewichtungsverfahren

Ein besonderer Punkt bezüglich Webbrowsern ist die Tatsache dass sie alle Dokumente die sie kennen in eine Reihenfolge bringen die auch Sinn macht. Nicht zu vernachlässigen ist auch die Wichtigkeit einer Ergebnisreihenfolge die tatsächlich die relevantesten Treffer zuerst anzeigt. Jede Suchmaschine wendet verschiedene Verfahren für die Relevanzberchnung an. Im Folgenden werden die prominentesten Möglichkeiten erklärt.

[...]

¹ Nach einem Paper von Gulli und Signorini, http://www.cs.uiowa.edu/~asignori/web-size/, 2005

² http://www.google.de/intl/de/why_use.html

³ z.B.: A9, Accoona, Alexa, Ask, Baidu, Exalead, Gigablast, Google, HotBot, Lexxe, Lycos, Majestic 12, Mozdex, MSN Search, Netcraft. Rambler, Wisenut, Yahoo, Yandex, Blingo

⁴ Auch Spider oder Crawler gennant

⁵ Dr. rer. nat. Harald Sack, in: http://www.minet.uni-jena.de/~sack/WS0405/materialien/webtechnologien-07sm.pdf