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.

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  . 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   dužine znakova   je korensko orijentisano stablo sa tačno   listova numerisanih od   do  . Svaki unutrašnji čvor različit od korena ima najmanje dva sina i svaka grana je označena nepraznim podstringom za  . 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   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  , konkatenacija oznaka grana na putu od korena do lista  , je jednaka sufiksu   koji počinje na poziciji  . Odnosno, da je   .

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   dužine   je  . Za slučaj velike azbuke složenost se povećava na  .

Složenost za azbuke konstantne veličineУреди

Za sufiksno stablo stringa   dužine  , ili generalizovano sufiksno stablo niza stringova   ukupne dužine   može se:

  • Pretraživati
    • Da li je string   dužine   podstring, za vreme  .
    • Pronaći prvo pojavljivanje sekvence stringova   ukupne dužine   kao podstringova, za vreme  .
    • Pronaći svih z pojavljivanja sekvence stringova   ukupne dužine   kao podstringova, za vreme  .
    • Tražiti regularni izraz P za vreme linearno  .
    • Za svaki sufiks sekvence  , naći dužinu najdužeg poklapanja prefiksa iz   sa  , za vreme  . Ovo se naziva statistika poklapanja za  
  • Tražiti svojstva stringova
    • Naći najduži zajednički podstring stringova   i   za vreme  .
    • Naći LZW dekompoziciju za vreme  .
    • Naći najduže ponavljajuće podstringove za vreme  .
    • Naći najponavljanije stringove odredjene dužine za vreme  .
    • Naći najkraće stringove iz   koji se ne pojavljuju u  , za vreme  , ako postoji   takvih stringova.
    • Naći najkraće podstringove koji se pojavljuju samo jednom za vreme  .
    • Naći, za svako  , najkaraći podstring   koji se ne pojavljuje nigde drugde u   za vreme  .

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   za svaki prefiks   za  , počevši od   uvećava za i dok stablo   ne bude konstruisano. Pravo sufiksno stablo   za je konstruisano iz   a vreme potrošeno za ceo algoritam je  . Ukonenov algoritam inicijalno konstruiše stablo u vremenu   da bi se konstruisala sva stabla   a zatim se optimizovanjem njegove implementacije dobija vremenski nivo složenosti  .

Osnovna struktura Ukonenovog algoritmaУреди

Konstruiše stablo  
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  . 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   na dole do  .

LiteraturaУреди