Algoritmy konstrukce sufixových stromů

Abstract

V predloženej práci študujeme algoritmy pre výstavbu dátovej štruktúry sufixový strom. Táto štruktúra pomáha optimálne riešiť mnoho problémov z oblasti spracovávania textu. Existuje hneď niekoľko prístupov a algoritmov, ako ju postaviť. Cieľom je vytvoriť taxonómiu algoritmov konštruujúcich sufixové stromy a poskytnúť tak prehľad v ich vlastnostiach a použiteľnosti. Algoritmy doležité z roznych hľadísk sú prezentované, je vysvetlený princíp a myšlienka ich práce. Nasledovne sa porovnajú v testoch a odhalia sa ich prínosy a úskalia. Z výsledkov testov, ale aj teoretických znalostí a znalostí z naštudovanej literatúry, sú zistené spoločné znaky algoritmov a po predložení vhodných kritérií je vytvorená ich taxonómia.

In the present work we study suffix tree construction algorithms. This structure helps solving a variety of text problems in optimal time. There are several approaches and algorithms for building a suffix tree. The goal is to create a taxonomy of these algorithms and provide an overview of their properties and suitable usage. The algorithms important from various points of view are presented. Fundamentals and main ideas of their work are explained. Consequently, they are compared in tests to reveal their main flaws and strength. According to the test results as well as to theoretical knowledge and to information gained from previous studies common features are determined and after presenting the appropriate criteria a taxonomy is created.