Um einen schnellen Zugriff auf Textdokumente über enthaltene Stichwörter zu ermöglichen, müssen die Texte zu einem invertierten Dateisystem aufbereitet werden. Hierbei handelt es sich um die gespeicherten Dokumente als Fließtext und zwei Indexdatein. 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 alphabetischen 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	verflacht	27
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)
  [Die Frequenz pro Zeile ist immer 1, da ein Wort an einer Position nur einmal vorkommen kann. Die Spalte kann man aber zum Zählen der Häufigkeiten nutzen.]

Nr. Stichwort	DocID	Position im Text	Frequenz
...	...	...	...
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.

Suche:

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: 25. September 2017

Quellen:

Einen guten Einstieg zum Thema Index bieten die Wikipedia Artikel "Index (search engine)" und "Inverted Index"

C.J. van Rijsbergen: Information Retrieval, Kapitel 4
Online-Vorlesung zum inverted index des Stanford-Experten Dan Jurafsky on YouTube.

< Seite drucken >
< Zum Seitenanfang >

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