Algoritmy nad rozšířeným sufixovým polem
| Název práce v češtině: | Algoritmy nad rozšířeným sufixovým polem |
|---|---|
| Název v anglickém jazyce: | Algorithms for enhanced suffix array |
| Akademický rok vypsání: | 2008/2009 |
| Typ práce: | diplomová 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í: | 07.10.2008 |
| Datum zadání: | 07.10.2008 |
| Datum a čas obhajoby: | 25.05.2009 00:00 |
| Datum odevzdání elektronické podoby: | 25.05.2009 |
| Datum proběhlé obhajoby: | 25.05.2009 |
| Oponenti: | Mgr. Martin Senft, Ph.D. |
| Zásady pro vypracování |
| Sufixový strom je populární datová struktura, která umožňuje efektivní řešení řady vyhledávacích problémů [3], její nevýhodnou je ovšem značná prostorová náročnost. Sufixové pole [4-5] je naproti tomu prostorově úsporná datová struktura, která však nemá tak široké aplikace. Jistý kompromis mezi oběma strukturami představuje sufixové pole, vybavené dodatečnými informacemi. Výsledky prací [1-2] ukazují, jak lze takto rozšířeným sufixovým polem systematicky nahradit sufixový strom.
Cílem práce je praktické porovnání algoritmů nad oběma datovými strukturami, případně jejich vylepšení a rozšíření. Autor by měl prostudovat známé aplikace sufixových stromů [3, kap. 7 a 9] a ve vybraných algoritmech se pokusit nahradit tuto datovou strukturu rozšířeným sufixovým polem tak, aby nedošlo k výraznému zvýšení časové složitosti. Součástí práce by měla být i implementace nad oběma datovými strukturami a experimentální porovnání časové i prostorové náročnosti na dostatečně reprezentativní množině testovacích dat. |
| Seznam odborné literatury |
| [1] Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, The enhanced suffix array and its application to genome analysis, Proc. Second Workshop on Algorithms in Bioinformatics, LNCS 2452 (2002), 449-463.
[2] Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, J. Discrete Algs. 2 (2004), 53-86. [3] Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997. [4] Simon Puglisi, W. F. Smyth, Andrew Turpin, A taxonomy of suffix array construction algorithms, ACM Computing Surveys 39 (2007), 1-31. [5] Pavel Žoha, Algoritmy konstrukce sufixového pole, diplomová práce MFF UK, Praha 2006. |
| Předběžná náplň práce |
| Srovnávací studie algoritmů nad sufixovým stromem a rozšířeným sufixovým polem. |
| Předběžná náplň práce v anglickém jazyce |
| A comparative study of algorithms for suffix tree and enhanced suffix array. |