Um einen schnellen Zugriff auf Textdokumente über enthaltene Stichwörter zu ermöglichen, müssen die Texte zu einem invertierten Dateisystem aufbereitet werden. Ein invertiertes Dateisystem besteht aus

• den direkten Dateien. Das sind die Textdokumente. Sie liegen leicht verändert vor (z.B. Entfernung von HTML-Code, Vereinheitlichung auf Kleinschreibung).
• dem Index. Das ist eine alphabetische Liste der in den direkten Dateien enthaltenen Stichwörter. Jede Indexeintragung verweist wiederum auf eine invertierte Datei.
• den invertierten Dateien. Sie sind die Verbindungen zwischen dem Index und den direkten Dateien. Sie verweisen auf alle Textdokumente, in denen das bestimmte Stichwort vorkommt. Außerdem enthalten sie Informationen, die für ein Rankingverfahren (vgl. LE 6: Retrievalmodelle) benötigt werden.

Quelle: Glöggler, Kap. 3.2 und 3.3.3

Vom Textdokument zum invertierten Dateisystem

(ein vereinfachtes Beispiel)

Dokument 1

Er konnte nie über etwas lachen, wie kann ein Mensch so tief verflachen!

Dokument 2

Wozu, so fragt man sich, Reichtum, Wohlstand, Macht, wenn alles dies die Menschen nur verflacht?

(aus: Christian Morgenstern, Sprüche)

Arbeitsschritte des Programms bei der Volltextinvertierung:

1. Schritt:		2. Schritt:
Erstellen eines Index in der Reihenfolge des Vorkommens im Text. Jedes Wort erhält beim ersten Vorkommen eine feste Adresse (Nr.)		alphabetische Sortierung des Index aus Schritt 1
numerisch sortierter Index		alphabetisch sortierter Index
Adresse	Stichwort	Stichwort	Adresse
1	er	alles	22
2	konnte	die	24
3	nie	dies	23
4	über	ein	9
5	etwas	er	1
6	lachen	etwas	5
7	wie	fragt	15
8	kann	kann	8
9	ein	konnte	2
10	mensch	lachen	6
11	so	macht	20
12	tief	man	16
13	verflachen	mensch	10
14	wozu	menschen	25
15	fragt	nie	3
16	man	nur	26
17	sich	reichtum	18
18	reichtum	sich	17
19	wohlstand	so	11
20	macht	tief	12
21	wenn	über	4
22	alles	verflachen	13
23	dies	dies	23
24	die	wenn	21
25	menschen	wie	7
26	nur	wohlstand	19
27	verflacht	wozu	14

3. Schritt:

Jetzt wird das invertierte Dateisystem erstellt, indem für jedes Wort eine invertierte Liste angelegt wird, in der angegeben ist:

• Identnummer des Dokuments, in dem das Stichwort vorkommt
• Position im Text
• Häufigkeit (Frequenz)
• Zusatzinformationen, wie z.B. Gewicht des Stichwortes im Text

Nr. Stichwort	DocID	Position im Text	Frequenz	Zusatzinfos z.B. Gewicht
...	...	...	...
10	1	10	1
11	1 2	11 2	1 1
...	...	...	...
27	2	15	1

Erläuterungen

Eine Zeile ist eine invertierte Liste/Datei im invertierten Dateisystem. Für jedes Stichwort wird eine eigenständige invertierte Liste in der invertierten Datei erstellt.

Achtung: Die Bezeichnungen 'invertierte Liste' und 'invertierte Datei' werden häufig verwechselt, bzw. synonym verwendet. Es gibt keine einheitliche Sprachregelung.

Quelle:

C.J. van Rijsbergen: Information Retrieval, Kapitel 4

Bei der Suche nach einem Dokument greift ein Retrieval System zunächst auf den alphabetisch sortierten Index zu. Der Index holt sich Informationen zu dem gesuchten Indexterminus in der entsprechenden invertierten Datei. Die wiederum greift über die in ihr enthaltenen Dokument-Identnummern auf die direkten Textdateien zu.

Stichwortsuchen in Textdokumenten erfolgen also über alphabetisch oder numerisch sortierte Listen; dadurch sind sie schnell. Eine direkte Suche nach einem Stichwort in einer Sammlung von Textdokumenten (Stringsuche) ist sehr langsam und nur in sehr kleinen Textmengen üblich.

Stand: 1. März 2005

< Seite drucken >
< Zum Seitenanfang >

STEP 1 - Einführung | STEP 2 - Initialaufgabe | STEP 3 - Lektüre 1 | STEP 4 - Lektüre 2 | STEP 5 - Übung