Käänteistiedostot

Kun indeksinä käytetään tietorakennetta, jossa dokumentista löydetään ainoastaan kokonaisista sanoista (ja joskus myös sanojen alkuosista) koostuvat hahmot tai hahmojen alkupositiot, mutta ei esim. sanojen rajat ylittäviä tai sanojen sisällä olevia hahmoja, kutsutaan tietorakennatta käänteistiedostoksi. Koska käänteistiedosto sisältää vain pienen osajoukon kaikista tekstistä löytyvistä hahmoista, on käänteistiedosto merkittävästi pienempi, kuin täydellisen indeksin sisältävä loppuosapuu tai loppuosataulukko. Parhaimmillaan käänteistiedoston koko on vain 10% indeksoidun tekstin koosta. Jos avainsanat tallennetaan fyysisesti käänteistiedostoon (päinvastoin, kuin esim. loppuosataulukossa, johon tallennetaan vain loppuosien tekstipositioita), ei tallennettujen avainsanojen tarvitse enää olla täsmälleen samoja, kuin tekstistä löytyvien sanojen. Usein onkin järkevää tallentaa käänteistiedostoon sanoja vain perusmuodossa.

Käänteistiedosto koostuu kahdesta osasta:

1. Avainsanakohtaiset positiolistat, jotka sisältävät listan avainsanan esiintymien positioista tekstissä.
2. Hakutietorakenteesta, joka sisältää avainsanaindeksin, josta pystytään löytämään haetun avainsanan positiolista tehokkaasti.

Käänteistiedoston hakutietorakenne voidaan toteuttaa monella eri tavalla. Jatkossa merkitään käänteistiedostosta löytyvien uniikkien avainsanojen lukumäärä $a$:lla. Tietorakenteiden kokoja laskettaessa oletetaan, että kaikki osoittimet ovat 32-bittisiä.