Algoritmy konstrukce sufixového pole
| Název práce v češtině: | Algoritmy konstrukce sufixového pole |
|---|---|
| Název v anglickém jazyce: | Suffix array construction algorithms |
| Akademický rok vypsání: | 2005/2006 |
| 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í: | 11.11.2005 |
| Datum zadání: | 11.11.2005 |
| Datum a čas obhajoby: | 05.02.2007 00:00 |
| Datum odevzdání elektronické podoby: | 05.02.2007 |
| Datum proběhlé obhajoby: | 05.02.2007 |
| Oponenti: | RNDr. Jan Lánský, Ph.D. |
| Zásady pro vypracování |
| 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). |
| Seznam odborné literatury |
| [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. |
| Předběžná náplň práce |
| Cílem práce je provést praktické porovnání efektivity algoritmů pro konstrukci sufixového pole. |