Sufiksni niz

U informatici, sufiksni niz je sortirani niz svih sufiksa niske. To je jednostavna, ali moćna struktura podataka koja se koristi, između ostalog, u tekstu punom indeksa, pri kompresiji podataka i algoritmima iz oblasti bioinformatike. Sufiksni nizovi su uvedeni od strane Manbera i Majersa (1990) kao jednostavna i po prostoru efikasna alternativa sufiksnih stabala. Ona su nezavisno otkrivena od strane Gonet, Baeza-Iates, Snajder (1992) pod imenom PAT niz.

Definicija

Neka je $S=s_{1},s_{2},...,s_{n}$ niska i neka $S[i,j]$ označava podnisku od $S$ u rasponu od $i$ do $j$.

Sufiksni niz $A$ od $S$ je sada definisan da bude niz celih brojeva koji pružaju početne pozicije nastavaka od $S$ u leksikografskom poretku. To znači da, unos $A[i]$ sadrži početnu poziciju $i$-tog najmanjeg sufiksa u $S$ i tako za sve $1<i\leq n$: $S[A[i-1],n]<S[A[i],n]$.

Primer

Nisku $S=banana\$$ ćemo indeksirati kao:

i	1	2	3	4	5	6	7
S[i]	b	a	n	a	n	a	$

Tekst se završava sa posebnim terminirajućim slovom $ koji je jedinstven 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

Ove sufikse sortiramo:

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

Sufiksni niz $A$ sadrži startne pozicije ovih sortiranih sufiksa:

i	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3

Kompletan niz sa sufiksima:

1	$	a	a	a	b	n	n
2		$	n	n	a	a	a
3			a	a	n	$	n
4			$	n	a		a
5				a	n		$
6				$	a
7					$

Tako na primer, $A[3]$ sadrži vrednost $4$, i stoga odnosi se na sufiks koji počinje na poziciji $4$ u $S$, što je sufiks $ana\$$.

Prebacivanje u sufiksna stabla

Sufiksni nizovi su tesno povezani sa sufiksnim stablima:

• Sufiksni nizovi mogu biti konstruisani prolaskom po dubini DFS kroz sufiksno stablo. Sufiksni niz odgovara obeležjima listova koji se dobiju u redosledu kojim su oni posećeni tokom prolaza, ako su rubovi posećeni u leksikografskim redosledu njihovog prvog karaktera.
• Sufiksno stablo može biti izgrađeno u linearnom vremenu korišćenjem kombinacije sufiksa i LCP niza.

Pokazano je da se svaki algoritam za sufiksna stabla može sistematski zameniti sa algoritmom koji koristi sufiksni niz unapređen sa dodatnim informacijama (kao što je LCP niz) i rešava isti problem za istu vremensku složenost. Prednosti sufiksnih nizova u odnosu na sufiksna stabla obuhvataju poboljšanje prostorne složenosti, jednostavnija izgradnja algoritma u linearnom vremenu (npr. u odnosu na Ukonenov algoritam) i poboljšanje lokalizacije keša.

Prostorna efikasnost

Sufiksni nizovi su uvedeni od strane Manbera i Majersa (1990) u cilju poboljšanja prostornih zahteva sufiksnih stabala: Sufiksni nizovi smeštaju $n$ celih brojeva. Pod pretpostavkom da ceo broj zahteva 4 bajta, sufiksni niz zahteva $4n$ bajtova ukupno. To je znatno manje od $20n$ bajtova koji se zahtevaju pažljivom implementacijom sufiksnog stabla. Međutim, u pojedinim aplikacijama, prostorni zahtevi sufiksnih nizova i dalje mogu biti previsoki. Analizirano u bitovima, sufiksni niz zahteva ${\mathcal {O}}(n\log n)$ prostora, dok originalni tekst preko azbuke veličine $\sigma$ zahteva samo ${\mathcal {O}}(n\log \sigma )$ bitova. Za ljudski genom sa $\sigma =4$ i $n=3.4\times 10^{9}$ sufiksni niz bi stoga zauzimao oko 16 puta više memorije nego sam genom.

Algoritmi za konstrukciju

Naivan pristup za izgradnju sufiksnog niza je da se koristi neki od algoritama sortiranja zasnovanih na poređenju. Ovi algoritmi zahtevaju ${\mathcal {O}}(n\log n)$ poređenja sufiksa, ali poređenje sufiksa radi u ${\mathcal {O}}(n)$ vremenu, tako da je ukupno vreme izvršavanja putem ovog pristupa je ${\mathcal {O}}(n^{2}\log n)$.

