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

Permalink: http://www.nusl.cz/ntk/nusl-270670


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses