Suffiksitaulukko on tietorakenne, joka ilmaisee merkkijonon suffiksien (eli loppuosien) järjestyksen. Jokainen taulukon alkio on indeksi, josta jokin suffiksi alkaa. Voimme etsiä suffiksitaulukon avulla tehokkaasti merkkijonon osajonoja.

Esimerkki

Esimerkiksi merkkijonon ABAACBAB suffiksitaulukko on [2,6,0,3,7,1,5,4]. Seuraava kuva näyttää, miten suffiksitaulukko vastaa merkkijonon suffikseja:

Tässä tapauksessa kohdasta 2 alkava suffiksi AACBAB on aakkosjärjestyksessä ensimmäinen, joten suffiksitaulukon ensimmäinen alkio on 2. Tämän jälkeen seuraavana järjestyksessä on kohdasta 6 alkava suffiksi AB, jne.

Suffiksitaulukon muodostaminen

Suffiksitaulukon muodostamiseen on kehitetty monia tehokkaita algoritmeja. Seuraavassa on melko helposti toteutettavissa oleva algoritmi, jonka aikavaativuus on O(n \log^2 n), kun n on merkkijonon pituus. Ideana on tarkastella merkkijonon osajonoja, joiden pituus on 2:n potenssi, ja antaa niille tunnuksia. Jos kaksi osajonoa ovat samat, niiden tunnus on sama.

Kierroksella k tarkastellaan osajonoja, joiden pituus on 2^{k-1}. Kierroksella 1 jokainen osajono saa tunnuksen suoraan merkkien järjestyksestä. Muilla kierroksilla tunnus muodostetaan kahdessa osassa: alustava tunnus on pari, jossa on merkkijonon vasemman ja oikean osan tunnus, ja lopullinen tunnus saadaan numeroimalla parit niiden järjestyksen mukaan. Jos oikea osa alkaa merkkijonon ulkopuolelta, niin voimme päättää, että sen tunnus on 0.

Seuraava kuva näyttää, kuinka merkkijono ABAACBAB käsitellään:

Kierroksella 1 merkkien A...C tunnukset ovat 1...3. Kierroksella 2 muodostetaan tunnukset 2-pituisille osajonoille. Esimerkiksi osajonon AB alustava tunnus on (1,2), koska sen vasemman osan A tunnus on 1 ja oikean osan B tunnus on 2. Osajonon AB lopullinen tunnus kierroksella 2 on 2, koska sitä ennen järjestyksessä on osajonoa AA vastaava pari (1,1).

Kun tällä tavalla suoritetaan \lceil \log_2 n \rceil +1 kierrosta, jokainen osajono saa erillisen tunnuksen. Yllä olevassa kuvassa kaikilla osajonoilla on erillinen tunnus jo kierroksen 3 jälkeen, eli kierros 4 ei oikeastaan olisi tarpeellinen. Lopuksi voimme päätellä suffiksitaulukon sisällön tunnuksista, koska tunnusten järjestys on sama kuin osajonojen järjestys.

Suffiksitaulukon käyttäminen

Suffiksitaulukon hyötynä on, että voimme tarkastaa sen avulla tehokkaasti, onko merkkijonossa tiettyä osajonoa. Tämä onnistuu käymällä haettava osajono läpi merkki kerrallaan ja rajaamalla binäärihaun avulla aluetta, jossa se voi esiintyä suffiksitaulukossa.

Esimerkiksi osajonon BA esiintymät löytyvät näin:

Tällainen haku vie aikaa O(k \log n), missä k on haettavan osajonon pituus. Voimme hakea tällä tavalla tehokkaasti useita osajonoja suffiksitaulukon luomisen jälkeen.