Napredniji algoritmi koriste činjenicu da sufiksi koji treba da budu sortirani nisu proizvoljne niske, ali su međusobno povezani. Ovi algoritmi nastoje da postignu sledeće ciljeve:

• minimalna asimptotska složenost $\Theta (n)$
• lagan u prostoru, što znači malo ili nimalo radne memorije pored teksta i koliko je potrebno samom sufiksnom nizu
• brz u praksi

Jedan od prvih algoritama za postizanje svih ciljeva je SA-IS algoritam autora Nong, Žang, Can (2009). Algoritam je takođe prilično jednostavan (< 100 linija koda) i može se povećati da istovremeno izgradi i LCP niz. SA-IS algoritam je jedan od najbržih poznatih algoritama za izgradnju sufiksnog niza. Pažljiva implementacija od Juta Mori Arhivirano na sajtu Wayback Machine (26. jul 2014) nadmašuje većinu drugih linearnih ili super-linearnih pristupa izgradnje.

Pored vremenskih i prostornih zahteva, algoritmi za izgradnju sufiksnog niza se takođe razlikuju po azbuci koju podržavaju: konstanta azbuka gde je veličina azbuke vezana stalnom, celobrojnom azbukom gde su karakteri celi brojevi u opsegu u zavisnosti od $n$ i opšte azbuke gde su dozvoljena samo poređenja karaktera.

Većina algoritama za izgradnju sufiksnog niza su zasnovani na jednom od sledećih pristupa:

• Algoritmi sa dupliranjem prefiksa su zasnovani na strategiji Karp, Miller & Rosenberg 1972. Ideja je da se pronađu prefiksi koji poštuju leksikografski redosled sufiksa. Procenjuje se dužina dupliranog prefiksa u svakoj iteraciji algoritma dok je prefiks jedinstven i pruža rang pridruženog sufiksa.
• Rekurzivni algoritmi prate pristup algoritama za izgradnju sufiksnih stabala po Farach 1997 za rekurzivno sortiranje podskupa sufiksa. Ovaj podskup se onda koristi za zaključivanje sufiksnog niza preostalih sufiksa. Oba od ovih sufiksnih nizova se onda spajaju i čine konačni sufiksni niz.
• Algoritmi za indukovano kopiranje su slični rekurzivnim algoritmima u smislu da oni koriste već sortirani podskup da podstaknu brzo sortiranje preostalih sufiksa. Razlika je u tome što ovi algoritmi favorizuju iteraciju iznad rekurzije za sortiranje izabranih podskupova sufiksa. Istraživanje ovih raznolikih grupa algoritama je objavljeno od strane Puglisi, Smyth & Turpin 2007.

Poznat rekurzivni algoritam za celobrojne azbuke je DC3 / izobličenje algoritam Kärkkäinen & Sanders 2003. On radi u linearnom vremenu i uspešno se koristi kao osnova za paralelne i algoritme za izgradnju sufiksnog niza sa eksternom memorijom.

Najnoviji rad Salson et al. 2009 predlaže algoritam za ažuriranje sufiksnog niza teksta koji je izmenjen umesto ponovne izgradnje novog sufiksnog niza od nule. Čak i ako je teoretski u najgorem slučaju vremenska kompleksnost ${\mathcal {O}}(n\log n)$, čini se da se dobro pokazuju u praksi: eksperimentalni rezultati autora pokazali su da je njihova implementacija dinamičkih sufiksnih nizova generalno efikasnija od ponovne izgradnje kada se ubacuje razuman broj slova u originalni tekst.

Aplikacije

Sufiksni niz niske može da se koristi kao indeks da brzo locirate svaku pojavu podniske obrasca $P$ u nisci $S$. Pronalaženje svakog pojavljivanja uzorka je ekvivalentno pronalaženju svakog sufiksa koji počinje sa podniskom. Zahvaljujući leksikografskim poretku, ovi sufiksi će biti grupisani zajedno u sufiksnom nizu i mogu se naći efikasno sa dve binarne pretrage. Prva pretraga locira početnu poziciju intervala, a druga određuje krajnju poziciju:

    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)

