📚 Page 05 von 8 · ~25 Min

Der Inverted Index – die genialste Datenstruktur des Web 📚

Warum funktioniert Suche in 400 Milliarden Seiten schneller als das Finden einer Datei auf deinem Laptop? Wegen dieser Idee. In dieser Page bauen wir Schritt für Schritt einen echten Inverted Index – inkl. Tokenization, Stemming, Posting Lists, Skip Pointers und Index-Kompression.

🔤 Tokenization 🌱 Stemming 📋 Posting Lists 🗜 Kompression

▶Live ausprobieren

Tippe ein Wort. Sieh wie die Suchmaschine in einem Schritt findet, in welchen Dokumenten es vorkommt.

01Forward vs Inverted Index – der Unterschied

Beide Datenstrukturen verbinden Dokumente mit Wörtern. Aber in genau umgekehrter Richtung.

📄 Forward Index

Dokument → Wörter darin

Doc 1: [roboter, baut, drucker]
Doc 2: [drucker, druckt, pla]
Doc 3: [roboter, hat, motor]
        

Schwäche: Suchst du „motor", musst du alle Docs durchgehen, um zu sehen, wer's enthält. Bei 400 Mrd Docs nicht machbar.

🔁 Inverted Index

Wort → Dokumente, die's enthalten

roboter: [1, 3]
drucker: [1, 2]
motor:   [3]
pla:     [2]
        

Stärke: „motor" suchen = ein Schlag im Index. Sofort: „Doc 3". O(1) statt O(n).

02Tokenization – Text in Wörter zerlegen

Klingt einfach. Ist es nicht.

Beispiel-Satz: "Lunolabs baut den XLeRobot, einen 3D-gedruckten Roboter."

Naive Tokenization (Split bei Whitespace):

Lunolabs baut den XLeRobot, einen 3D-gedruckten Roboter.

Probleme:

Komma und Punkt kleben an Wörtern: XLeRobot, ist nicht das gleiche wie XLeRobot
Bindestriche: ist 3D-gedruckten ein Wort oder zwei?
Apostrophe: „l'amour" → eins oder zwei Tokens?
Asiatische Sprachen: Chinesisch hat keine Leerzeichen zwischen Wörtern
Emojis: 🚀 ist ein Zeichen, aber als Suchterm relevant

Gute Tokenizer machen das richtig:

lunolabs baut den xlerobot einen 3d gedruckten roboter

03Normalization – alles vergleichbar machen

"Roboter", "ROBOTER", "Robotern", "robóter" sollen alle den gleichen Index-Eintrag finden.

Schritt 1: Lowercasing

„Roboter" → roboter. Trivial, aber wichtig.

Schritt 2: Stopword-Removal

Wörter wie der, die, das, und, ist, in tragen kaum Bedeutung. Sie raus.

lunolabs baut den xlerobot einen 3d gedruckten roboter

Schritt 3: Stemming / Lemmatization

Wortvarianten auf einen gemeinsamen Stamm reduzieren. Zwei Ansätze:

Methode	Beispiel	Bemerkung
Stemming (regelbasiert)	laufen, läuft, lief → lauf	Schnell, kann „falsche" Stämme erzeugen (z.B. „better" → „bett")
Lemmatization (wörterbuchbasiert)	laufen, läuft, lief → laufen	Schöner, aber langsamer und sprachabhängig

🌍

Klassiker: Der Porter-Stemmer (1980, Englisch) und der Snowball-Stemmer (Multi-Sprache) sind seit Jahrzehnten im Einsatz – in Elasticsearch, Lucene, Solr.

04Posting Lists – die Daten hinter dem Wort

Pro Wort speichert der Index nicht nur „in welchen Docs", sondern auch wo und wie oft.

Eine Posting List ist die Liste aller Vorkommen eines Wortes:

POSTING LIST
Term: "roboter"
df: 3              # in 3 Dokumenten
postings:
  doc=1, tf=2, positions=[5, 18]
  doc=7, tf=5, positions=[2, 14, 22, 31, 40]
  doc=42, tf=1, positions=[8]
    

Was jeder Eintrag speichert:

