Compressed Suffix Arrays

Sažeto sufiksno polje je struktura korištena za sažimanje i indeksiranje teksta, a služi u svrhu lociranja uzoraka u tekstu. Ovakva struktura zauzima manje memorijskog prostora od nekih drugih struktura za indeksiranje (npr. sufiksnog stabla) te nudi zadovoljavajuće vremenske i memorijske performanse. U sklopu ovog završnog rada proučila sam i implementirala metode sažimanja sufiksnog polja: Re-Pair, Delta kodiranje i Elias-Fanovu metodu koje koriste Psi funkciju. Obavila sam analizu tih metoda kompresije uz naglasak na prednosti i nedostatke svake metode. Usporedila sam i analizirala performanse mojih implementacija. Dodatno objašnjavam i postupke dekompresije.Compressed suffix array is a structure used for text compression, text indexing and pattern matching. This type of structure uses less memory space than some of the other indexing structures (for instance suffix tree) and it offers satisfying time and memory performance. In this Bachelor thesis I use three different methods of suffix array compression: Re-Pair, Delta encoding and Elias-Fano method which use Psi function. Analysis is performed on different compression methods with a focus on benefits and shortcomings of each method. I compare and analyze performance of each method. Additionaly, procedures of decompression are explained