Název:
Možnosti využití sufixových stromů
Překlad názvu:
Suffix Trees Capabilities
Autoři:
Chlubna, Pavel ; Hynek, Jiří (oponent) ; Burgetová, Ivana (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2020
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze][eng]
Tato práce pojednává o struktuře sufixových stromů, jejich implementaci a problematice, kterou pomocí sufixových stromů řešíme. Práce se také zaměřuje na konstrukci sufixového stromu, pomocí Ukkonenova algoritmu. Kromě samotné implementace se práce také zabývá porovnáním jiných používaných algoritmů se sufixovými stromu, z hlediska časové náročnosti. Výstupem této práce je ucelená aplikace s grafickým rozhraním, která demonstruje využití sufixových stromů při řešení různých problematik a nabízí porovnání této struktury s jinými algoritmy.
This thesis discusses structure of suffix trees, their implementation and problematics, we can solved with suffix trees. The thesis also focuses on construction of suffix trees, with usage of Ukkonen's algorithm. Apart of implementation of this structure this thesis deals with comparing other commonly used algorithms with suffix trees in term of time complexity. A result of this thesis is application with graphical interface, that shows usage of suffix trees in solving various problematics and shows comparison of this structure to other algorithms.
Klíčová slova:
algoritmy pro vyhledávání v textu; dynamické programování; porovnávání vzorů; Sufixový strom; Ukkonenův algoritmus; časová náročnost; dynamic programming; pattern matching; string-searching algorithm; Suffix tree; time complexity; Ukkonen's algorithm
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/191682