Proseminar: Content Management
Suchmaschinen im World Wide Web
Auf der Suche nach relevanten Informationen im World Wide Web kann der Mensch auf zwei verschiedene Hilfsmittel zurückgreifen: Themenkataloge, die von Redaktionen zusammengestellte, bewertete und hierarchisch-geordnete Link-Sammlungen darstellen; und Suchmaschinen, welche im Vorfeld autonom das WWW durchlaufen, dabei einen riesigen Index aller gefundenen Seiten erstellen und somit eine Stichwortsuche auf diesem ermöglichen.In der Theorie läßt sich eine Suchmaschine in mehrere Komponenten aufteilen, nämlich in URL Server, Crawler, Parser und Store Server die zur Erstellung des Indexes dienen.
Der Index wiederum läßt sich in die Datenstrukturen Lexicon, Hit Lists und Repository unterteilen. Der Searcher schließlich übernimmt die Auswertung der Suchanfrage.
In der Praxis unterscheiden sich Suchmaschinen jedoch stark durch mehrere, verschiedenartige Ansätze, die ihren Ursprung im Information Retrieval begründen. Besonderes Augenmerk wird hierbei auf die Techniken zum Durchlaufen des WWW, die Steigerung der Recall- und der Precision-Rate und auf die Wartung des Indexes gelegt.
Im Einzelnen nun etwas genauer:
Das World Wide Web ist eine Menge von gerichteten Graphen wobei die Knoten Seiten und die Zeiger Links repräsentieren.
Themenkataloge, wie z.B. www.web.de/suchen oder de.yahoo.com, haben den Vorteil, daß die enthaltenen Seiten, wegen der redaktionellen Bearbeitung, von hoher Qualität sind und eine klar gegliederte Einteilung der Themenbereiche durch eine Baumstruktur von Kategorien und Unterkategorien eine eindeutige Navigation und Suche ermöglicht.
Nachteilig ist, daß nur ein geringer Prozentsatz des gesamten WWW erfaßt wird, sowie daß das Wachstum eines solchen Katalogs nicht mit dem Wachstum des WWW Mithalten kann. Das Wachstum des World Wide Web wird jährlich unter www.isc.org analysiert.
Suchmaschinen, wie z.B. www.google.de, www.altavista.com oder www.northernlight.com, haben im Vergleich zu Katalogen den Vorteil, daß sie mehrere Millionen Seiten indiziert haben. Die Probleme hierbei sind, daß es häufig zu viele oder gar keine relevanten Suchergebnisse gibt (schlechte Ranking-Algorithmen), das Tote Links in den Suchergebnissen auftauchen und das die Mächtigkeit der Anfragesprache nicht ausreichend ist.
Meta-Suchmaschinen, wie z.B. www.metacrawler.com oder www.metager.de, senden die Suchanfrage an mehrere normale Suchmaschinen und bereiten dann die zurückgegebenen Seiten der Relevanz nach geordnet auf.
Komponenten einer Suchmaschine:
Der URL Server enthält und verwaltet die URLs (Uniform Ressource Locators, z.B. http://www.kein-plan.de/) die noch nicht indiziert wurden und reicht diese an den Crawler weiter. (Hier wird entschieden ob eine Breiten- oder Tiefensuche für das Durchlaufen des WWW angewandt wird) Dem Problem, das auf manche Seiten kein Link verweist, wird mit der Möglichkeit der manuellen Eingabe der URL, Abhilfe geschaffen.Der Crawler (auch Robot oder Web-Spider genannt) übersetzt die URL, die er vom URL Server zugespielt bekommt, mit Hilfe des DNS (Domain Name System) in deren eindeutige IP-Adresse (z.B. entspricht die IP 216.239.37.100 der URL www.google.de) und holt mittels des HTTP-GET-Kommandos die entsprechende Seite, die dann an den Parser weitergereicht wird.
Der Parser erstellt aus jeder, vom Crawler überreichten Seite einen Ableitungsbaum und gibt diesen an den Store Server weiter. (Problem: Der Parser muß eine Vielzahl von HTML-Dialekten verstehen und sehr fehlertolerant agieren können.)
Der Store Server versorgt nun den URL Server mit den neuen Links aus dem Ableitungsbaum vom Parser. Er extrahiert und speichert alle später durchsuchbaren Informationen im Repository. Des weiteren wird der Seitentext nach Worten durchsucht (und bei Bedarf das Lexicon mit diesen neuen Wörtern erweitert) und in den Hit Lists vermerkt wie oft das jeweilige Wort in der Seite vorkommt.
Datenstrukturen einer Suchmaschine:
Das Lexicon enthält nun alle suchbaren Wörter, die in einer effizienten Datenstruktur (z.B. Hashtabelle) abgelegt sind. Jedes Wort hat Zeiger auf die entsprechende Hit List.Die Hit List(s) enthält zu jedem Wort (des Lexicons) eine Menge von Zeigern die auf die Informationen im Repository, in denen es vorkommt, verweisen. Zusätzlich wird vermerkt wie oft das Wort im Titel oder in Überschriften vorkommt.
Das Repository ist der Speicherort für Informationen der indizierten Seiten, die zur Ausgabe benötigt werden. Wegen der enormen Datenmenge werden u.a. Titel, META-Elemente, die ersten 20 Zeilen (oder sogar Volltext) komprimiert gespeichert.
Der Searcher stellt einen Webserver, der als Frontend für die gesamte Datenbank fungiert und der als Eingabemaske für die Suchanfrage dient, dar.
Aus Lexicon und Hit Lists wird die Suchergebnis-Menge erstellt, die dann mittels Ranking-Algorithmen sortiert wird. Das höchste Ranking bekommen i. a. Dokumente, die die meisten Suchwörter am häufigsten beinhalten.
Zurückgegeben werden dann die relevanten Links, die mit Zusatzinformationen aus dem Repository (z.B. Titel, META-Description, Textausschnitt) angereichert sind.
- Information Retrieval ist das gezielte Auffinden von Informationen in bereits erstellten und gespeicherten Dokumenten.
Um die Güte zu bewerten, benutzt man zwei häufig verwendete Maßstäbe, nämlich die Recall-Rate, die das Verhältnis der Anzahl der zurückgegebenen, relevanten Dokumente zur Gesamtzahl aller relevanten Dokumente widerspiegelt;
sowie die Precision-Rate, die das Verhältnis der Anzahl der zurückgegebenen, relevanten Dokumente zur Gesamtzahl aller zurückgegebenen Dokumente bezeichnet. (Practical Precision heißt hierbei, daß der Benutzer sich in der Regel nur die ersten 10 bis 20 zurückgegebenen Links anschaut und den Rest ignoriert.)
Techniken zum Durchlaufen des WWW sind die folgenden:
Breitensuche bedeutet eine Indizierung der direkten Nachbarschaft. Verfolgt werden alle Links der ersten Seite, dann alle der zweiten Seite und so fort (FIFO-Queue).Tiefensuche meint, daß der gesamte Graph auf den der erste Link der ersten Seite zeigt, erforscht wird, bevor der nächste Link verfolgt wird (Stack).
Backlink Count ist die Technik, mit welcher sich der URL Server merkt auf welche URLS wie viele Links existieren. Somit werden also populäre Seiten bevorzugt indiziert (in Analogie zum citation index von wissenschaftliche Veröffentlichungen).
Page Rank stellt eine Erweiterung des Backlink Count dar und wurde erstmals von Google verwirklicht. Seiten mit einem hohen PageRank-Wert haben höheres Gewicht als Seiten mit niedrigem Wert. Zum Beispiel ist eine Seite wichtiger auf die Yahoo einen Link hat, als eine Seite , auf die eine private Homepage zeigt.
Ranking-Verfahren (bzw Algorithmen) allgemeinerer Natur sind z.B. die Anzahl von übereinstimmenden Worten, die Häufigkeit des Vorkommens von Suchbegriffen, die Übereinstimmung des Domain-Namens mit dem Suchwort, das Title-Tag, Überschriften, META-Content und META-Keywords und der Dokumentenanfang.
Techniken zur Steigerung der Recall-Rate sind die folgenden:
Eine Indexvergrößerung liefert potentiell eine größere Recall-Rate. Jedoch setzt die Architektur der Datenbank und die Skalierbarkeit der selbigen Grenzen.Natural Language Processing bedeutet die Verwendung von Stemming und/oder eines Thesaurus.
Stemming heißt die automatische Verwendung Wildcards bzw. die Reduzierung von Wörtern auf deren Grundform. Dabei entsteht jedoch die Gefahr der Mehrdeutigkeit (inform* = informal oder information?) was wiederum die Precision-Rate senkt.
Ein Thesaurus fügt dem Suchbegriff entsprechend Synonyme zur Suchanfrage hinzu. Wegen Doppelbedeutungen wirkt sich das u.U. auch senkend auf die Precision-Rate aus (Ist ein Virus ein Computervirus oder ein Krankheitserreger?).
Die Art des Indexes spielt auch eine nicht zu vernachlässigende Rolle. Da nur 0,03% aller Seiten mehr als 100 verschiedene, bedeutungstragende Wörter benutzen, wurde früher hauptsächlich die Vektordarstellung verwendet. Wegen der inhomogenen Struktur des WWW und der steigenden Leistung der Hardware wird heute aber immer mehr zur Volltextrepräsentation übergegangen.
Techniken zur Erhöhung der Precision-Rate sind:
Die Mächtigkeit der Anfragesprache und damit die intensive Ausnutzung durch den Suchenden ist wohl der Kernpunkt einer erfolgreichen Suche im WWW.Im Allgemeinen lassen sich Boolsche Ausdrücke (AND, OR, NOT und Klammern), Existenzbedingungen (+, -), Wildcards (auch Joker oder Platzhalter genannt und mit einem * gekennzeichnet), phrasierte Ausdrücke in Anführungszeichen ('Bastian Baltasar Bux'), Wortabstandbedingungen (Schneewitchen NEAR Zwerge), Suche innerhalb von HTML-Elementen (TITLE, H1, etc.) und Beschränkungen auf bestimmte Sprachen oder eine ganz bestimmtes Datum, verwenden.
Nachbearbeitung und Clustering heißt, daß die Suchergebnisse mit bekannten, relevanten Seiten abgeglichen werden. Es erfolgt eine semantische Klassifizierung der Suchergebnisse in Kategorien, was aufwendig aber sehr effektiv ist.
Auch eine Optimierung der Ranking-Algorithmen (vgl. Backlink Count und Page Rank) ist natürlich eine effiziente Methode zur Steigerung der Precision-Rate.
Methoden zur Wartung des Indexes sind die folgenden:
Die Updatehäufigkeit ist wohl das A und O der Wartung des Indexes. Da aber eine regelmäßige Neu-Indizierung alles Seiten wegen der riesigen Anzahl unmöglich ist, wird mittels Backlink Count und Page Rank die wichtigen Seiten häufiger aktualisiert als unwichtigere. Auch werden gerne diejenigen Seiten bevorzugt, die häufiger in den Ergebnislisten auftauchen.Das Problem das sich noch stellt ist die Behandlung von Toten Links. Ca. 10% des Indexes einer Suchmaschine sind tote Links, also Links die ins Leere führen, da die Adresse sich geändert hat oder die entsprechende Seite vom Netz genommen wurde. Eine Lösung wäre ein Erhöhung der Aktualisierungsfrequenz. Bei Volltext-Indexes entsteht zudem der Vorteil, daß der Zugriff auf das von der Suchmaschine gespeicherte Dokument möglich wird obwohl es temporär vielleicht nicht erreichbar ist (vgl. Cache bei Google).
Fazit:
Manche Suchmaschinen bieten (teils zur Abgrenzung von anderen Suchmaschinen) nur einzelne Techniken (im Bezug auf die Mächtigkeit der Anfragesprache z.B.) an. Die enorme Größe und das Wachstum des WWW rückt die Skalierbarkeit immer mehr in den Vordergrund. Auch bringt die Kommerzialisierung falsche Prioritäten mit sich (z.B. Werbung :'Wir haben 300 Millionen Seiten indiziert!' - Recall ist viel größer als Precision).Meta-Suchmaschinen, die über mehrere Suchmaschinen suchen, können meist nicht die Vorteile der jeweiligen Anfragesprache ausnutzen (einziger Vorteil ist ein höhere Netzabdeckung).
Trends:
Meta-Suchmaschinen wie z.B. Metacrawler verwenden eine effiziente Nachbearbeitung, wie z.B. Ergebnis-Merging, Doubletten-Eliminierung und Verwendung von Operatoren.Google bietet ein automatisches Übersetzen einer fremdsprachigen Seite in die Muttersprache an. Auch lassen sich bei weitem nicht nur (Text-) Dokumente suchen. Eine Erweiterung des Suchgebietes auf Bilder, Tonmaterial und Filme zeigt z.B. Altavista.
Literatur-Links zu Suchmaschinen-Technologien:
The anatomy of a large-scale hypertextual web search engine:citeseer.nj.nec.com/brin98anatomy.html
Suchmaschinen Frequently Asked Questions:
www.smkl.de/suchmaschinen/
Web Robots Page (Robots Exclusion Standard):
www.robotstxt.org/wc/robots.html
Suchfibel.de - Anleitung zur erfolgreichen Suche im Internet:
www.suchfibel.de/
Recherchefibel.de - Alles Wissenswerte rund um die Online-Recherche:
www.recherchefibel.de/
Schatzsucher - Die Internetsuchmaschinen der Zukunft:
www.heise.de/ct/98/13/178/
Internet Software Consortium - Domain Survey:
www.isc.org/ds/
TeamOne - Metaangaben für Suchdienste und Browser:
www.teamone.de/selfhtml/tcbc.htm
Search Engine Watch - Glossary, Report, Search Assistance Features:
www.searchenginewatch.com/
Glossary for Information Retrieval:
www.cs.jhu.edu/~weiss/glossary.html
SPHINX - a framework for creating personal, site-specific web crawlers:
decweb.ethz.ch/WWW7/1875/com1875.htm
The effect of centroid size on precision and recall of web search engines:
ibm.nsysu.edu.tw/INET98/1x/1x_8.htm
Efficient Crawling through URL ordering:
www7.scu.edu.au/programme/fullpapers/1919/com1919.htm
A simple web site search programm - just 224 lines of pearl 5:
www.boutell.com/search/
Suchmaschinen im Internet:
www.ib.hu-berlin.de/~kumlau/handreichungen/h58/
Allgemeine Suchmaschinenen:
Google - Bringt Ordnung ins Web:www.google.de/
AltaVista - Sucht auch nach Bildern, Tonmaterial und Filmen:
www.altavista.com/
NorthernLight:
www.northernlight.com/
Themenkataloge:
Suchen mit Web.de:www.web.de/suchen/
Yahoo Deutschland:
de.yahoo.com/
Meta-Suchmaschinen:
MetaCrawler:www.metacrawler.com
MetaGer - RRZN Hannover:
www.metager.de
Spezielle Suchmaschinen:
Open Directory Project:www.dmoz.org/
Sucharchiv - Suchmaschine für spezialisierte Suchmaschinen:
www.sucharchiv.com/
Suchmaschinen, Verzeichnisse und andere Nachschlagewerke:
www.heise.de/ct/tipsundtricks/cttt7.shtml
Vita:
Florian Ermann war Informatik-Student an der Universität Erlangen-Nürnberg.
Seine Spezialgebiete in welchen er gerade forscht sind nicht existent. Er wurde 1978 ins Leben berufen und fristet seitdem sein Dasein auf Gaja, ein kleiner, in seinen letzten Millionen Jahren liegender, Planet in einer Ecke der Milchstraße. ;-)