Architektur von Suchmaschinen: Indexierung

Heute werde ich mich in unserer Reihe zur Architektur von Suchmaschinen dem dritten und letzen Aufgabenbereich des Information Retrieval Systems widmen, der Indexierung beziehungsweise der „Schaffung durchsuchbarer Datenstrukturen“.

Die Aufgabe von Suchmaschinen ist es, dem Nutzer möglichst die Internetseiten anzuzeigen, die zu seinen Suchbegriffen am passendsten und relevantesten sind. In unserer Serie haben wir die Datengewinnung und die Dokumentenanalyse bereits besprochen. Wir haben geklärt, wie es den Suchmaschinen gelingt automatisch Inhalte im Web zu finden und diese dann auch noch zu verstehen. Wir sind auf bestimmte Filter eingegangen, die angewandt werden, um die inhaltlich relevanten Teile einer Website herauszufinden. Und schließlich haben wir erklärt, wie die Suchmaschinen die relevanten Keywords in den einzelnen Dokumenten finden.

Diese bisher geschilderten Vorgänge sind allesamt nötig, um eine vernünftige, durchsuchbare Datenstruktur erstellen zu können.

Indexierung

Wenn man den Begriff Indexierung bei Wikipedia eingibt, erhält man folgende Definition: „Als Indexierung […] bezeichnet man beim Information Retrieval die Zuordnung von Deskriptoren zu einem Dokument zur Erschließung der darin enthaltenen Sachverhalte.“ Diese Erklärung macht deutlich, dass es sich bei der Indexierung nicht um einen von den weiteren Vorgängen im Webcrawler und Information Retrieval System abgekoppelten Prozess handelt. Genau genommen gehören alle in unserer Reihe zur Architektur von Suchmaschinen beschriebenen Maßnahmen zur Indexierung. In unserer schematischen Darstellung der Architektur von Suchmaschinen halte ich es aber trotzdem für sinnvoll erst jetzt von Indexierung zu sprechen, vor allem auch zur Vereinfachung.

Die Hauptaufgabe der Suchmaschinen, nämlich relevante Suchergebnisse zu liefern, kann nur erfüllt werden, wenn durchsuchbare Datenstrukturen vorliegen. Im Information Retrieval System wird dies mit Hilfe eines invertierten Dateisystems erreicht.

Das invertierte Dateisystem

Das invertierte Dateisystem kann in drei Elemente unterteilt werden:

1. Direkte Dateien: Dies sind die ursprünglichen Dokumente, als Textdatei vorliegend, von HTML-Code entfernt und vereinheitlicht.
2. Index: Anders als man meinen könnte, enthält der Index nicht die gesamten Dokumente, sondern lediglich die aus ihnen gewonnen Keywords, die in alphabetischer Reihenfolge sortiert werden. Der Index enthält also alle Keywords aus allen „indexierten“ Dokumenten.
3. Invertierte Dateien: Die invertierten Dateien sind das Herzstück des Ganzen. Sie verknüpfen den Index mit den direkten Dateien, denn zu jedem Keyword im Index existiert eine invertierte Datei, die die DocID der Dokumente enthält, in denen das Keyword vorkommt. Außerdem enthalten die invertierten Dateien weitere Informationen, die später das Ranking erst möglich machen.

Wenn jetzt also ein bestimmtes Keyword abgefragt wird, das sich im Index befindet, so führt von dort ein Verweis zu einer invertierten Datei. Hier finden sich wiederum Verweise auf alle Dokumente, die dieses Stichwort enthalten. Diese können dann für die Ergebnisliste herangezogen werden.

Boolesche Operatoren

Selbstverständlich ist es eher unwahrscheinlich und auch unpraktisch nur nach einem Keyword suchen zu können. Die Suche nach mehreren Stichworten ist heute gängige Praxis in allen Suchmaschinen. Grundlage dafür sind die sogenannten Booleschen Operatoren. Dies sind Verknüpfungen, die mit Operatoren wie UND, ODER, NICHT zwischen zwei Keywords erstellt werden können. Diese kann der User nach wie vor selbst in der Suchmaske bestimmen, allerdings laufen diese Operatoren automatisch immer im Hintergrund, wenn mehrere Keywords gleichzeitig eingeben werden. So kann im invertierten Dateisystem anhand der DocIDs in den invertierten Dateien verglichen werden, welche Dokumente zum Beispiel beide Keywords enthalten.