Original title:
Algoritmy nad rozšířeným sufixovým polem
Translated title:
Algorithms for enhanced suffix array
Authors:
Šedek, Jindřich ; Senft, Martin (referee) ; Dvořák, Tomáš (advisor) Document type: Master’s theses
Year:
2009
Language:
cze Abstract:
[cze][eng] Su fixový strom je v oblasti efektivních řešení vyhledávacích problémů jednou z nejdůležitějších datových struktur. Hlavní nevýhodou sufixového stromu je jeho prostorová složitost. Sufixové pole je naproti tomu prostorově úsporná datová struktura, která však nemá tak široké aplikace. Aby bylo možné využít sufi xové pole v pokročilejších aplikacích, je nutné jej rozšířit dalšími pomocnými informacemi. Tato práce je zaměřna na experimentální srovnání rozšířeného sufi xového pole se sufi xovým stromem ve vybraných aplikacích z hlediska časové a prostorové složitosti.Suffix tree is one of the most important data structures in string processing. However, the space consumption of the suffix tree is a bottleneck in large scale applications. Suffix array is by contrast a space efficient data structure having not so large domain of applications. To allow usage of the suffix array in more complex applications, we have to enhance it with an additional information. This work is aimed at a study of the enhanced suffix array and suffix tree in selected applications.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/20744