Suffix tree construction with minimized branching
| Thesis title in Czech: | Suffix tree construction with minimized branching |
|---|---|
| Thesis title in English: | Suffix tree construction with minimized branching |
| Key words: | sufixový strom, konstrukční algoritmus, minimalizace větvení |
| English key words: | suffix tree, construction algorithm, minimization of branching |
| Academic year of topic announcement: | 2010/2011 |
| Thesis type: | diploma thesis |
| Thesis language: | anglič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: | 12.11.2010 |
| Date of assignment: | 12.11.2010 |
| Date and time of defence: | 03.09.2012 09:00 |
| Date of electronic submission: | 03.08.2012 |
| Date of submission of printed version: | 03.08.2012 |
| Date of proceeded defence: | 03.09.2012 |
| Opponents: | Mgr. Rudolf Kadlec, Ph.D. |
| Guidelines |
| 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). |
| References |
| [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. |
| Preliminary scope of work |
| Implementace a experimentální analýza konstrukce sufixového stromu, založené na minimalizaci počtu větvících operací. |
| Preliminary scope of work in English |
| Implementation and experimental analysis of suffix tree construction with minimized branching. |