Sažeta sufiksna polja

undergraduate thesis

• Title (english): Compressed Suffix Arrays
• Author: Anita Božić
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Boris Milašinović (član povjerenstva)
• Committee member: Zdravko Galić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: sufiksna polja; sažeta sufiksna polja; Re-Pair; Delta kodiranje; Elias-Fanova metoda; Psi funkcija; SA-IS
• Keywords (english): suffix arrays; compressed suffix arrays; Re-Pair; Delta encoding; Elias-Fano method; Psi function; SA-IS
• Language: croatian
• URN:NBN: urn:nbn:hr:168:396573
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 19:15:13