Suffix tree construction with minimized branching
| Název práce v češtině: | Suffix tree construction with minimized branching |
|---|---|
| Název v anglickém jazyce: | Suffix tree construction with minimized branching |
| Klíčová slova: | sufixový strom, konstrukční algoritmus, minimalizace větvení |
| Klíčová slova anglicky: | suffix tree, construction algorithm, minimization of branching |
| Akademický rok vypsání: | 2010/2011 |
| Typ práce: | diplomová práce |
| Jazyk práce: | anglič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í: | 12.11.2010 |
| Datum zadání: | 12.11.2010 |
| Datum a čas obhajoby: | 03.09.2012 09:00 |
| Datum odevzdání elektronické podoby: | 03.08.2012 |
| Datum odevzdání tištěné podoby: | 03.08.2012 |
| Datum proběhlé obhajoby: | 03.09.2012 |
| Oponenti: | Mgr. Rudolf Kadlec, Ph.D. |
| Zásady pro vypracování |
| Sufixový strom je datová struktura, navržená jako prostorově úsporná reprezentace všech přípon daného slova, která umožňuje efektivní řešení řady vyhledávacích problémů [1]. Klasické konstrukční algoritmy [2-3], které se liší pouze seskupením prováděných kroků [4], používají k rychlému procházení stromem stejnou strategii, založenou na existenci sufixových hran. V práci [5] je navrženo alternativní řešení tohoto problému, založené na minimalizaci počtu větvení, které představují časově nejnáročnější operace celé kostrukce. Tento postup, který by měl vést k vyšší efektivitě v praxi, ovšem v nejhorším případě dosahuje vyšší časové složitosti nežli klasické řešení.
Cílem práce je implementace a experimentální analýza efektivity metody [5]. Součástí vyhodnocení by mělo být srovnání s diskově-orientovanými algoritmy, které sice v nejhorším případě dosahují kvadratické časové složitosti, ale dle experimentů uvedených v [6-7] jsou rychlejší než klasické lineární algoritmy [2-3]. Zajímavé bylo též prozkoumat chování algoritmu na datech, která vedou k dolnímu odhadu časové složitosti Omega(n^1.5). |
| Seznam odborné literatury |
| [1] Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
[2] Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM 23 (2): 262-272, 1976 [3] Esko Ukkonen, On-line construction of suffix trees, Algorithmica 14 (3): 249-260, 1996 [4] Martin Senft, Compressed by the Suffix Tree, DCC 2006, 183-192. [5] Martin Senft, T. Dvořák, On-line suffix treee construction with minimized branching, J. Discrete Algorithms, to appear. [6] Y. Tian, S. Tata, R. A. Hankins, J. M. Patel, Practical methods for constructing suffix trees, VLDB Journal 14 (2005), 281-299. [7] C-F. Cheung, J. X. Yu, H. Lu, Constructing Suffix Tree for Gigabyte Sequences with Megabyte Memory, IEEE Transactions on Knowledge and Data Engineering, 17 (2005), 90-105. |
| Předběžná náplň práce |
| Implementace a experimentální analýza konstrukce sufixového stromu, založené na minimalizaci počtu větvících operací. |
| Předběžná náplň práce v anglickém jazyce |
| Implementation and experimental analysis of suffix tree construction with minimized branching. |