Naslov
Sažeta sufiksna polja
(Compressed Suffix Arrays)

Autori
Božić, Anita

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
03.07

Godina
2018

Stranica
52

Mentor
Domazet-Lošo, Mirjana

Ključne riječi
sufiksna polja ; sažeta sufiksna polja ; Re-Pair ; Delta kodiranje ; Elias-Fanova metoda ; Psi funkcija ; SA-IS
(suffix arrays ; compressed suffix arrays ; Re-Pair ; Delta encoding ; Elias-Fano method ; Psi function ; SA-IS)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA