Sufiksno stablo

Из Википедије, слободне енциклопедије
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 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 orjentisano 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[уреди]