Indeksointi

Edellä esitetetyt hahmontunnistusalgoritmit ovat käytännöllisiä silloin, kun tekstiin tehdään hakuja harvoin tai kun teksti muuttuu usein. Jos teksti on stabiilia, mutta siihen tehdään paljon hakuja, kannattaa tekstistä muodostaa tietorakenne, joka mahdollistaa haut, joissa koko tekstiä ei tarvitse selata hahmoa etsiessä. Parhaimmillaan tekstin esiprosessoinnilla päästään tietorakenteisiin ja algoritmeihin, joilla hahmon etsimisen aikavaatimus on $O(\vert P\vert)$ tekstin pituudesta $\vert S\vert$ riippumatta. Tällaista tekstin esiprosessointia kutsutaan indeksoinniksi (engl. indexing) ja muodostettua tietorakennetta indeksiksi (engl. index). Esimerkiksi tavallisen kirjan lopusta löytyvän hakemiston voidaan ajatella olevan kirjan indeksitietorakenne.

Indeksejä on tehty jo ennen tietokoneaikaa. Kirjassa [WMB94] kerrotaan professori Lane Cooperin vuonna 1911 julkaisseen 211 000 hakusanaa sisältäneen indeksin runoilija William Wordsworthin teoksiin. Tämä indeksi valmistui seitsemässä kuukaudessa, mikä oli erittäin hyvä suoritus tuohon aikaan. Indeksiä olikin työstämässä hyvin organisoitu 67 ihmisen työryhmä. Nykyään tavallista kotimikroa ja verkosta ilmaiseksi saatavissa olevia ohjelmia käyttäen ei aikaa tällaisen indeksin muodostamiseen kuluisi kymmentä minuuttia kauempaa.

Merkitään $D(S)$:llä tekstistä $S$ muodostettua indeksitietorakennetta ja $\vert D(S)\vert$:llä indeksitietorakenteen kokoa. Tällöin hyvällä indeksillä on seuraavat ominaisuudet:

1. $\vert D(S)\vert$ on suoraan verrannollinen tekstin pituuteen $\vert S\vert$.
2. $D(S)$:n muodostamisen aikavaatimus on $O(\vert S\vert)$.
3. $D(S)$:n avulla kysymykseen "löytyykö hahmo $P$ tekstistä $S$?" voidaan vastata ajassa $O(\vert P\vert)$.
4. $D(S)$:n avulla hahmon $P$ kaikki $k$ esiintymää voidaan löytää tekstistä $O(k\vert P\vert)$ ajassa.

Usein käytännön syistä joudutaan tinkimään näistä vaatimuksista. Erityisesti indeksin tarkkuudesta tingitään: sen sijaan, että indeksistä löytyisivät kaikki kaikkien mahdollisten hahmojen esiintymät, sieltä löytyvätkin vain kokonaisten sanojen tai kokonaisten sanojen alkuosien esiintymät. Tässä tutkielmassa tällaista indeksiä kutsutaan harvaksi indeksiksi. Luvussa 5.4 esiteltävät käänteistiedostot ovat harvoja indeksejä.