hrvatski

Implementacija komprimirane podatkovne strukture za pretraživanje teksta temeljene na FMindeksu

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.

sažimanje; FMindeks; indeks; implementacija; bioinformatika; genom; sastavljanje

nije evidentirano