Algoritmy nad rozšířeným sufixovým polem

• Thesis title in Czech: Algoritmy nad rozšířeným sufixovým polem
• Thesis title in English: Algorithms for enhanced suffix array
• Academic year of topic announcement: 2008/2009
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: doc. RNDr. Tomáš Dvořák, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 07.10.2008
• Date of assignment: 07.10.2008
• Date and time of defence: 25.05.2009 00:00
• Date of electronic submission: 25.05.2009
• Date of proceeded defence: 25.05.2009
• Opponents: Mgr. Martin Senft, Ph.D.

Guidelines

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.

References

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

Preliminary scope of work

Srovnávací studie algoritmů nad sufixovým stromem a rozšířeným sufixovým polem.

Preliminary scope of work in English

A comparative study of algorithms for suffix tree and enhanced suffix array.