Algoritmy konstrukce sufixových stromů

• Thesis title in Czech: Algoritmy konstrukce sufixových stromů
• Thesis title in English: Suffix Tree Construction Algorithms
• Academic year of topic announcement: 2006/2007
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: Mgr. Martin Senft, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 09.11.2006
• Date of assignment: 09.11.2006
• Date and time of defence: 10.09.2007 00:00
• Date of electronic submission: 10.09.2007
• Date of proceeded defence: 10.09.2007
• Opponents: Mgr. Vladan Majerech, Dr.

Guidelines

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).

References

[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/

Preliminary scope of work

Cílem práce je provést praktické porovnání efektivity algoritmů pro konstrukci sufixového stromu.

Preliminary scope of work in English

The goal of this work is to compare efficiency of suffix tree construction algorithms.