Suffix tree is a data structure which enables the performing of fast search-like operations on the text. In order to be used efficiently, it must be created quickly. In this thesis, we focus on the new kind of suffix link simulation called "minimized branching", which aims to increase the speed of suffix tree construction by reducing the number of branching operations. Our main goal is to present a comparison of the currently used methods for the suffix tree construction and to point out some advantages and disadvantages of the individual approaches. We introduce, implement and practically evaluate multiple variations of the standard McCreight's and Ukkonen's algorithms, as well as Partition and Write Only Top Down (PWOTD) algorithm, originally developed for disk-based construction. Our main result is the integrated description and implementation of these algorithms, which are both well-suited to be further built upon. We also present a simple recommendations on when it is advisable to use a particular algorithm's variation and why.
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:305101 |
| Date | January 2012 |
| Creators | Bašista, Peter |
| Contributors | Dvořák, Tomáš, Kadlec, Rudolf |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0022 seconds