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. Alaterä Anu, Halttunen Kai, "Tiedonhaun perusteet - Osa lukutaitoa.". Helsinki BTJ Kirjastopalvelu, 2002, sivu 31. Käänteistiedostosta hakeminen on nopeaa, koska järjestelmä tekee haun aakkostetusta hakusanaluettelosta sen sijaan, että hakisi tiedon koko peräkkäistiedostosta. Tenopir Carol, Jung Soon Ro, "Full text databases.". Greenwood Press, 1990, sivut 52-53.

Käänteistiedosto on keskeinen tiedostorakenne nykyisissä kaupallisissa tekstitietokannoissa: lähes kaikki hakujärjestelmät käyttävät sitä. Järvelin Kalervo, "Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin.". Suomen ATK-kustannus Espoo, 1995, sivu 96. Esimerkiksi nimikirjoitustiedostoon verrattuna käänteistiedostot ovat ylivoimaisesti parempia lähes joka osa-alueella, kuten nopeudessa, tilan tarpeen vähyydessä ja toiminnallisuudessa. Zopel Justin, Moffat Alistair, Ramamohanarao Kotagiri, "Inverted Files Versus Signature Files for Text Indexing", ACM Transactions on Database Systems, Vol. 23, No. 4, 1998, sivu 454.

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. Tenopir Carol, Jung Soon Ro, "Full text databases.". Greenwood Press, 1990, sivu 55. Osa yleisimmistä sanoista poistetaan sulkusanalistan avulla järjestelmän tehokkuuden parantamiseksi Robertson S.E., Spärck Jones K., "Simple, proven approaches to text retrieval", Technical Report Number 356, University of Cambridge, 1994. Suomenkielisiä sulkusanoja ovat esimerkiksi ja, tai, että, mutta. Timonen Jari, "Validointimenetelmien soveltaminen LSA-dimension etsintään automaattisessa esseiden arvioinnissa.". Joensuun yliopisto, Tietojenkäsittelytiede, Pro gradu -tutkielma, 16.2.2005. Viitattu 8.12.2011

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. Järvelin Kalervo, "Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin.". Suomen ATK-kustannus Espoo, 1995, sivu 97.

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 Järvelin Kalervo, "Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin.". Suomen ATK-kustannus Espoo, 1995, sivut 101-102.

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. Järvelin Kalervo, "Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin.". Suomen ATK-kustannus Espoo, 1995, sivu 102.

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.

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. Järvelin Kalervo, "Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin.". Suomen ATK-kustannus Espoo, 1995, sivu 105.

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. Järvelin Kalervo, "Tekstitiedonhaku tietokannoista - Johdatus periaatteisiin ja menetelmiin.". Suomen ATK-kustannus Espoo, 1995, sivu 106.

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.

Viitteet

Luokka:Tiedonhaku