3.1.3: Implementierung mit einer invertierten Liste

Boolesche Retrieval Systeme werden i. a. mit Hilfe von invertierten Listen implementiert, d. h. es wird für jedes Feld 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 TI^-1_t1 . Dieses Verfahren ermöglicht einen schnellen Zugriff, es erfordert dafür aber auch erhebliche Mengen an Speicherplatz. Zudem muß häufig bei einer Erweiterung des Dokumentbestandes die invertierte Liste neu berechnet werden.

Zur Konstruktion einer invertierten Liste muss eine Liste aller Terme, nach denen gesucht werden kann, vorgegeben werden bzw. es müssen Regeln angegeben werden, mit denen bestimmt werden kann, ob ein Term als Suchterm zulässig ist oder nicht. Wird eine "von Hand" konstruierte Liste mit zulässigen Wörtern oder Termen vorgegeben, spricht man von einem kontrollierten Vokabular. Bei der sogenannten 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 zum einen 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. Zur Bestimmung des Vokabulars kann man folgendermaßen vorgehen:

• Es werden Regeln festgelegt, nach denen Texte in Terme zerlegt werden. Das betrifft z. B. die Behandlung von Interpunktionszeichen, Bindestrichen etc.
• In einer Stoppwortliste werden die häufigsten Wörter wie Artikel, Präpositionen etc. gesammelt, die nicht in die Liste aufgenommen werden.
• Es werden Regeln festgelegt, nach denen bestimmte Zeichenketten aussortiert werden, wie z. B. solche, die nur aus Ziffern bestehen, Römische Zahlen etc.
• Die Zeichenketten, die nach Anwendung dieser Regeln übrigbleiben, sind die zulässigen 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 und die Listen mit den Positionen werden getrennt, wobei die Terme in eine Indexdatei geschrieben werden, die zu jedem Term einen Pointer auf die zugehörige Liste enthält (bzw. einen Offset in einem Postings File, das alle Positionen enthält).

Die Trennung der Terme und Listen in verschiedene Dateien dient dazu, den Zugriff auf die Terme zu beschleunigen. Es muß in diesem Fall bei der sequentiellen Suche pro Term, der vor dem gesuchten Term liegt, nur ein Pointer überlesen werden und nicht die ganze Liste der Positionen.

Eine Anfrage wird nun folgendermaßen bearbeitet:

• Es werden die Terme in der Anfrage isoliert.
• Zu jedem Term wird in der Indexdatei der invertierten Liste der Pointer auf die Liste mit den Positionen, also den Nummern der Dokumente bzw. der Dokumentfelder, in denen der Term vorkommt, ermittelt.
• Die Listen zu den verschiedenen Termen werden, je nachdem, durch welchen Operator die Terme verbunden sind, vereinigt, es wird der Durchschnitt gebildet oder es wird eine Differenz berechnet.
• Die Dokumente, die in der resultierenden Liste übrigbleiben, werden aus der Dokumentdatei geholt und als Resultat der Anfrage präsentiert.

Der aufwändigste Schritt bei der Berechnung der invertierten Liste ist das Sortieren, insbesondere, wenn die ganze Liste auf einmal sortiert wird. Deshalb setzen an diesem Punkt diverse Verbesserungsmethoden an. Zum einen können die Daten aufgeteilt werden, so dass die Datenmengen, die zwischengespeichert werden müssen, handhabbar bleiben. Zum anderen können die Terme in den Knoten eines binären Baums gespeichert werden, an denen dann Listen mit den Positionsangaben angehängt werden.

Ein weiteres Verfahren ist der Fast Inversion Algorithm von Fox and Lee (1991 [->] beschrieben in Frakes Baeza-Yates 1992 [->]).