Untersuchung und Bewertung
Nachdem wir jetzt ein ganzes Semester an der Suchmaschine gebastelt haben, ist
es Zeit für eine kritische Bewertung. Dies soll hiermit geschehen.
Bevor auf die einzelnen Teile der Suchmaschine detailierter eingegangen wird, kurz
einige übergreifende Beobachtungen:
- Betrachtet man Precission und Recall als alleinige Qualitätsmassstäbe, so
hängt die Qualität einer Suchmaschine ausschliesslich von der Qualität des
Stemmings und der Ranking-Funktion ab. Alles andere (Index, etc.) ist nur Beiwerk.
- Geschwindigkeit wird nicht im Index gewonnen oder verloren, sondern in der
Auswertung der Suchanfrage und bei der Verknüpfung der Ergebnisse. Beim nächsten
Mal sollte daher auf diesen Aspekt erheblich mehr Gewicht gelegt werden. Die Fragestellung
dabei wäre: Wie muss ein Index aussehen, damit UND und ODER Verknüpfungen von
Postinglisten möglichst optimal unterstützt werden?
Das Modell
Das Modell der Suchmaschine basiert auf voneinander entkoppeltem Indexaufbau und Suche.
Dieses Modell ist vor allem während der Entwicklungsphase ausgesprochen sinnvoll, da
es hierdurch möglich ist, die Masse des Codes (Indexaufbau) getrennt von den
komplexen Teilen des Codes (Suche) zu entwickeln und zu testen. Darüber hinaus
ist dieses Modell auch für die Fehlersuche sehr hilfreich, da Fehler jederzeit
durch Speichern und Wiedereinspielen des Index reproduziert werden können.
Die zweite wichtige Designentscheidung - das massive Multithreading - hat sich hingegen nicht bewährt.
Es zeigte sich, dass nicht das Einlesen der HTML-Dateien, sondern vor allem das Parsen und Indexieren
sehr zeitintensiv ist. In allen Tests, bei denen Dokumente von deutschen Servern indexiert wurden,
trat das Phänomen auf, dass erst nachdem (fast) alle Seiten gelesen waren mit der Indexierung
begonnen wurde. Der eigendlich gewünschte Effekt, dass die Latenzzeit des Netzwerkzugriffs durch
Parsen und Indexieren überbrückt wird, trat somit nicht ein.
Insbesondere für eine weitere Verwendung der Suchmaschine ist die starke Modularisierung
der Suchmaschine sehr hilfreich. So ist es z.B. möglich durch Aendern von zwei Zeilen Code einen
neuen Parser (z.B. für TeX oder RTF) entweder zusätzlich oder im Austausch für den
HTML-Parser einzubinden. Auch die Unterteilung des Spiders in Gatherer und Fetcher erlaubt
vielfältige Erweiterungen, da hierdurch das Lesen und Auswerten der Dokumente strikt
voneinander getrennt sind.
Der Index
Eine Bewertung des Index ist nur schwer möglich, da sein Hauptqualitätskriterium -
Geschwindigkeit - nur schwer bewertbar ist.
Die Verwendung zweier Modi - Aufbau und Abfrage - hat sich bewährt.
Da der optimierte Index nur read-only ist, können dort fast alle Datenstrukturen als
Felder statischer Grösse implementiert werden. Neben der Möglichkeit effektive Datenstrukturen einsetzen zu können erhöht insbesondere der dadurch entfallende Zwang zur Synchronisation die Geschwindigkeit der Suchmaschine. Die Verwendung einer Prefix-Tabelle
hat sich ebenfalls als sinnvoll erwiesen, da hierdurch die Grösse des am häufigsten benutzten
Teils des Index - der Wortliste - erheblich reduziert werden konnte.
Der Nachteil dieses Modells ist, daß der Index nur durch ein komplettes Neueinlesen aller Seiten aktualisierbar ist. Alle bisher gemachten Erfahrugen zeigen jedoch, daß das Parsen und Indexieren um ein Vielfaches langsamer sind als das Lesen des Dokuments. Es macht daher keinen Sinn, das ohnehin schon langsame Indexieren noch langsamer zu machen, nur um Zeit an Stellen zu sparen, die nicht zeit-kritisch sind. Aus diesem Grunde halte ich diesen Nachteil
beim Einsatz der Suchmaschine zum Indexieren einer begrentzer Anzahl von Domains sogar für einen Vorteil.
Als sehr sinnvoll hat sich auch der Mehraufwand erwiesen, die Postinglisten nach Dokument-IDs zu
sortieren. Hierdurch können UND und ODER Verknüpfungen erheblich schneller durchgeführt werden, da das Zusammenfassen der Listen über einfaches Merging erfolgen kann.
Kritisch anzumerken ist jedoch, dass wir die Bedeutung des Index wohl etwas überschätzt haben.
Das Parsen und Normalisieren der Suchanfrage und das Aufbereiten der Ergebnismenge ist für
die meisten Suchanfragen erheblich zeitaufwendiger als das reine Suchen einer Postingliste
zu einem Wort. Ausnahmen hierbei sind lediglich Phrasensuchen, deren Abarbeitungsgeschwindigkeit stark vom Design des Index abhängig ist. Hier kommen uns die DocReps zugute, durch die unser Inmdex mit Sicherheit schneller ist als ein Index, in dem Dokumente nur über aufwendige Suche in den Postinglisten 'rekonstruierbar' sind.
Stemming und Spracherkennung
Die Erkennung der Sprache anhand der ersten 50 Worte des Textes scheint relativ
fehlerfrei zu funktionieren. Problem hierbei ist natürlich zu beachten, dass mit einem
englischen Abstract beginnende deutsche Texte nicht korrekt erkannt werden. Es wäre daher zu
überlegen, ob statt der ersten 50 Worte eine relativ gleichmässig verteilte Stichprobe von
Worten aus dem gesamten Text zur Spracherkennung herangezogen werden sollte.
Informationen zum Stemming finden sich ausfürlich in dem Paper von Jörg Caumanns.
Ranking
Das Ranking ist in der aktuellen Implementierung leider nur sehr rudimentär
vorhanden, so dass eine Bewertung nicht vorgenommen werden kann. Im Verlauf des
Semesters ist uns jedoch allen bewusst geworden, dass die Ranking-Funktion einer der
entscheidenden Teile einer Suchmaschine ist. Falls dieses Seminar nocheinmal
stattfinden sollte, muss auf jeden Fall mehr Zeit für die Frage verwendet werden,
welche Kriterien mit welchem Gewicht in das Ranking einfliessen sollen und
wie eine solche Funktion aussehen kann.
Die Anfragesprache
Die Anfragesprache ist im wesentlichen mit den von anderen Suchmaschinen verwendeten
Anfragesprachen identisch. Einzige Ausnahme ist, dass wir keine Klammerung unterstützen.
Der Nachteil dieser Einschränkung ist, dass viele komplexere Suchanfragen, die
bei anderen Suchmaschinen möglich sind, bei unserer Suchmaschine nicht gestellt werden
können. Vorteil des Verzichts auf Klammerung ist hingegen, dass die Suchanfrage in
eine Liste anstatt in einen Baum geparst werden kann. Hierdurch wird die Bearbeitung
und Auswertung der Anfrage vereinfacht.
Die Ergebnisdarstellung
Die Ergebnisdarstellung ist - anders als in herkömmlichen Suchmaschinen
- grafisch etwas ausladender darsgestellt. Dies wird auf den meisten
Systemen eine bessere Lesbarkeit der Ergebnisse hervorrufen, ein Manko
der meisten Suchmaschinen.
Die Navigation durch den Ergebnisraum ist
derzeit insofern eher an kleinee lokale Suchmaschinen denn an die
bekannten Internet-Suchportals angelehnt, als die Navigation nur von
Seite zu Seite erfolgt. Ein Sprung auf Seite 17 kostet 16 klicks, gäbe
es direkte Links auf die Seiten, wäre nur ein klick nötig. Das fehlen
dieses Features ist aber relativ leicht nachzurüsten und derzeit eher
einfach zu verschmerzen. Wert wurde vor allem darauf gelegt, daß dem
User alle Metadaten, die zu einem Dokument vorliegen, angezeigt
werden. Diesbezüglich ausgestattete Dokumente erhalten auf diese Weise
mehr Platz auf dem Bildschirm. Inwiefern dieser Ansatz si als
proktikabel erweist, muß aber noch in der Praxis geprüft werden. Denkbar
wäre der Ausschluß bestimmter Metadaten, etwa dem GENERATOR-Tag in
zukünftigen Versionen.
Last modified: Mon Feb 22 09:47:07 MET 1999