Käänteistiedosto
Käänteistiedosto (käytetään myös termejä käänteishakemisto ja käänteisrakenne) on tietokanta, johon kerätään tiedostossa esiintyvät hakuavaimet ja niiden esiintymiin viittaavat linkit. Käänteistiedostoa käytetään tiedonhakuun etenkin tekstitietoa sisältävissä tietokannoissa.
Käänteistiedostoja käytetään hakuoperaatioihin, sillä haku peräkkäistiedostoista on hyvin hidasta. Käänteistiedostosta hakeminen on nopeaa, koska järjestelmä tekee haun aakkostetusta hakusanaluettelosta sen sijaan, että hakisi tiedon koko peräkkäistiedostosta.
Käänteistiedosto on keskeinen tiedostorakenne nykyisissä kaupallisissa tekstitietokannoissa: lähes kaikki hakujärjestelmät käyttävät sitä. Esimerkiksi nimikirjoitustiedostoon verrattuna käänteistiedostot ovat ylivoimaisesti parempia lähes joka osa-alueella, kuten nopeudessa, tilan tarpeen vähyydessä ja toiminnallisuudessa.
Käänteistiedosto muodostetaan poimimalla peräkkäistiedoston kaikista tietueista hakuavaimet ja listaamalla ne yhdessä tietueen numeron kanssa listaksi. Hakuavaimia voidaan poimia joko yhdestä tai useammasta kentästä.
Hakuavaimiksi poimitaan yleensä tietueiden kaikki sanat. Osa yleisimmistä sanoista poistetaan sulkusanalistan avulla järjestelmän tehokkuuden parantamiseksi Suomenkielisiä sulkusanoja ovat esimerkiksi ja, tai, että, mutta.
Hakuavain-tietuenumerolista lajitellaan hakuavainten mukaan nousevaan järjestykseen.
Samat hakuavaimet yhdistetään yhdeksi hakuavaimeksi, ja niihin viittaavat tietuenumerot listataan hakuavaimen yhteyteen. Tuloksena on käänteistiedosto, jossa jokaisesta hakuavaimesta kerrotaan sen kaikkien esiintymien osoitteet tiedoston tietueissa.
Käänteistiedostoja voidaan muodostaa eri kenttien perusteella (esim. otsikko, tekijä, asiasanat) tai useita kenttiä sisältävinä sekakäänteistiedostoina. Sekakäänteistiedoston hakuavaimiin liitetään kenttätunniste, eli tieto siitä, missä perustiedoston kentässä hakuavain esiintyy.
Käänteistiedoston ja perustiedoston koot ovat usein samat, mutta erilaisen tiedostorakenteensa vuoksi käänteistiedostosta on huomattavasti nopeampaa hakea, kuin perustiedostosta.
Sanakirjatiedostolla varustetusta käänteistiedostosta haku tapahtuu seuraavasti:
Hakumenettelyä havainnollistetaan kuvassa 1. Oletetaan, että perustiedosto on muodostettu vaikka lastenkirjojen nimistä. Niistä on muodostettu myös sanakirjatiedosto sekä käänteistiedosto. Muista kentistä (tekijä, asiasanat, jne) tehdään lisähakemistot, mutta tarkastellaan tässä vain nimikekenttää. Hakuavaimina ovat apina ja navigoi. Suurta perustiedostoa ei yleensä tarvitse tutkia ennen kuin on selvitetty, mitkä sen tietueista täyttävät hakuehdot. Perustiedosto saattaa sisältää jopa miljoonia tietueita, mutta tällä hakumenettelyllä sieltä ei tarvitse poimia kuin nämä tietueet. Näin hakuajat jäävät enintään muutaman sekunnin mittaisiksi.
Hakuavaimien syötön jälkeen esiintymien lukumäärätieto haussa saadaan suoraan sanakirjatiedostosta. Hakuohjelma voi hakea käänteistiedoston vastaavat tietueet valmiiksi työmuistiin sillä aikaa kun esiintymien lukumäärätietoa haetaan, mikä vie suhteellisen kauan. Tuloksena saatava tieto hakuehdon apina JA navigoi osumien määrästä, vaatii käänteistiedoston tutkimista. Tällöin joudutaan vertaamaan hakuavaimiin apina ja navigoi liittyviä tietuenumerolistoja.
Käänteistiedostoa ja sanakirjatiedostoa käyttävän tietokannan päivittäminen on työlästä. Perustiedoston päivittämisen lisäksi täytyy päivittää myös kaikki lisähakemistot ja sanakirjatiedostot, joita muutokset koskevat.
Uuden tietueen lisääminen tapahtuu seuraavasti:Kuvassa 2 esitetään kuvan 1 päivitetty käänteistiedosto tietueen numero 10 lisäyksen jälkeen. Tietue numero 10 sisälsi hakuavaimet "apina", "syö" ja "puussa". Näin ollen tietuenumero 10 tulee lisätä näiden avainten tietoihin käänteistiedostossa ja kasvattaa näiden avainten esiintymälukumäärää yhdellä sanakirjatiedostossa. Hakusanaa "syö" ei ennestään ollut tietokannassa, joten täytyy se lisätä sekä käänteis- että sanakirjatiedostoon. Tietueen poisto ja muutos tapahtuu samalla tavalla, päivittäen myös käänteis- ja sanakirjatiedosto.