Pronalaženje podniske obrasca $P$ dužine $m$ u nisci $S$ dužine $n$ uzima ${\mathcal {O}}(m\log n)$ vremena, s obzirom da za jedno poređenje sufiksa treba da uporedite $m$ znakova. Manber & Myers 1990 opisuju kako se ova granica može poboljšati do ${\mathcal {O}}(m+\log n)$ vremena koristeći informacije iz LCP niza. Ideja je da poređenje obrasca ne mora ponovo da uporedi određene znakove, kada je već poznato da su deo najdužeg zajedničkog prefiksa za uzorak i trenutni interval pretrage. Abouelhoda, Kurtz & Ohlebusch 2004 su poboljšali granicu još dalje i postigli vreme potrage za ${\mathcal {O}}(m)$ kao što je poznato iz sufiksnih stabala.

Algoritmi za sortiranje sufiksa mogu da se koriste za računanje Barouz-Viler transformacije (BVT). BVT zahteva sortiranje svih cikličnih permutacija niza. Ako se ova niska završava sa posebnim terminirajućim karakterima koji su leksikografski manji od svih drugih karaktera (tj., $), onda poredak sortirane rotirane matrice BVT odgovara redosledu sufiksa u sufiksnom nizu. BVT se stoga može izračunati u linearnom vremenu, prvo izgradnjom sufiksnog niza teksta i zatim zaključenjem BVT niske: $BWT[i]=S[A[i]-1]$.

Sufiksni nizovi se takođe mogu koristiti za traženje podniske u mašinskom prevodu zasnovanom na primerima, zahtevajući mnogo manje prostora nego puna tabela fraza koja se koristi u statističkom mašinskom prevođenju. Mnoge dodatne aplikacije sufiksnog niza zahtevaju LCP niz .

Literatura

• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). „Replacing suffix trees with enhanced suffix arrays”. Journal of Discrete Algorithms. 2: 53. doi:10.1016/S1570-8667(03)00065-0. 
• Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. str. 319—327. 
• Manber, Udi; Myers, Gene (1993). „Suffix arrays: a new method for on-line string searches”. SIAM Journal on Computing. 22: 935—948. doi:10.1137/0222058. 
• Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). „New indices for text: PAT trees and PAT arrays”. Information retrieval: data structures and algorithms. 
• Kurtz, S (1999). „Reducing the space requirement of suffix trees”. Software-Practice and Experience. 29 (13): 1149. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O. 
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). „Algorithms in Bioinformatics”. Lecture Notes in Computer Science. 2452: 449. ISBN 978-3-540-44211-0. doi:10.1007/3-540-45784-4_35. 
• Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). „A taxonomy of suffix array construction algorithms”. ACM Computing Surveys. 39 (2): 4. doi:10.1145/1242471.1242472. 
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). „2009 Data Compression Conference”: 193. ISBN 978-0-7695-3592-0. doi:10.1109/DCC.2009.42. 
• Fischer, Johannes (2011). „Algorithms and Data Structures”. Lecture Notes in Computer Science. 6844: 374. ISBN 978-3-642-22299-3. doi:10.1007/978-3-642-22300-6_32. 
• Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). „Dynamic extended suffix arrays”. Journal of Discrete Algorithms. 8 (2): 241. doi:10.1016/j.jda.2009.02.007. 
• Burkhardt, Stefan; Kärkkäinen, Juha (2003). „Combinatorial Pattern Matching”. Lecture Notes in Computer Science. 2676: 55. ISBN 978-3-540-40311-1. doi:10.1007/3-540-44888-8_5. 
• Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). „Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72”: 125. doi:10.1145/800152.804905. 
• Farach, M. (1997). „Proceedings 38th Annual Symposium on Foundations of Computer Science”: 137. ISBN 978-0-8186-8197-4. doi:10.1109/SFCS.1997.646102. 
• Kärkkäinen, Juha; Sanders, Peter (2003). „Automata, Languages and Programming”. Lecture Notes in Computer Science. 2719: 943. ISBN 978-3-540-40493-4. doi:10.1007/3-540-45061-0_73. 
• Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). „Better external memory suffix array construction”. Journal of Experimental Algorithmics. 12: 1. doi:10.1145/1227161.1402296. 
• Kulla, Fabian; Sanders, Peter (2007). „Scalable parallel suffix array construction”. Parallel Computing. 33 (9): 605. 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