Invertierte Dateisysteme
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. Entferungung 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, Wohstand, Macht,
wenn alles dies die Menschen nur verflacht? |
(aus: Christian Morgenstern, Sprüche)
Arbeitsschritte des Programms bei der Volltextinvertierung:
1. Schritt:Erstellung eines Index in der Reihenfolge des Vorkommens im Text. Jedes Wort erhält beim ersten Vorkommen eine feste Adresse (Nr.) | 2. Schritt: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 | verflacht | 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 | Zusatzinfo |
|---|
| ... | ... | ... | ... |
| 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.
Quellen:
Einführung in Information Retrieval
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 nicht üblich.
Stand: 24. August 2003
