Uopšteno sufiksno stablo

U informatici, uopšteno sufiksno stablo je sufiksno stablo za skup niski. Za dati skup niski $D=S_{1},S_{2},\dots ,S_{d}$ ukupne dužine $n$ , to je radiks stablo koje sadrži svih $n$ sufiksa niski. Uglavnom se koristi u bioinformatici.^[1]

Funkcionisanje

Stablo se može konstruisati u $\Theta (n)$ vremenskoj i prostornoj složenosti i može se iskoristiti da se pronađe svih $z$ pojavljivanja niske $P$ dužine $m$ u $O(m+z)$ vremenu, što je asimptotski optimalno (pod uslovom da je veličina azbuke konstantna, videti ^[2], pp. 119).

Prilikom pravljenja ovakvog drveta, svaka niska mora biti ograničena jedinstvenim označavajućim simbolom (ili niskom) koji je van azbuke, kako bi se osiguralo da nijedan sufiks nije podniska neke druge, garantujući da je svaki sufiks predstavljen jedinstvenim lisnim čvorom.

Algoritmi za pravljenje UST uključuju Ukonenov algoritam (1993) i MekKrejtov algoritam (1976).

Primer

Sufiksno stablo za niske ABAB i BABA je prikazano na gornjoj slici. Ograničene su jedinstvenim završnim niskama $0 i $1. Brojevi u lisnim čvorovim su broj niske i početnu poziciju. Uočite kako prolaz kroz lisne čvorove sleva udesno odgovara sortiranom poretku sufiksa. Krajevi se mogu označiti niskama ili jedinstvenim simbolima. Grane ka $ od korena nisu prikazane u ovom primeru.

Alternative

Alternativa za pravljenje uopštenog sufiksnog stabla je da se niske spoje u jednu, a potom da se napravi obično sufiksno drvo ili sufiksni niz za rezultujuću nisku. Kada se pronalasci ocenjuju nakon pretrage, globalne pozicije se mapiraju unutar dokumenata, a lokalne pozicije uz pomoć nekog algoritma i/ili strukture podataka, kao što je binarna pretraga od početka ili kraja dokumenta.

Reference

^ Lucas Chi Kwong Hui (1992). „Color Set Size Problem with Applications to String Matching”. Combinatorial Pattern Matching, Lecture Notes in Computer Science, 644. str. 230—243. ^{[mrtva veza]}
^ Paul Bieganski; John Riedl; John Carlis & Ernest F. Retzel (1994). „Generalized Suffix Trees for Biological Sequence Data”. Biotechnology Computing, Proceedings of the Twenty-Seventh Hawaii International Conference on. str. 35—44.
^ Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

[1]

[2]