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.

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 ${\displaystyle 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 ${\displaystyle S}$ dužine znakova ${\displaystyle m}$ je korensko orijentisano stablo sa tačno ${\displaystyle m}$ listova numerisanih od ${\displaystyle 1}$ do ${\displaystyle m}$. Svaki unutrašnji čvor različit od korena ima najmanje dva sina i svaka grana je označena nepraznim podstringom za ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle i}$, konkatenacija oznaka grana na putu od korena do lista ${\displaystyle i}$, je jednaka sufiksu ${\displaystyle S}$ koji počinje na poziciji ${\displaystyle i}$. Odnosno, da je ${\displaystyle 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 ${\displaystyle S}$ dužine ${\displaystyle n}$ je ${\displaystyle \Theta (n)}$. Za slučaj velike azbuke složenost se povećava na ${\displaystyle O(n\log n)}$.

Složenost za azbuke konstantne veličine

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

• Pretraživati
  • Da li je string ${\displaystyle P}$ dužine ${\displaystyle m}$ podstring, za vreme ${\displaystyle O(m)}$.
  • Pronaći prvo pojavljivanje sekvence stringova ${\displaystyle P_{1},\dots ,P_{q}}$ ukupne dužine ${\displaystyle m}$ kao podstringova, za vreme ${\displaystyle O(m)}$.
  • Pronaći svih z pojavljivanja sekvence stringova ${\displaystyle P_{1},\dots ,P_{q}}$ ukupne dužine ${\displaystyle m}$ kao podstringova, za vreme ${\displaystyle O(m+z)}$.
  • Tražiti regularni izraz P za vreme linearno ${\displaystyle n}$.
  • Za svaki sufiks sekvence ${\displaystyle P}$, naći dužinu najdužeg poklapanja prefiksa iz ${\displaystyle P[i\dots m]}$ sa ${\displaystyle D}$, za vreme ${\displaystyle \Theta (m)}$. Ovo se naziva statistika poklapanja za ${\displaystyle P}$
• Tražiti svojstva stringova
  • Naći najduži zajednički podstring stringova ${\displaystyle S_{i}}$ i ${\displaystyle S_{j}}$ za vreme ${\displaystyle \Theta (n_{i}+n_{j})}$.
  • Naći LZW dekompoziciju za vreme ${\displaystyle \Theta (n)}$.
  • Naći najduže ponavljajuće podstringove za vreme ${\displaystyle \Theta (n)}$.
  • Naći najponavljanije stringove odredjene dužine za vreme ${\displaystyle \Theta (n)}$.
  • Naći najkraće stringove iz ${\displaystyle \Sigma }$ koji se ne pojavljuju u ${\displaystyle D}$, za vreme ${\displaystyle O(n+z)}$, ako postoji ${\displaystyle z}$ takvih stringova.
  • Naći najkraće podstringove koji se pojavljuju samo jednom za vreme ${\displaystyle \Theta (n)}$.
  • Naći, za svako ${\displaystyle i}$, najkaraći podstring ${\displaystyle S_{i}}$ koji se ne pojavljuje nigde drugde u ${\displaystyle D}$ za vreme ${\displaystyle \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 ${\displaystyle S_{i}}$ za svaki prefiks ${\displaystyle S_{i}[1..n]}$ za ${\displaystyle S}$, počevši od ${\displaystyle I_{1}}$ uvećava za i dok stablo ${\displaystyle I_{m}}$ ne bude konstruisano. Pravo sufiksno stablo ${\displaystyle S}$ za je konstruisano iz ${\displaystyle I_{m}}$ a vreme potrošeno za ceo algoritam je ${\displaystyle O(m)}$. Ukonenov algoritam inicijalno konstruiše stablo u vremenu ${\displaystyle O(m^{3})}$ da bi se konstruisala sva stabla ${\displaystyle I_{i}}$ a zatim se optimizovanjem njegove implementacije dobija vremenski nivo složenosti ${\displaystyle O(m)}$.

Osnovna struktura Ukonenovog algoritma

Konstruiše stablo ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle T_{m}+1}$ na dole do ${\displaystyle T_{i}}$.

Literatura