Naslov
Metode izgradnje polja najduljih zajedničkih prefiksa niza
(Methods for the longest common prefix array construction)

Autori
Mesarić, Marko

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

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
04.07

Godina
2018

Stranica
48

Mentor
Domazet-Lošo, Mirjana

Ključne riječi
polje najduljih zajedničkih prefiksa niza ; algoritmi indeksiranja teksta ; Burrows-Wheelerova transformacija ; sufiksno polje
(longest common prefix array ; text indexing algorithms ; Burrows-Wheeler transformation ; suffix array)

Sažetak
U okviru ovog završnog rada obrađene su strukture podataka koje se često koriste u bioinformatici: sufiksno polje, polje najduljih zajedničkih prefiksa (LCP polje) i Burrows-Wheelerova transformacija znakovnog niza. Analizirane su različite metode izgradnje LCP i BWT polja s posebnim osvrtom na nedavno objavljeni algoritam u kojemu je dodatni memorijski prostor za izgradnju LCP polja O(1). Algoritmi za izgradnju BWT i LCP polja implementirani su u programskom jeziku C++. Uspoređene su različite metode izgradnje LCP polja prema vremenu izvođenja i memorijskoj potrošnji te su potom i uspoređena s postojećim programskim rješenjima.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA