Niz sufiksa

U računarskoj nauci, niz sufiksa je sortirani niz svih sufiksa stringa. To je struktura podataka koja se koristi, između ostalog, u indeksima kompletnog teksta, algoritmi za kompresiju podataka unutar polja bioinformatike.

Suffix array
Tip	Array
Smislili	Manber & Myers 1990
Time complexity in big O notation
Prosek	Najgori slučaj
Vreme	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$
Konstrukcija	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$

Nizovi sufiksa su predstavili Manber & Myers 1990 kao jednostavnu, prostorno efikasnu alternativu sufiks drvima. Nezavisno su otkrivene od strane Gaston Gonnet u 1987 pod imenom PAT niz.

Definicija

Neka je $S=S[1]S[2]...S[n]$ string i neka je $S[i,j]$ označi podstring od $S$ koje je od $i$ do $j$.

Niz sufiksa $A$ od $S$ je sada definisan kao niz celih brojeva koji daju startne pozicije sufiksima od $S$ u leksikografskom redu. Ovo znači, da ulaz $A[i]$ sadrži startnu poziciju od $i$-tog najmanjeg sufiksa u $S$ i tako za svako $1<i\leq n$: $S[A[i-1],n]<S[A[i],n]$.

Primer

Uzmite u obzir tekst $S$=banana$ da je indeksiran:

Tekst se završava specijalnim stražarskim znakom $ koji je poseban i leksikografski manji od bilo kog drugog karaktera. Tekst ima sledeće sufikse:

Suffix	i
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

Sufiksi mogu biti poređani u rastućem poretku:

Suffix	i
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

Niz sufiksa $A$ sadrži startne pozicije ovih sortiranih sufiksa: Niz sufiksa sa sufiksaima ispisanim vertikalno ispod radi jasnoće: Na primer, $A[3]$ sadrži vrednost 4, i premda referira na sufiks koji počinje na poziciji 4 unutar $S$, što je sufiks ana$.

Povezanost sa sufiks drvima

Nizvi sufiksa su usko povezani sa sufiks drvima:

• Nizovi sufiksa mogu da se konstruišu izvođenjem prelaza prvo u dubinu na drvetu sufiksa. Niz sufiksa odgovara oznakama listova datim u redu u kome su posećene tokom prolaska, ako su ivice posećene u leksikografskom redu njihovog prvog karaktera.
• Sufiks drvo može da se konstruiše u linearnom vremenu korišćenjem kombinacije sufiksa i LCP niza. Za opis algoritma, pogledajte odgovarajući deo u  LCP array članku.

Pokazano je da svaki algoritam sufiks drveta može sistematski da se zameni sa algoritmom koji koristi sufiks nizove koji ima dodatne informacije (kao LCP niz) i rešava isti problem u istoj vremenskoj kompleksnosti. Prednosti nizova sufiksa nad drvima sufiksa su poboljšani prostorni zahtevi, jednostavniji algoritmi u linearnom vremenu (tj., u poređenju sa Ukonenovim algoritmom) i poboljšana lokalnost keša.

Prostorna efikasnost

Nizove sufiksa su uveli Manber & Myers 1990 da bi poboljšali zahteve prostora sufiks drveća: Nizovi sufiksa čuvaju $n$ celih brojeva. Pretpostavljajući da ceo broj zahteva 4 bajta, niz sufiksa zahteva $4n$ bajtova ukupno. Ovo je drastično manje od $20n$ bajtova koji su potrebni za imlementaciju preciznog drveta sufiksa.

Međutim, u određenim priimenama, prostorni zahtevi nizova sufiksa mogu da budu previsoki. Analizirano u bitovima, niz sufiksa zahteva ${\mathcal {O}}(n\log n)$ prostora, a originalni tekst iz alfabeta veličine $\sigma$ zahteva samo ${\mathcal {O}}(n\log \sigma )$ bitova. Za ljudski genom sa $\sigma =4$ and $n=3.4\times 10^{9}$ niz sufiksa bi prema tome okupirao 16 puta više memorije nego sam genom.

Ovakva odstupanja su pokrenula trend prema kompresovanim nizovima sufiksa i BWT-zasnovanim celotekstualnim indeksima kao što je FM-index. Ove strukture podataka zahtevaju samo prostor unutar veličine teksta ili čak i manje.

Konstrukcioni algoritmi

Sufiks drvo može da se napravi u ${\mathcal {O}}(n)$ i može biti konvertovan u niz sufiksa prelaženjem drveta prvo u dubinu takođe u  ${\mathcal {O}}(n)$, tako da postoje algoritmi koji mogu da izgrade niz sufiksa u ${\mathcal {O}}(n)$.

Naivni pristup za izgradnju niza sufiksa je korišćenjem algoritma za sortiranje koji je zasnovan na poređenju. Ovi algoritmi zahtevaju  ${\mathcal {O}}(n\log n)$ sufiks poređenja, ali poređenje sufiksa radi u ${\mathcal {O}}(n)$ vremenu, tako da je ukupno vreme ovog pristupa ${\mathcal {O}}(n^{2}\log n)$.

