Algoritmy konstrukce sufixových stromů
| Název práce v češtině: | Algoritmy konstrukce sufixových stromů |
|---|---|
| Název v anglickém jazyce: | Suffix Tree 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: | Mgr. Martin Senft, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 09.11.2006 |
| Datum zadání: | 09.11.2006 |
| Datum a čas obhajoby: | 10.09.2007 00:00 |
| Datum odevzdání elektronické podoby: | 10.09.2007 |
| Datum proběhlé obhajoby: | 10.09.2007 |
| Oponenti: | Mgr. Vladan Majerech, Dr. |
| Zásady pro vypracování |
| Sufixový strom je velmi zajímavá datová struktura, která umožňuje asymptoticky optimálně řešit řadu úloh o řetězcích. Od doby, kdy byla v roce 1973 poprvé popsána Weinerem [1], byla předmětem řady vědeckých prací. Avšak i přes existenci několika různých konstrukčních algoritmů [2,3,4,5, 6, 7 ,8, 9], bylo překvapivě málo usilí věnováno zkoumání praktické rychlosti jeho konstrukce ve vnitřní paměti.
Autor by se měl na základě studia publikovaných algoritmů pokusit vytvořit taxonomii známých metod pro konstrukci sufixového stromu, na tomto základě vybrat několik typických reprezentantů, implementovat je v jednotném prostředí a poté porovnat jejich efektivitu. Doporučuji provést nejen obvyklý odhad časové náročnosti na vhodně vybraném souboru experimentálních dat, ale pokusit se též o konstrukci mezních případů, které by odhalily slabiny jednotlivých algoritmů. Zajímavé by bylo též srovnání s příbuznými sufixovými datovými strukturami (např. DAWG a CDAWG). |
| Seznam odborné literatury |
| [1] P. Weiner. Linear Pattern Matching Algorithms. Proc. 14th IEEE Annual Symp. on Switching and Automata Theory, pp1-11, 1973.
[2] E. M. McCreight. A Space-Economical Suffix Tree Construction Algorithm. Jrnl. of Algorithms, 23(2) pp262-272, 1976. [3] E. Ukkonen. Constructing Suffix Trees On-Line in Linear Time. In Algorithms, Software, Architecture, J.v.Leeuwen (ed), vol#1 of Information Processing 92, Proc. IFIP 12th World Computer Congress, Madrid, Spain, Elsevier Sci. Publ., pp484-492, 1992. [4] E. Ukkonen. On-line Construction of Suffix Trees. Algorithmica, 14(3) pp249-260, 1995. [5] M. Farach. Optimal suffix tree construction with large alphabets. Foundations of Computer Science, 38th Annual Symposium on, 137--143., 1997. [6] S. Kurtz. Reducing the space requirement of suffix trees. Softw., Pract. Exper. 29(13) pp1149-1171, 1999. [7] Sandeep Tata, Richard A. Hankins, and Jignesh M.Patel, Practical Suffix Tree Construction, VLDB 2004, Toronto, Canada. (http://www.eecs.umich.edu/tdd/) [8] Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, Jignesh M. Patel, Practical Methods for Constructing Suffix Trees, VLDB Journal 14(3) Sep 2005, pp 281-299. [9] R. Cole, R. Hariharan. Faster Suffix Tree Construction with Missing Suffix Links. 32nd Annual ACM Symposium on Theory of Computing, pp. 407--415, May 2000. [10] http://mummer.sourceforge.net/ |
| Předběžná náplň práce |
| Cílem práce je provést praktické porovnání efektivity algoritmů pro konstrukci sufixového stromu. |
| Předběžná náplň práce v anglickém jazyce |
| The goal of this work is to compare efficiency of suffix tree construction algorithms. |