FM-tree

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.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