Sufiksno stablo

Sufiksno stablo predstavlja strukturu podataka koja opisuje internu strukturu stringa (niske) na vrlo iscrpan način. Sufiksno stablo može da se upotrebi da bi se rešio problem tačnog traženja za linerano vreme (postižući istu složenost u najgorem slučaju koju su postigli algoritmi KMP (Knuth-Morris-Pratt) i Bojer-Mur (Boyer-Moore), ali njihova prednost je u mogućnosti primene u algoritmima linearne složenosti za probleme sa stringovima složenijim od tačnog traženja. Štaviše, sufiksna stabla obezbeđuju most između problema tačnog traženja i približnog traženja.

Sufiksno stablo za string BANANA. Svaki podstring se završava simbolom $. Putanje od korena do lista odgovaraju sufiksima (6 sufiksa - 6 putanja) A$, NA$, ANA$, NANA$, ANANA$ i BANANA$. Brojevi u listovima označavaju početnu poziciju odgovarajućeg sufiksa.

Istorija

Autor prvog algoritma za konstrukciju sufiksnih stabala linearne vremenske složenosti je Vajner (Weiner) 1973. godine, pri čemu je on za to stablo koristio termin stablo pozicija. Drugačiji, i što se tiče štednje prostora prilikom gradnje sufiksnih stabala bolji algoritam, dao je MekKrejt (McCraight) nekoliko godina kasnije. Nakon toga, Ukonen (Ukkonen) je razvio konceptualno drugačiji linerani algoritam za izgradnju sufiksnih stabala koji ima sve prednosti MekKrejtovog algoritma (a detaljnija analiza pokazuje da se on može smatrati varijantom MekKrejtovog algoritma), ali nudi mnogo jednostavnije objašnjenje.

Ovi algoritmi su linearne vremenske složenosti za azbuke konstantne dužine, i u najgorem slučaju imaju vremensku složenost $O(n\log n)$. Farah (Farach) je 1997. osmislio prvi algoritam za konstrukciju sufiksnih stabala koji daje optimalne rezultate za azbuke bilo kojih veličina. Farahov algoritam je postao osnova za sve novije algoritame za konstrukciju sufiksnih stabala i nizova.

Definicija

Sufiksno stablo za string $S$ dužine znakova $m$ je korensko orijentisano stablo sa tačno $m$ listova numerisanih od $1$ do $m$. Svaki unutrašnji čvor različit od korena ima najmanje dva sina i svaka grana je označena nepraznim podstringom za $S$. Nikoje dve grane koje izlaze iz čvora ne mogu da imaju oznake grane koje počinju istim znakom. Pošto ne postoji sufiksno stablo koje zadovoljava datu definiciju za sve stringove, na $S$ se dodaje jedan znak za kraj, koji nije u alfabetu, najčešće A$. Ovim se osigurava da ni jedan sufiks konačnog stringa ne može da bude prefiks ni jednog drugog sufiksa. Ključna osobina kod sufiksnih stabala je ta, da za svaki list $i$, konkatenacija oznaka grana na putu od korena do lista $i$, je jednaka sufiksu $S$ koji počinje na poziciji $i$. Odnosno, da je $S[i..m]$ .

Uopšteno sufiksno stablo

Uopšteno sufiksno stablo je sufiksno stablo za više reči i sadrži sve sufikse iz te grupe reči. Svaka reč u ovakvom stablu mora biti završena različitim terminalnim simbolom ili rečju.

Složenost algoritma

Za azbuke konstantne veličine, složenost algoritma sufiksnog stabla $S$ dužine $n$ je $\Theta (n)$. Za slučaj velike azbuke složenost se povećava na $O(n\log n)$.

Složenost za azbuke konstantne veličine

Za sufiksno stablo stringa $S$ dužine $n$, ili generalizovano sufiksno stablo niza stringova $D=\{S_{1},S_{2},\dots ,S_{K}\}$ ukupne dužine $n=|n_{1}|+|n_{2}|+\cdots +|n_{K}|$ može se:

• Pretraživati
  • Da li je string $P$ dužine $m$ podstring, za vreme $O(m)$.
  • Pronaći prvo pojavljivanje sekvence stringova $P_{1},\dots ,P_{q}$ ukupne dužine $m$ kao podstringova, za vreme $O(m)$.
  • Pronaći svih z pojavljivanja sekvence stringova $P_{1},\dots ,P_{q}$ ukupne dužine $m$ kao podstringova, za vreme $O(m+z)$.
  • Tražiti regularni izraz P za vreme linearno $n$.
  • Za svaki sufiks sekvence $P$, naći dužinu najdužeg poklapanja prefiksa iz $P[i\dots m]$ sa $D$, za vreme $\Theta (m)$. Ovo se naziva statistika poklapanja za $P$
• Tražiti svojstva stringova
  • Naći najduži zajednički podstring stringova $S_{i}$ i $S_{j}$ za vreme $\Theta (n_{i}+n_{j})$.
  • Naći LZW dekompoziciju za vreme $\Theta (n)$.
  • Naći najduže ponavljajuće podstringove za vreme $\Theta (n)$.
  • Naći najponavljanije stringove odredjene dužine za vreme $\Theta (n)$.
  • Naći najkraće stringove iz $\Sigma$ koji se ne pojavljuju u $D$, za vreme $O(n+z)$, ako postoji $z$ takvih stringova.
  • Naći najkraće podstringove koji se pojavljuju samo jednom za vreme $\Theta (n)$.
  • Naći, za svako $i$, najkaraći podstring $S_{i}$ koji se ne pojavljuje nigde drugde u $D$ za vreme $\Theta (n)$.

Primene

Sufiksna stabla imaju siroku primenu u rešavanju problema pri editovanju i pretrazi teksta, kompjuterskoj biologiji i drugim oblastima. Neka od primarnih polja primene su:

• Traženje najdužeg ponavljajućeg podstringa
• Traženje najdužeg zajedničkog podstringa
• Traženje najdužeg palindorma u stringu

Jedno od osnovnih polja primene sufiksnih stabala je bioinformatika. Proučavanje genoma je u najvećoj meri zasnovano na pretraživanju stringova i nalaženju određenih uzoraka u okviru njih. Sufiksna stabla se takodje primenjuju na polju kompresije podataka i neke vrste LZW kompresije koriste sufiksna stabla (LZSS).

Konstrukcija sufiksnog stabla

Esko Ukonen (Esko Ukkonen) je napravio algoritam za konstrukciju sufiksnog stabla u linearnom vremenu koji je konceptualno najlakši algoritam za konstrukciju u linearnom vremenu.

Ukonenov algoritam konstruiše implicitno sufiksno stablo $S_{i}$ za svaki prefiks $S_{i}[1..n]$ za $S$, počevši od $I_{1}$ uvećava za i dok stablo $I_{m}$ ne bude konstruisano. Pravo sufiksno stablo $S$ za je konstruisano iz $I_{m}$ a vreme potrošeno za ceo algoritam je $O(m)$. Ukonenov algoritam inicijalno konstruiše stablo u vremenu $O(m^{3})$ da bi se konstruisala sva stabla $I_{i}$ a zatim se optimizovanjem njegove implementacije dobija vremenski nivo složenosti $O(m)$.

Osnovna struktura Ukonenovog algoritma

Konstruiše stablo $T_{i}$
for i=1 to m-1
begin {faza i+1 }
      for j=1 to i+1
            begin {produženje j}
            Polazeći od korena nalazi se kraj puta označenog sa u tekućem stablu.
            Ako je potrebno, taj put se produžava dodavanjem znaka ,
            i time osigurava da je string u stablu.
      end;
end;

Za razliku od Ukonenovog algoritma, Vajnerov algoritam počinje celim stringom $S$. Kao i kod Ukonenovog algoritma, unosi se po jedan sufiks u rastuće stablo, ali u bitno različitom rasporedu. Vajnerov algoritam konstruiše stabla od $T_{m}+1$ na dole do $T_{i}$.

Literatura

• Gusfield, Dan (1999), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press. ISBN 978-0-521-58519-4..
• McCreight, Edward M. (1976), „A Space-Economical Suffix Tree Construction Algorithm”, Journal of the ACM, 23 (2): 262—272, doi:10.1145/321941.321946 .
• Farach, Martin (1997), „Optimal Suffix Tree Construction with Large Alphabets”, 38th IEEE Symposium on Foundations of Computer Science (FOCS '97) (PDF), стр. 137—143 .
• McCreight, Edward M. (1976), „A Space-Economical Suffix Tree Construction Algorithm”, Journal of the ACM, 23 (2): 262—272, doi:10.1145/321941.321946 .
• Ukkonen, E. (1995), „On-line construction of suffix trees” (PDF), Algorithmica, 14 (3): 249—260, doi:10.1007/BF01206331 .