Omvendt indeks

Et inverteret indeks er en datastruktur, hvori den tilsvarende liste for hvert ord i en samling af dokumenter viser alle dokumenterne i den samling, hvori det forekommer. Det omvendte indeks bruges til at søge gennem tekster.

Der er to varianter af det omvendte indeks:

et indeks, der kun indeholder en liste over dokumenter for hvert ord,
et indeks, der eventuelt inkluderer ordets position i hvert dokument [1] .

Ansøgning

Lad os beskrive, hvordan vi løser problemet med at finde dokumenter, der indeholder alle ordene fra søgeforespørgslen . Når du behandler en søgeforespørgsel på et enkelt ord, er svaret allerede i det omvendte indeks - tag blot den liste, der svarer til ordet fra forespørgslen. Ved behandling af en flerordsforespørgsel tages skæringspunktet mellem listerne svarende til hvert af forespørgselsordene.

Normalt, i søgemaskiner , efter opbygning af en liste over dokumenter, der indeholder ord fra en forespørgsel ved hjælp af et omvendt indeks, rangeres dokumenterne fra listen . Det omvendte indeks er den mest populære datastruktur, der bruges til informationssøgning [2] .

Eksempel

Lad os have et korpus af tre tekster , og så vil det omvendte indeks se sådan ud: $T_{0}=$ "it is what it is" $T_{1}=$ "what is it" $T_{2}=$ "it is a banana"

"a": {2} "banan": {2} "er": {0, 1, 2} "det": {0, 1, 2} "hvad": {0, 1}

Her angiver tallene numrene på de tekster, hvor det tilsvarende ord forekommer. Behandling af "what is it"søgeforespørgslen vil derefter give følgende resultat . $\{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}$

Applikationsfunktioner i rigtige søgemaskiner

På listen over forekomster af et ord i dokumenter er der ud over dokumenternes id normalt også angivet faktorer ( TF-IDF , binær faktor: "om ordet rammer titlen eller ej", andre faktorer), som er brugt i ranglisten. Indekset kan bygges ikke efter alle ordformer , men efter lemmaer (ifølge ords kanoniske former). Stopord kan udelukkes og et indeks ikke bygges til dem, forudsat at hvert af dem forekommer i næsten alle dokumenter i korpuset. For at fremskynde beregningen af skæringspunkter bruges heuristik af skip-pointere . Ved behandling af anmodninger, der indeholder mange ord, bruges quorum-funktionen, som springer til næste trin i rangeringen af den del af dokumenter, hvor ikke alle ord fra anmodningen blev fundet.

Se også

Søg indeks

Litteratur

Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Moderne informationssøgning . - Reading, Massachusetts : Addison-Wesley Longman, 1999. - 192 s. — ISBN 0-201-39829-X .
Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao. Inverterede filer versus signaturfiler til tekstindeksering // ACM Transactions on Database Systems ( TODS): Journal. - 1998. - Nej. 23 . - S. 453 - 490 . - doi : 10.1145/296854.277632 .