Käänteinen indeksi

Käänteinen indeksi on tietorakenne , jossa asiakirjakokoelman jokaiselle sanalle vastaava luettelo listaa kaikki asiakirjat kokoelmassa, jossa se esiintyy. Käänteistä indeksiä käytetään tekstien etsimiseen.

Käänteisestä indeksistä on kaksi muunnelmaa:

hakemisto, joka sisältää vain luettelon asiakirjoista jokaiselle sanalle,
hakemisto, joka sisältää valinnaisesti sanan sijainnin kussakin asiakirjassa [1] .

Sovellus

Kuvataanpa, kuinka ratkaisemme ongelman löytää asiakirjoja, jotka sisältävät kaikki hakukyselyn sanat . Yksisanaista hakukyselyä käsiteltäessä vastaus on jo käänteisessä hakemistossa - ota vain sanaa vastaava lista kyselystä. Monisanaista kyselyä käsiteltäessä otetaan kutakin kyselysanaa vastaavien luetteloiden leikkauspiste.

Yleensä hakukoneissa luettelon asiakirjat asetetaan paremmuusjärjestykseen sen jälkeen, kun on luotu luettelo asiakirjoista, jotka sisältävät kyselyn sanoja käänteisen indeksin avulla . Käänteinen indeksi on suosituin tiedonhaussa käytetty tietorakenne [ 2] .

Esimerkki

Olkoon meillä kolmen tekstin korpus ja , niin käänteinen indeksi näyttää tältä: $T_{0}=$ "it is what it is" $T_{1}=$ "what is it" $T_{2}=$ "it is a banana"

"a": {2} "banaani": {2} "on": {0, 1, 2} "se": {0, 1, 2} "mitä": {0, 1}

Tässä numerot osoittavat niiden tekstien numerot, joissa vastaava sana esiintyy. Sitten "what is it"hakukyselyn käsittely antaa seuraavan tuloksen . $\{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}$

Sovellusominaisuudet oikeissa hakukoneissa

Sanan esiintymisluettelossa asiakirjoissa mainitaan yleensä dokumenttien id:n lisäksi tekijät ( TF-IDF , binääritekijä: " osuiko sana otsikkoon vai ei", muut tekijät), jotka ovat käytetään rankingissa. Hakemistoa ei voida rakentaa kaikkien sanamuotojen mukaan, vaan lemmien mukaan (sanojen kanonisten muotojen mukaan). Pysäytyssanat voidaan sulkea pois ja niille ei rakenneta hakemistoa olettaen, että jokainen niistä esiintyy lähes kaikissa korpuksen dokumenteissa. Leikkausten laskemisen nopeuttamiseksi käytetään ohitusosoittimien heuristiikkaa . Käsiteltäessä monia sanoja sisältäviä pyyntöjä käytetään quorum-toimintoa, joka hyppää seuraavaan järjestysvaiheeseen asiakirjan osan, josta ei löytynyt kaikkia pyynnön sanoja.

Katso myös

Haku hakemistosta

Kirjallisuus

Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Nykyaikainen tiedonhaku . - Reading, Massachusetts : Addison-Wesley Longman, 1999. - 192 s. — ISBN 0-201-39829-X .
Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao. Käänteiset tiedostot vs. allekirjoitustiedostot tekstin indeksointiin // ACM Transactions on Database Systems ( TODS) : Journal. - 1998. - Ei. 23 . - s. 453 - 490 . - doi : 10.1145/296854.277632 .