FM-stablo

završni rad

• Naslov (engleski): FM-tree
• Autor: Veronika Knezović
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Igor Mekterović (član povjerenstva)
• Član povjerenstva: Ivica Botički (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2019-07-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Izloženo je i implementirano FM-stablo, novi algoritam koji predstavlja poboljšanje u odnosu na postojeći algoritam lociranja FM-indeksa. Opisane su strukture sufiksno polje i Burrows-Wheelerova transformacija te algoritmi prebrojavanja i lociranja FM-indeksa. Objašnjena je teorijska ideja organiziranja prostora pretraživanja u konceptualno stablo. Uspoređena su vremena izvođenja FM-stabla i algoritma lociranja FM-indeksa. Implementaciju sam napisala u Javi te su testovi su provedeni na datotekama različitih veličina.

Sažetak (engleski)

An FM-tree is a new algorithm that represents an improvement over the existing FM-index locating algorithm. The structures suffix array and Burrows Wheeler Transform, as well as counting and locating algorithms of the FM-index, are described. The theoretical idea of organizing search space into a conceptual multiway tree is explained. The FM-tree and FM-index locating algorithms have been compared. I wrote their implementation in Java programming language and the tests were executed on files of different sizes.

• Ključne riječi: FM-indeks; FM-stablo; sufiksno polje; Burrows-Wheelerova transformacija; bioinformatika
• Ključne riječi (engleski): FM-index; FM-tree; suffix array; Burrows Wheeler Transform; bioinformatics
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:101899
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-07 19:07:50