Invertert indeks
I informasjonsgjenfinning er en Invertert indeks en ord-orientert mekanisme for å indeksere tekstsamling for å øke hastigheten på søkeoppgaver. For eksempel ved bruk av en søkemotor. Det å finne informasjon effektivt og nøyaktig basert på søkekriterier er en viktig faktor innenfor emnet informasjonsinnhenting («information retrieval» (IR)). En invertert indeks består av to hovedelementer: vokabularet (også kjent som «lexicon» eller «dictionary») og forekomster («postings»). Vokabularet er alle ordene i en tekst, og for hvert ord i vokabularet lagrer indeksen en referanse til det dokumentet som inneholder ordet.[1]
Det finnes to hovedvarianter av inverterte indekser:
- En invertert filindeks: som inneholder en liste med referanser til dokumenter for hvert ord.[1]
- En fullstendig invertindeks: som i tillegg til en liste med referanser til dokumenter for hvert ord, også inneholder posisjonen til hvert ord i et dokument.[1]
Invertert filindeks[rediger | rediger kilde]
En invertert filindeks er som sagt en liste med referanser til dokumenter for hvert ord som forekommer. I sin enkleste form kan man representere indeksen ved hjelp av en matrise.
Her er et eksempel hvor det er tre dokumenter som inneholder litt tekst:
d1 = «it is what it is» d2 = «what is it» d3 = «it is a banana»
En kan representere det på følgende måte:
| Vokabular | η1 | d1 | d2 | d3 | |
|---|---|---|---|---|---|
| a | 1 | - | - | 1 | |
| banana | 1 | - | - | 1 | |
| is | 3 | 2 | 1 | 1 | |
| it | 3 | 2 | 1 | 1 | |
| what | 2 | 1 | 1 | - |
I tabellen ovenfor ser vi at ordene som forekommer er representert i vokabularet, mens ni illustrerer total antall forekomster av ordet i dokumenter. Vi ser for eksempel at ordet «a» kun forekommer i ett dokument, nemlig dokument d3. I de ulike dokumentene, di ser vi hvor mange ganger ordet forekommer i hvert dokument.
Skulle man bare utført en boolsk søkefunksjon ville man kun trengt en bekreftelse på om ordet eksisterte i dokumentet eller ikke. Hadde en for eksempel søkt på «a» ville man fått returnert d3 ettersom det er det eneste dokumentet som inneholder termen «a».[1][2]
Fullstendig Invertert indeks[rediger | rediger kilde]
Noe den inverterte filindeksen ikke er egnet til er det å svare på spørringer som tar forbehold om setninger eller nærhet. Dersom man for eksempel kjører en spørringer etter «New York» har ikke den inverterte filindeksen noe informasjon som sier at de to ordene kan høre sammen. Den vil trolig da returnere dokumenter som inneholder de to ordene på ulike steder i dokumentet.
Hva jeg vil ha:
d1 = «New York is the most populous city in the United States...»
Hva som kan returneres:
d2 = «I love this new place in York»
En fullstendig invert indeks tar i tillegg, til en liste med referanser til dokumenter for hvert ord, også med posisjonen til hvert ord i et dokument. La oss ta et eksempel for å vise hvordan man kan illustrere dette.
d1 = «it is what it is» d2 = «what is it» d3 = «it is a banana»
| Vokabular | η1 | Forekomster med posisjon | |
|---|---|---|---|
| a | 1 | [3, 1 [3]] | |
| banana | 1 | [3, 1 [4]] | |
| is | 3 | [1, 2[2, 5]], [2, 1[2]], [3, 1[2]] | |
| it | 3 | [1,2[1,4]], [2,1[3]], [3, 1[1]] | |
| what | 2 | [1,1[3]], [2,1[1]] |
Vi ser i følgende matrise at ordet «a» forekommer i ett dokument. Dette ser vi under tabellen η1. Under tabellen #Forekomster med posisjon» ser vi at ordet forekommer i dokument nummer 3, og her forekommer ordet kun 1 gang og ordet er på posisjon nummer 3. Tar vi derimot ordet «What» ser vi at den forekommer i to dokumenter. Det første dokumentet dette ordet forekommer i er dokument nummer 1. Her forekommer ordet 1 gang og posisjonen er 3. Neste dokument er dokument 2. Her forekommer ordet en gang på posisjon en.
Ved at vi nå har posisjonen til ordene kan vi se om flere ord som «New York» kan ha en sammenheng.[1][2]