Postingslisten

Postingslisten (Singular: Postingsliste) sind eine zentrale Datenstruktur in der Information Retrieval. Für jedes Suchwort wird eine Liste von Fundstellen geführt, die angibt, in welchen Dokumenten dieses Wort vorkommt. Postingslisten bilden das Gegenstück zum Wörterbuch und bilden den Kern eines invertierten Index, der Anfragen effizient beantwortet.

Ein Eintrag in einer Postingsliste, ein Posting, enthält typischerweise eine Dokumentenkennung. Häufig werden zusätzlich die Termhäufigkeit im Dokument (TF) sowie Positionsangaben gespeichert, also die Positionen, an denen das Wort im Text vorkommt. Positionen ermöglichen Phrase- und Nahabfragen sowie eine präzisere Bewertung der Relevanz.

Es gibt Varianten: Postingslisten mit Positionsdaten (positional postings) und Listen ohne Positionsdaten. Im invertierten Index werden pro Term oft mehrere Postings zusammengeführt, um Abfragen zu beantworten. Neben der Suche unterstützen Postings auch Ranking-Modelle (z. B. TF-IDF oder modernere Modelle).

Speicher- und Leistungsaspekte: Große Listen werden komprimiert gespeichert. Typische Techniken sind Lückenkodierung (Gap Encoding), variable-byte Coding oder PForDelta; oft kommen Sprungpointer (Skip pointers) zum Einsatz, um Schnitte von großen Listen zu beschleunigen. In verteilten Systemen können Indizes auf mehreren Knoten gespeichert und entsprechend synchronisiert werden.

Historischer Kontext: Die Idee eines invertierten Index stammt aus der Informationsbeschaffung und der IR-Forschung; Postingslisten ermöglichen schnelle Abfragen über Textcorpora.