Napredniji algoritmi uzimaju u korist činjenicu da sufiksi koji trebaju da se sortiraju nisu arbitrarni stringovi nego su povezani međuobno. Ovi algoritmi teže da dostignu sledeće ciljeve:

• minimalnu asimptotsku kompleksnost $\Theta (n)$
• lakoću u prostoru, što znači malo ili bez radne memorije pored teksta i niza sufiksa
• brzinu u praksi

Jedan od prvih algoritama koji su postigli sve ciljeve je SA-IS algoritam koji su napravili Nong, Zhang & Chan 2009. Algoritam je takođe jednostavan (< 100 LOC) i može biti nadograđen da istovremeno konstruiše LCP niz.  SA-IS algoritam je jedan od najbržih poznatih algoritama za konstrukciju niza sufiksa. Pažljiva implementacija implementation by Yuta Mori Arhivirano na sajtu Wayback Machine (26. jul 2014) prevazilazi većinu drugih linearnih ili super-linearnih pristupa konstrukciji.

Pored vremenskih i prostornih zahteva, algoritmi za konstrukciju nizova sufiksa takođe variraju u zavisnosti od alfabeta koji podržavaju: konstantni alfabeti su alfabeti čija je veličina vezana za konstantu, celobrojni alfabeti gde su karakteri celi brojevi u rasponu zavisnom od $n$ i generalni alfabeti gde su samo poređenja karaktera dozvoljena.[6]

Većina algoritama za konstrukciju nizova sufiksa je zasnovano na sledećim pristupima:

• Algoritmi dupliranja prefiksa su zasnovani na strategiji Karp, Miller & Rosenberg 1972. Ideja je da se nađu prefiksi koji poštuju leksikografsko slaganje sufiksa. Pretpostavljena dužina prefiksa se duplira u svakoj iteraciji algoritma dok prefiks ne postane poseban i donese rang povezanog sufiksa.
• Rekurzivni algoritmi prate pristup algoritama konstrukcije sufiks drveta koje je napravio Farach 1997 da bi rekurzivno sortirali podset sufiksa. Podset se onda koristi da zaključi niz sufiksa za preostale sufikse. Oba od ovih nizova sufiksa se spajaju da bi izračunali konačni niz sufiksa.
• Algoritmi za indukovano kopiranje su slični rekurzivnim algoritmima u smislu da koriste već sortiran podset da indukuje brzo sortiranje preostalih sufiksa. Razlika je u tome što ovi algoritmi služe iteraciju nad rekurzijom da bi sortirali označeni podset sufiksa. Anketa ove raznolike grupe algoritama je spojena od strane Puglisi, Smyth & Turpin 2007.

Poznati rekurzivni algoritam za celobrojne alfabete je DC3 / skew algoritam koji su napravili Kärkkäinen & Sanders (2003). Radi u linearnom vremenu i uspešno je korišćen kao bazična paralela i eksterna memorija algoritama za konstrukciju nizova sufiksa.

Skorašnji rad Salson et al. (2009) predlaže algoritam za obnavljanje niza sufiksa teksta koji je editovan umesto da se stvara novi niz sufiksa od početka. Čak i u teoretskoj vremenskoj kompleksnosti je brzina ${\mathcal {O}}(n\log n)$, izgleda da radi dobro u praksi: eksperimentalni rezultati autora su pokazali da je njihova implementacija dinamičkih nizova sufiksa generalno efikasnija nego ponovno pravljenje ubacivanja nekoliko slova u originalni tekst.

Primene

Niz sufiksa stringa može biti korišćen kao indeks da se brzo locira svaka pojava obrasca podstringa $P$ unutar stringa $S$. Pronalaženje svake pojave obrasca je ekvivalentno traženju svakog sufiksa koji počinje sa podstringom. Zahvaljujući leksikografskom raspoređivanju, ovi sufiksi se grupišu zajedno u niz sufiksa i mogu da se efiksano pronađu uz dva binarna pretraživanja. Prvo pretraživanje locira početnu poziciju intervala, a druga određuje poziciju kraja:

    def search(P):
        l = 0; r = n
        while l < r:
            mid = (l+r) / 2
            if P > suffixAt(A[mid]):
                l = mid + 1
            else:
                r = mid
        s = l; r = n
        while l < r:
            mid = (l+r) / 2
            if P < suffixAt(A[mid]):
                r = mid
            else:
                l = mid + 1
        return (s, r)

Traženje obrasca podstringa $P$ dužine $m$ u stringu $S$ dužine $n$ zahteva ${\mathcal {O}}(m\log n)$ vremena, uz to da jedna komparacija sufiksa treba da uporedi $m$ karaktera. Manber & Myers (1990) opisuju kako granica može da se poboljša na ${\mathcal {O}}(m+\log n)$ vremena korišćenjem LCP informacija. Ideja je da poređenje obrazaca ne mora da ponovo upoređuje određene karaktere, kada se već zna su deo najdužeg čestog prefiksa obrasca i trenutnog intervala pretraživanja. Abouelhoda, Kurtz & Ohlebusch (2004) su poboljšali granicu još dalje i dostigli vreme pretraživanja ${\mathcal {O}}(m)$ poznatog iz sufiks drveća.

