Was ist ein invertierter Index?
Ein invertierter Index (englisch inverted index) ist ein Verzeichnis, das zu jedem Wort die Dokumente nennt, in denen es vorkommt. Mit ihm findet eine Suche ein Wort in Millionen von Texten in Sekunden, ohne jeden Text zu lesen.
Denken Sie an das Stichwortverzeichnis am Ende eines Lehrbuchs. Sie schlagen ein Wort nach und sehen sofort die Seiten. Jede Suche arbeitet nach diesem Prinzip.
Am Ende dieser Lektion
Notiz
Ich kann mit einem invertierten Index die Dokumente zu einem Wort finden.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Dokument | ein Text, der durchsucht wird | ein Aushang der Mensa |
| Index | ein Verzeichnis, das zu jedem Wort die Fundstellen nennt | |
| Postingliste | die Liste der Dokumentnummern zu einem Wort | [1, 3, 4] |
| Boolesche Suche | eine Suche, die Wörter mit UND, ODER und NICHT verknüpft | |
| Anfrage | die Wörter, die jemand eintippt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ohne Index müsste eine Suche jeden Text lesen
Die einfachste Suche liest alle Dokumente nacheinander und prüft, ob das Wort darin steht. Bei vier Texten geht das schnell. Bei einer Million Texten dauert jede Anfrage viel zu lange.
Der Index dreht die Blickrichtung um. Statt zu jedem Dokument seine Wörter zu speichern, speichert er zu jedem Wort seine Dokumente. Darum heißt er invertiert, also umgekehrt.
Einen kleinen Index bauen
dokumente = {
1: "die mensa oeffnet um elf uhr",
2: "die bibliothek oeffnet um acht uhr",
3: "die mensa bietet nudeln an",
4: "nudeln und kaese in der mensa",
}
index = {}
for nummer in dokumente:
for wort in dokumente[nummer].split():
if wort not in index:
index[wort] = []
if nummer not in index[wort]:
index[wort].append(nummer)
print(index["mensa"])
print(index["nudeln"])
# Suchen Sie nach "uhr". Was passiert bei einem Wort, das in keinem Text steht?
Die Postingliste zu „mensa“ im Terminal
docker exec jupyter python3 -c "d={1:'die mensa oeffnet um elf uhr',2:'die bibliothek oeffnet um acht uhr',3:'die mensa bietet nudeln an',4:'nudeln und kaese in der mensa'}; print([n for n in d if 'mensa' in d[n].split()])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beispiel: vier Dokumente und ihr Index
| Wort | Postingliste | Bedeutung |
|---|---|---|
| mensa | 1, 3, 4 | steht in drei Dokumenten |
| nudeln | 3, 4 | steht in zwei Dokumenten |
| oeffnet | 1, 2 | steht in zwei Dokumenten |
| bibliothek | 2 | steht nur im zweiten Dokument |
| kaese | 4 | steht nur im vierten Dokument |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
UND, ODER und NICHT verknüpfen Postinglisten
Eine Anfrage mit mehreren Wörtern verknüpft ihre Postinglisten. UND behält die Nummern, die in beiden Listen stehen. ODER behält die Nummern, die in mindestens einer Liste stehen. NICHT streicht die Nummern der zweiten Liste aus der ersten.
Das nennt man Boolesche Suche, nach dem Mathematiker George Boole. Sie liefert Treffer oder keine Treffer, aber keine Reihenfolge.
Beispiel: drei Anfragen an den Index
| Anfrage | Rechnung | Treffer |
|---|---|---|
| mensa UND nudeln | [1, 3, 4] und [3, 4] | 3, 4 |
| oeffnet ODER nudeln | [1, 2] oder [3, 4] | 1, 2, 3, 4 |
| mensa NICHT nudeln | [1, 3, 4] ohne [3, 4] | 1 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Zwei sortierte Listen zusammenführen
liste_a = [1, 3, 4]
liste_b = [3, 4]
treffer = []
i = 0
j = 0
while i < len(liste_a) and j < len(liste_b):
if liste_a[i] == liste_b[j]:
treffer.append(liste_a[i])
i = i + 1
j = j + 1
elif liste_a[i] < liste_b[j]:
i = i + 1
else:
j = j + 1
print(treffer)
# Ändern Sie liste_b zu [2, 4]. Welche Nummer bleibt übrig?
Eine UND-Suche im Terminal
docker exec jupyter python3 -c "d={1:'die mensa oeffnet um elf uhr',2:'die bibliothek oeffnet um acht uhr',3:'die mensa bietet nudeln an',4:'nudeln und kaese in der mensa'}; print([n for n in d if 'mensa' in d[n].split() and 'nudeln' in d[n].split()])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele denken, der Index enthalte die Texte selbst. Das stimmt nicht. Er enthält nur Wörter und Nummern. Den Text holt die Suche erst, wenn sie die Trefferliste anzeigt.