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.

Rakenne

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.

Toimintaperiaate haussa

Sanakirjatiedostolla varustetusta käänteistiedostosta haku tapahtuu seuraavasti:

• sopivien hakuavainten valinta
• sanakirjatiedostosta haetaan näitä hakuavaimia vastaavat tietueet
• näitä avaimia vastaavat avain/tietuenumerolista-parit haetaan käänteistiedostosta
• hakuavaimiin liittyviä tietuenumerolistoja tutkitaan haun muotoilua vastaavalla tavalla: haettaessa kahdella avaimella (esimerkiksi apina AND navigoi), joiden molempien tulee esiintyä halutussa tietueessa, etsitään avainten apina ja navigoi tietuenumerolistojen yhteisiä tietuenumeroita
• numeroiden perusteella tietueet poimitaan perustiedostosta

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.

Kuva.1 Haku käänteistiedostosta

Päivittäminen

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:

• Tietueen hakemistoon kirjattavat hakuavaimet sekä tietuenumero poimitaan ennen tallennusta. Tietue lisätään perustiedostoon ja käänteistiedosto päivitetään.
• Jos hakuavain esiintyy käänteistiedostossa, lisätään uuden tietueen numero sen tietuenumerolistaan. Jos hakuavainta ei ole käänteistiedostossa, hakemistoon lisätään uusi hakuavain tietuenumeron kanssa.

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.

Kuva 2. Käänteistiedostoston ja sanakirjan päivitys

Lähteet

• Alaterä Anu, Halttunen Kai. 2002. Tiedonhaun perusteet - Osa lukutaitoa. Helsinki BTJ Kirjastopalvelu.
• Järvelin Kalervo. 1995. Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin. Suomen ATK-kustannus Espoo.
• Robertson S.E. 1994. Spärck Jones K. Simple, proven approaches to text retrieval. Technical Report Number 356, University of Cambridge.
• Tenopir Carol, Jung Soon Ro. 1990. Full text databases. Greenwood Press.
• Timonen Jari. 2005. Validointimenetelmien soveltaminen LSA-dimension etsintään automaattisessa esseiden arvioinnissa. Joensuun yliopisto, Tietojenkäsittelytiede, Pro gradu -tutkielma. ftp://cs.joensuu.fi/pub/Theses/2005_MSc_Timonen_Jari.pdf
• Zobel Justin, Moffat Alistair, Ramamohanarao Kotagiri. 1998. Inverted Files Versus Signature Files for Text Indexing. ACM Transactions on Database Systems, Vol. 23, No. 4.