Naslov
Implementacija komprimirane podatkovne strukture za pretraživanje teksta temeljene na FMindeksu
(Implementation of compressed data structure for text searching based on FMindex)

Autori
Šošić, Martin

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

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
29.06

Godina
2012

Stranica
41

Mentor
Šikić, Mile

Ključne riječi
sažimanje; FMindeks; indeks; implementacija; bioinformatika; genom; sastavljanje
(compressed; FMindex; index; implementation; bioinformatics; genome; assembly)

Sažetak
FMindeks autora Ferragine i Manzini-a posljednjih je godina jako popularan. FMindeks je komprimirana struktura podataka koja omogućuje brzo i učinkovito pretraživanje teksta uz zauzeće memorije ovisno o veličini sažetog teksta. U ovom radu implementirali smo FMindeks u jeziku C++ i isprobali njegovu uporabu na raznim tipovima teksta. Za razliku od idealne implementacije indeksa koja ima složenost lociranja O(p), naša implementacija radi lociranje u složenosti O(p(logn)/(loglogn)). Unatoč tome testovi su pokazali da indeks radi brzo i da vrijeme lociranja s porastom teksta raste vrlo sporo. Pokazali smo i primjenu indeksa u sastavljanju genoma.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA