Komprimovani sufiks niza

U računarstvu, komprimovani sufiks niza (engl. Compressed suffix array) je komprimovana struktura podataka za pronalaženje modela. Imajući u vidu tekst T od n karaktera iz Σ azbuke, komprimovani sufiks niza podržava traženje proizvoljnih obrazaca u T. Za ulaz obrasca P od m karaktera, vreme za traženje je jednako do n puta višeg reda entropije teksta T , plus neki dodatni delovi bita za skladištenje empirijskog statističkog modela i O(n).

Originalni primer komprimovanog sufiksa niza rešavao je dugogodišnji otvoreni problem pokazujući da je brzo pronalaženje modela bilo moguće korišćenjem samo linearno-prostorne strukture podataka, naime, proporcionalno sa veličinom teksta T, koje zauzima $O(n\,{\log |\Sigma |})$ bita. Konvencionalni sufiks niza i sufiks drvo koriste $\Omega (n\,{\log n})$ bita, što je znatno veće. Osnova za strukturu podataka je rekurzivno raspadanje koristeći "komšijsku funkciju", koja omogućava da se sufiks niza predstavlja jednom polovinom njegove dužine. Konstrukcija se ponavlja više puta dok rezultujući sufiks niza ne koristi linearni broj bitova. Sledeći rad je pokazao da je stvarni prostor za skladištenje bio vezan za nulti red entropije i da indeks podržava samo-indeksiranje.. Zauzimanje memorije je dodatno poboljšano što je dovelo do postizanja krajnjeg cilja - višeg reda entropije. Kompresija se postiže podelom komšijske funkcije kontekstima višeg reda, i zbijanje svake particije sa talasastim stablom. Korišćenje prostora je izuzetno konkurentno u praksi sa drugim kompresorima, a takođe podržava brzo pronalaženje modela.

Pristupi memoriji, stvoreni od strane komprimovanog sufiksa nizova i drugih komprimovanih struktura podataka za pronalaženje modela, uglavnom nisu lokalizovani, pa prema tome ove strukture podataka su bile izuzetno teško efikasno dizajnirane za upotrebu u eksternoj memoriji. Nedavni napredak pomoću geometrijskog dualiteta koristi prednosti blokiranja pristupa koji obezbeđuju diskovi da značajno ubrza I/O vreme.