Original title:
Algoritmy konstrukce sufixového pole
Translated title:
Suffix array construction algorithms
Authors:
Žoha, Pavel ; Lánský, Jan (referee) ; Dvořák, Tomáš (advisor) Document type: Master’s theses
Year:
2007
Language:
cze Abstract:
[cze][eng] Su fixové pole je datová struktura, která se používá při operacích s řetězci jako je vyhledávání vzorků. Má uplatnění také v některých algoritmech na bezztrátovou kompresi dat. V této práci uvádím srovnání různých postupů při konstrukci su fixového pole (algoritmy Manbera a Myerse, Kírkkáinena a Sanderse, Sewarda, Manziniho a Ferraginy a Ukkonenův algoritmus na konstrukci sufi xového stromu). Tyto metody jsem implementoval a spolu s běžnými třídícími algoritmy (mergesort, quicksort, heapsort a shellsort) testoval jednak na souborech běžně používaných formátů a jednak na náhodně generovaných datech nad různě velkými abecedami. Dále jsem se zabýval možností použití algoritmů pro vstupy nad abecedami většími než 256 znaků.Suffix array is a data structure used for string operations such as pattern matching. It is also useful for some lossless data compression algorithms. In this paper I present a comparison of several di erent ways to construct it (algorithms of Manber & Myers, Kárkkáinen & Sanders, Seward, Manzini & Ferragina and Ukkonen's algorithm for suffix tree construction). I implemented these methodes and together with common sorting algorithms (mergesort, quicksort, heapsort and shellsort) tested both on standard data les and on randomly generated les of di erent alphabet sizes. I also studied the possibility of using these algorithms for inputs of alphabet greater than 256 characters.
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/8150