Algoritmi za sortiranje sufiksa mogu da se koriste za izračunavanje Burrows–Wheeler transform (BWT). BWT zahteva sortiranje svih cikličnih permutacija stringa. Ako se ovaj string završava posebnim karakterom koji je leksikografski manji od svih drugih (tj., $), onda red sortirane rotirane BWT matrice korespondira redu sufiksa u nizu sufiksa. BWT premda može da bude izračunata u linearnom vremenu prvo konstruišući niz sufiksa teksta, a zatim dedukovanjem BWT stringa: $BWT[i]=S[A[i]-1]$.

Nizovi sufiksa mogu takođe da se koriste za traženje podstringova u Example-Based Machine Translation, tražeći mnogo manje prostora nego puna phrase table koja se koristi u Statistical machine translation.

Mnogo dodatnih primena nizova sufiksa zahteva LCP array. Neke od ovih su opisani u application section.

Reference

• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). „Replacing suffix trees with enhanced suffix arrays”. Journal of Discrete Algorithms. 2: 53—86. doi:10.1016/S1570-8667(03)00065-0. 
• Manber, Udi; Myers, Gene (1993). „Suffix Arrays: A New Method for On-Line String Searches”. SIAM Journal on Computing. 22 (5): 935—948. doi:10.1137/0222058. 
• Manber, Udi; Myers, Gene (1993). „Suffix Arrays: A New Method for On-Line String Searches”. SIAM Journal on Computing. 22 (5): 935—948. S2CID 5074629. doi:10.1137/0222058. 
• Kurtz, Stefan (1999). „Reducing the space requirement of suffix trees”. Software: Practice and Experience. 29 (13): 1149—1171. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O. 
• Algorithms in Bioinformatics. Lecture Notes in Computer Science. 2452. 2002. str. 449. ISBN 978-3-540-44211-0. S2CID 5138708. doi:10.1007/3-540-45784-4. 
• Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). „A taxonomy of suffix array construction algorithms”. ACM Computing Surveys. 39 (2): 4. S2CID 2653529. doi:10.1145/1242471.1242472. 
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). „Linear Suffix Array Construction by Almost Pure Induced-Sorting”. 2009 Data Compression Conference. str. 193—202. ISBN 978-0-7695-3592-0. S2CID 14123069. doi:10.1109/DCC.2009.42. 
• Fischer, Johannes . Inducing the LCP-Array. Algorithms and Data Structures. Lecture Notes in Computer Science. . doi:10.1007/978-3-642-22300-6 32 .  . . 2011. str. 374. ISBN 978-3-642-22299-3. 
• Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). „Dynamic extended suffix arrays”. Journal of Discrete Algorithms. 8 (2): 241—257. doi:10.1016/j.jda.2009.02.007. 
• Burkhardt, Stefan; Kärkkäinen, Juha . Fast Lightweight Suffix Array Construction and Checking. Combinatorial Pattern Matching. Lecture Notes in Computer Science. . doi:10.1007/3-540-44888-8 5 .  . . 2003. str. 55. ISBN 978-3-540-40311-1. 
• Farach, M. (1997). „Optimal suffix tree construction with large alphabets”. Proceedings 38th Annual Symposium on Foundations of Computer Science. str. 137—143. ISBN 0-8186-8197-7. S2CID 123355749. doi:10.1109/SFCS.1997.646102. 
• Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). „Rapid identification of repeated patterns in strings, trees and arrays”. Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. str. 125—136. S2CID 16652988. doi:10.1145/800152.804905. 
• Kärkkäinen, Juha; Sanders, Peter . Simple Linear Work Suffix Array Construction. Automata, Languages and Programming. Lecture Notes in Computer Science. . doi:10.1007/3-540-45061-0 73 .  . . 2003. str. 943. ISBN 978-3-540-40493-4. 
• Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). „Better external memory suffix array construction”. ACM Journal of Experimental Algorithmics. 12: 1—24. S2CID 12296500. doi:10.1145/1227161.1402296. 
• Kulla, Fabian; Sanders, Peter (2007). „Scalable parallel suffix array construction”. Parallel Computing. 33 (9): 605—612. doi:10.1016/j.parco.2007.06.004. 

Spoljašnje veze

• Suffix Array in Java
• Suffix sorting module for BWT in C code
• Suffix Array Implementation in Ruby
• Suffix array library and tools
• Project containing various Suffix Array c/c++ Implementations with a unified interface
• A fast, lightweight, and robust C API library to construct the suffix array
• Suffix Array implementation in Python
• Linear Time Suffix Array implementation in C using suffix tree