Konstrukční algoritmy pro sufixové datové struktury
| Název práce v češtině: | Konstrukční algoritmy pro sufixové datové struktury |
|---|---|
| Název v anglickém jazyce: | Suffix data structures construction algorithms |
| Akademický rok vypsání: | 2006/2007 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
| Vedoucí / školitel: | doc. RNDr. Tomáš Dvořák, CSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 13.11.2006 |
| Datum zadání: | 13.11.2006 |
| Datum a čas obhajoby: | 26.06.2007 00:00 |
| Datum odevzdání elektronické podoby: | 26.06.2007 |
| Datum proběhlé obhajoby: | 26.06.2007 |
| Oponenti: | Mgr. Martin Senft, Ph.D. |
| Zásady pro vypracování |
| DAWG (directed acyclic word graph) a CDAWG (compact DAWG) jsou datové struktury, navržené jako prostorově úsporné reprezentace všech přípon daného slova, které lze využít pro efektivní řešení úloh z oblasti vyhledávání v textu. Autor by se měl na základě studia literatury pokusit vytvořit taxonomii známých konstrukčních algoritmů, implementovat je v jednotném prostředí a poté porovnat jejich efektivitu na vhodně vybraném souboru experimentálních dat. Zajímavé by bylo pokusit se též o konstrukci mezních případů, které by odhalily slabiny jednotlivých algoritmů, či o srovnání s příbuznými sufixovými datovými strukturami (sufixový strom). |
| Seznam odborné literatury |
| W. Smyth: Computing patterns in strings, Addison-Wesley 2003.
M. Crochemore, R. Vérin, On compact directed acyclic word graphs, Structures in Logic and Computer Science, Lecture Notes in Computer Science, vol. 1261, Springer, Berlin, 1997, 192–211. J. Holub, M. Crochemore, On the Implementation of Compact DAWG's , Lecture Notes in Computer Science 2608(2002), 289-294. S. Inenaga, A. Shinohara, M. Takeda, S. Arikawa: Compact Directed Acyclic Word Graphs for a Sliding Window, Journal of Discrete Algorithms 2(2004), 33-51. S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, G. Pavesi: On-Line Construction of Compact Directed Acyclic Word Graphs, Discrete Applied Mathematics 146(2005), 156-179. |
| Předběžná náplň práce |
| Cílem projektu je implementovat a experimentálně vyhodnotit známé konstrukční algoritmy pro datové struktury DAWG a CDAWG. |
| Předběžná náplň práce v anglickém jazyce |
| The aim of the project is an implementation and experimental evaluation of construction algorithms for DAWG and CDAWG data structures. |