doc ID – welches Dokument
tf (term frequency) – wie oft im Dokument
positions – wo im Dokument (wichtig für Phrase Queries wie „echte Roboter")

Skip Pointers – schneller durch die Liste

Wenn zwei Wörter zusammen gesucht werden („roboter AND motor"), muss die Suche die Schnittmenge beider Posting Lists finden. Mit Skip Pointers (alle ~√n Einträge) springst du große Stücke.

SKIP POINTERS
"roboter":  [1] [3] [5] [9] -> [21] [28] -> [42] [55] -> [71] [88]
"motor":    [9] [10] [21] [88]

# Suche nach AND-Schnittmenge:
# Wenn aktuell bei roboter=9, motor=9 → match!
# Wenn aktuell bei roboter=21, motor=88 → spring direkt zu 71 via Skip!
    

05Index-Kompression – Milliarden Einträge auf TB

Naiv gespeichert wäre ein Web-Index Petabytes. Mit cleveren Tricks: Terabytes.

Variable Byte Encoding

Doc-IDs sind oft klein, aber 32-bit integers verschwenden Platz. Variable Byte: ein Wert braucht 1, 2, 3 oder 4 Bytes – je nach Grösse. Bit 7 = „mehr kommt".

Delta Encoding (Gaps)

Statt absoluter Doc-IDs nur die Differenzen speichern. Aus [1042, 1057, 1089, 1098] wird [1042, 15, 32, 9] – viel kleinere Zahlen, viel komprimierbarer.

Front Coding für Wörter

Im Wörterbuch (Term-Dict) stehen die Wörter sortiert. Aufeinanderfolgende Wörter teilen oft Präfixe: "robot", "roboter", "roboterhaft", "robotik". Speichere nur die Differenz zum Vorgänger.

📊

Wirkung: Ein moderner Suchindex erreicht ~25 % der unkomprimierten Grösse – ohne Verlust. Genau diese Tricks machen Such-Engines auf normalen Servern überhaupt erst betreibbar.

06Mini-Inverted-Index in Python

~30 Zeilen Code für einen funktionierenden (Mini-) Suchindex.

PYTHON
from collections import defaultdict
import re

def tokenize(text):
    # lowercase + nur Buchstaben/Ziffern
    return re.findall(r"[a-zäöü0-9]+", text.lower())

class InvertedIndex:
    def __init__(self):
        self.index = defaultdict(set)   # wort -> {doc_ids}
        self.docs = {}                  # doc_id -> original text

    def add(self, doc_id, text):
        self.docs[doc_id] = text
        for token in tokenize(text):
            self.index[token].add(doc_id)

    def search(self, query):
        tokens = tokenize(query)
        if not tokens: return []
        # Schnittmenge aller Posting-Lists (AND)
        result = self.index[tokens[0]]
        for t in tokens[1:]:
            result = result & self.index[t]
        return [self.docs[d] for d in result]

# --- DEMO ---
idx = InvertedIndex()
idx.add(1, "Lunolabs baut Roboter und 3D-Drucker")
idx.add(2, "3D-Drucker drucken Bauteile aus PLA")
idx.add(3, "Roboter brauchen Sensoren und Motoren")

print(idx.search("roboter motor"))
# => ["Roboter brauchen Sensoren und Motoren"]
    

🚀

Du hast gerade einen Suchindex gebaut. Das ist im Kern genau das, was Lucene/Elasticsearch machen – nur mit Stemming, Position-Tracking, Kompression, Sharding und ein paar hundert anderen Features obendrauf. Aber das Konzept? Diese 30 Zeilen.

🎯Key Takeaways

Der Inverted Index dreht die Frage um: nicht „welche Wörter im Dokument", sondern „welche Dokumente fürs Wort".
Tokenization ist die Kunst, Text in saubere Wörter zu zerlegen – mit allen Edge Cases.
Normalization (Lowercasing, Stopwords, Stemming) macht Wörter vergleichbar.
Posting Lists enthalten pro Wort: Doc-ID, Frequency, Positionen.
Skip Pointers beschleunigen AND/OR-Queries über mehrere Listen.
Index-Kompression (VByte, Delta-Encoding, Front-Coding) → ~25% der Roh-Grösse.
In ~30 Zeilen Python hast du einen funktionierenden Mini-Inverted-Index.