Algoritmy konstrukce sufixového pole

Abstract

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.

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ů.