Original title:
Konstrukční algoritmy pro sufixové datové struktury
Translated title:
Suffix data structures construction algorithms
Authors:
Šedek, Jindřich ; Dvořák, Tomáš (advisor) ; Senft, Martin (referee) Document type: Bachelor's theses
Year:
2007
Language:
cze Abstract:
[cze][eng] Directed Acyclic Word Graph (DAWG) je prostorově úsporná datová struktura, která slouží k ukládání přípon řetězců. Compact Directed Acyclic Word Graph (CDAWG) je ještě úspornější variantou DAWG. Jejich hlavní uplatnění je v hledání vzorků uvnitř rozsáhlých řetezců. Tato práce je zaměřena na implementaci několika známých konstrukčních algoritmů těchto datových struktur. Otestoval jsem je na různé druhy vstupních dat a porovnal jejich vlastnosti. Konkrétně jsem se zajímal o Blumerův algoritmus na konstrukci DAWG [1], Crochemorův algoritmus na konstrukci CDAWG [2] a Inenagův algoritmus na konstrukci CDAWG [3].Directed Acyclic Word Graph (DAWG) is a space efficient data structure used for storing suffixes of strings. Compact Directed AcyclicWord Graph (CDAWG) is a more space efficient variant of DAWG. Their main use is in searching short patterns in a huge amount of data. This work is aimed at an implementation of few construction algorithms of these data structures. It compaires characteristics of Blumer et. al algorithm for DAWG construction [1], Crochemore algorithm for CDAWG construction [2] and Inenaga algorithm for CDAWG construction [3].
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/10451