Algoritmy konstrukce sufixového pole
| Thesis title in Czech: | Algoritmy konstrukce sufixového pole |
|---|---|
| Thesis title in English: | Suffix array construction algorithms |
| Academic year of topic announcement: | 2005/2006 |
| 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: | 11.11.2005 |
| Date of assignment: | 11.11.2005 |
| Date and time of defence: | 05.02.2007 00:00 |
| Date of electronic submission: | 05.02.2007 |
| Date of proceeded defence: | 05.02.2007 |
| Opponents: | RNDr. Jan Lánský, Ph.D. |
| Guidelines |
| Sufixové pole je datová struktura, navržená v roce 1990 Manberem a Myersem [1] jako prostorově úsporná varianta sufixového stromu, která je využívána pro zpracování řetězců i kompresi dat (implementace Burrows-Wheelerovy transformace). V poslední době byly publikovány jak konstrukční algoritmy pracující v lineárním čase [2,3], tak algoritmy se složitostí v nejhorším případě superlineární [4,5], které jsou však při praktickém použití obvykle rychlejší.
Autor by se měl na základě studia publikovaných algoritmů pokusit vytvořit taxonomii známých metod pro konstrukci sufixového pole, 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ř. sufixový strom). |
| References |
| [1] U.Manber, G.Myers: Suffix arrays: A new mathod for online string searches. Proc. First ACM-SIAM Symp. on Discrete Algs. (1990), 319-327.
[2] P.Ko, S.Aluru: Space efficient linear time construction of suffix arrays. Proc. 14th Annual Symp. on Pattern Matching, LNCS 2676, Springer, 2003, 200-210. [3] J.Karkkainen, P.Sanders: Simple linear work suffix array construction. Proc. 30th International Colloquium on Automata, Languages and Programming, LNCS 2719, Springer, 2003, 943-955. [4] S.Burkhardt, J. Karkkainen: Fast lightweight suffix array construction and checking. Proc. 14th Annual Symp. Combinatorial Pattern Matching, LNCS 2676, Springer, 2003, 55-69. [5] G.Manzini, P.Ferragina: Engineering a lightweight suffix array construction algorithm. Algorithmica 40(2004), 33-50. |
| Preliminary scope of work |
| Cílem práce je provést praktické porovnání efektivity algoritmů pro konstrukci sufixového pole. |