Postingslista

Postingslista är inom informationsåtervinning en datastruktur som används i en inverted index. För varje ord eller term i en samling av dokument lagras en lista med referenser till de dokument där termen förekommer. Listan kan även innehålla ytterligare information om varje dokument, till exempel termfrekvensen (hur många gånger termen förekommer i dokumentet) och positionsinformation (de exakta positionerna där termen dyker upp). Positionsdata gör det möjligt att hantera fras- och närhetsfrågor, medan endast dokumentlistan tillåter enklare sökningar.

Vanligen är postingslistor sorterade efter dokumentidentifierare och lagras tillsammans i en termkatalog. Vid frågorbehandling används operationer som snitt och union över postingslistor för att identifiera dokument som innehåller en eller flera sökord. För frasfrågor krävs positionsdata för att verifiera att orden uppträder i rätt ordning och inom rätt avstånd.

Postingslistor kan komprimeras och delas upp i olika representationer för att spara lagringsutrymme och förbättra läsning. Vanliga tekniker inkluderar lucka-kodning (gap encoding) av dokument-id:n och variabel-längd kodning, samt användning av skip-punkter för snabbare blandningar. I moderna söksystem används ofta segmenterade eller log-structured indexeringar där postingslistor uppdateras i bakgrunden.

Behandling av uppdateringar kan vara kostsam, eftersom nya dokument kräver inkorporering i relevanta postingslistor. Många system använder batch-uppbyggnad eller inkrementella metoder och en mellanlagrad ordbok för att stödja snabba uppslag.