Název:
Konstrukční algoritmy pro sufixové datové struktury
Překlad názvu:
Suffix data structures construction algorithms
Autoři:
Šedek, Jindřich ; Dvořák, Tomáš (vedoucí práce) ; Senft, Martin (oponent) Typ dokumentu: Bakalářské práce
Rok:
2007
Jazyk:
cze
Abstrakt: [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].