Název: Algoritmy konstrukce sufixového pole
Překlad názvu: Suffix array construction algorithms
Autoři: Žoha, Pavel ; Lánský, Jan (oponent) ; Dvořák, Tomáš (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2007
Jazyk: cze
Abstrakt: [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.

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/8150

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-270670


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce