1.3.1.3: Implementierung mit invertierten Listen

Boolesche Retrieval-Systeme werden im Allgemeinen mit Hilfe von invertierten Listen implementiert: Für jedes Feld wird eine Liste (oder andere Speicherstruktur) angelegt, in der zu jedem Term eingetragen wird, in welchen Dokumenten er vorkommt (siehe auch Frakes Baeza-Yates, 1992 [->] ). Diese Listen von Dokumenten entsprechen den Umkehrabbildungen T^-1_t1 . Das Verfahren ermöglicht einen schnellen Zugriff, braucht dafür aber auch viel Speicherplatz. Zudem muss bei vielen Systemen die invertierte Liste bei einer Erweiterung des Dokumentenbestands komplett neu berechnet werden.

Zur Konstruktion einer invertierten Liste müssen die Terme, nach denen gesucht werden kann, bekannt sein. Dazu können sie entweder in einer Liste vorgegeben werden oder es müssen Regeln angegeben werden, mit denen sie sich aus den Textdokumenten gewinnen lassen. Wird eine "von Hand" konstruierte Liste mit zulässigen Wörtern oder Termen vorgegeben, spricht man von einem kontrollierten Vokabular . Bei der so genannten Freitextsuche werden die zulässigen Terme mit Hilfe von Regeln aus den Wörtern der Dokumente gewonnen. Durch diese Terme werden die Dokumente im booleschen Retrieval beschrieben. Man nennt sie deshalb auch Indexterme und sagt, dass das Dokument mit den Indextermen indexiert (vereinzelt auch indiziert) wird. Dieses Vokabular zulässiger Terme sollte einerseits möglichst alle "sinntragenden" Wörter enthalten, die in den Dokumenten auftreten, andererseits sollte es aus Gründen der Speicherplatzökonomie möglichst nicht zu groß werden. Insbesondere sehr häufige Terme benötigen durch die vielen Einträge viel Speicherplatz und tragen wenig zur inhaltlichen Unterscheidung der Dokumente bei. Sie können deshalb als Indexterme ausgeschlossen werden.

Zur Bestimmung des Vokabulars kann man folgendermaßen vorgehen: Zunächst werden Regeln festgelegt, nach denen Texte in Zeichenketten zerlegt werden. Dabei muss z.B. entschieden werden, wie mit Sonderzeichen wie Bindestrichen, Apostrophen und Punkten (als Abkürzung und Satzende) oder Ziffern in Zeichenketten umgegangen wird. Als Nächstes können Regeln festgelegt werden, nach denen bestimmte Zeichenketten aussortiert werden, z.B. solche, die nur aus Ziffern bestehen, römische Zahlen darstellen oder aus anderen Gründen nicht zur Indexierung zugelassen werden sollen. Schließlich können diejenigen Zeichenketten aussortiert werden, die in einer Stoppwortliste vorkommen. Eine solche Stoppwortliste enthält die häufigsten Wörter wie Artikel, Präpositionen und Partikel, die nicht in das Vokabular aufgenommen werden sollen, weil sie für sich allein nicht sinntragend sind. Die Zeichenketten, die nach diesen Schritten übrig bleiben, sind die Terme des Vokabulars.

Die invertierte Liste kann im Prinzip in folgenden Schritten konstruiert werden (siehe auch Harman, Baeza-Yates, Fox und Lee, 1992 [->] ):

• Anhand der Regeln zur Bestimmung zulässiger Terme werden die Dokumente in Terme zerlegt.
• Zu den Termen werden jeweils das Dokument und die Position des Auftretens im Dokument geschrieben (word within location list).
• Diese Paare aus Termen und ihren Positionen werden (primär nach Termen alphabetisch, sekundär nach Positionen) sortiert.
• Paare mit gleichen Termen werden zusammengefasst, wobei die Positionen in einer sortierten Liste an den Term angefügt werden.
• Die Terme werden von den Listen mit ihren Positionen getrennt. Dabei werden die Terme in eine Indexdatei geschrieben, die zu jedem Term einen Zeiger (Pointer) auf die zugehörige Liste enthält. Die Positionen können auch in ein einziges Postings File geschrieben werden. Dann muss in der Indexdatei zu jedem Term die Anzahl der Positionen und die Stelle im Postings File angegeben werden, an der ihre Aufzählung beginnt.

Eine Anfrage wird nun folgendermaßen bearbeitet:

• Zunächst werden die Terme in der Anfrage isoliert.
• Aus der invertierten Liste wird für jeden Term die Liste mit seinen Positionen in den Dokumenten oder deren Feldern ermittelt. Dazu lässt sich der Zeiger aus der Indexdatei verwenden oder es wird anhand der Stelle und Länge der entsprechende Abschnitt aus dem Postings File kopiert.
• Die Listen zu den verschiedenen Termen werden zusammengeführt: Sind die Terme mit OR verknüpft, werden die Listen vereinigt, sind sie mit AND verknüpft, wird der Durchschnitt gebildet, bei AND NOT wird die Differenz berechnet.
• Die Dokumente, die in der resultierenden Liste übrigbleiben, werden aus der Dokumentdatei geholt und als Resultat der Anfrage präsentiert.