|
|
Suffix Tree Construction Algorithms
Host, Ján ; Majerech, Vladan (referee) ; Senft, Martin (advisor)
In the present work we study suffix tree construction algorithms. This structure helps solving a variety of text problems in optimal time. There are several approaches and algorithms for building a suffix tree. The goal is to create a taxonomy of these algorithms and provide an overview of their properties and suitable usage. The algorithms important from various points of view are presented. Fundamentals and main ideas of their work are explained. Consequently, they are compared in tests to reveal their main flaws and strength. According to the test results as well as to theoretical knowledge and to information gained from previous studies common features are determined and after presenting the appropriate criteria a taxonomy is created.
|
|
|
Delta Compression
Kmeť, Peter ; Senft, Martin (advisor) ; Bílý, Tomáš (referee)
In this work I present an algorithm for the delta compression problem referring to e ective representation of changes, which occur in a modi ed version of the le with respect to the original le. The algorithm uses the method of searching a dictionary to replace repeating strings of characters by short references to their previous occurrence. These matches are located in both les. Common pre xes of strings are obtained using suffix arrays, potentially interesting alternative to other procedures. The solution is divided in couple of easily modi able modules and changes are stored in own le format. In the work results of used techniques are briefly discussed and possible improvements of the project are proposed.
|
|
|
Contemporary Methods in Fractal Image Compression
Čunát, Vladimír ; Senft, Martin (referee) ; Dvořák, Tomáš (advisor)
In the present work we study fractal image compression. We discuss basic techniques, published improvements, and a few proposed enhancements of the current methods including their implementation. A framework for fractal compression is introduced. It is designed in order to be able to replace individual parts of the encoding process by di erent algorithms, simplifying comparison of their combinations. Presented enhancements are evaluated on a set of testing images. With proposed penalisation method decompressed images reach higher qualities. The differential coding combined with reordering of range-blocks decreases the amount of needed space approximately by 5%. On the other hand the prediction implemented by KD-trees isn't as accurate in comparison to a paper using another data structure.
|
|
|
Suffix data structures construction algorithms
Šedek, Jindřich ; Senft, Martin (referee) ; Dvořák, Tomáš (advisor)
Directed Acyclic Word Graph (DAWG) is a space efficient data structure used for storing suffixes of strings. Compact Directed AcyclicWord Graph (CDAWG) is a more space efficient variant of DAWG. Their main use is in searching short patterns in a huge amount of data. This work is aimed at an implementation of few construction algorithms of these data structures. It compaires characteristics of Blumer et. al algorithm for DAWG construction [1], Crochemore algorithm for CDAWG construction [2] and Inenaga algorithm for CDAWG construction [3].
|
|
|
Mariáš Card Game Trainer
Malý, Dominik ; Bílý, Tomáš (referee) ; Senft, Martin (advisor)
Mariáš is probably the most well-known and favourite card game in Czech Republic and despite this remains to be seen almost exclusively in our country. In this work we study the ways, how can this interesting game be implemented in the speech of ones and zeros typical for computers. This work also briefly describes the evolution of full information games solving algorithms, from old minimax to alfabeta pruning and my own adjusted negamax - algorithm for games without full information, using a more universal approach, which could be theorethically extended for all card games, whether existing or not.
|
|
|
Algorithms for enhanced suffix array
Šedek, Jindřich ; Senft, Martin (referee) ; Dvořák, Tomáš (advisor)
Suffix tree is one of the most important data structures in string processing. However, the space consumption of the suffix tree is a bottleneck in large scale applications. Suffix array is by contrast a space efficient data structure having not so large domain of applications. To allow usage of the suffix array in more complex applications, we have to enhance it with an additional information. This work is aimed at a study of the enhanced suffix array and suffix tree in selected applications.
|
|
|
Suffix Array for Large Alphabet
Šesták, Radovan ; Senft, Martin (referee) ; Lánský, Jan (advisor)
Burrows-Wheeler Transform (BWT) [3] is used as the major part in block compression which has good balance of speed and compression ratio. Suffix arrays are used in the coding phase of BWT and we focus on creating them for alphabet larger than 2^8 symbols. The motivation for this work has been software project XBW[4] - an application for compression of large XML files. The role of BWT is to reorder input before applying other algorithms. We describe and implement three families of algorithms for encoding. First is inspired by the work of Sadakane [10] and further improved by Larsson [8]. Second family includes algorithm by Seward [11] and algorithm by Itoh further improved by Kao [5]. Finally we present algorithm by Kärkkäinen and Sanders [6] for constructing suffix arrays in linear time.
|
|
|
Algorithm Visualisation
Vranec, Maroš ; Kučera, Luděk (referee) ; Senft, Martin (advisor)
Animelib is Java library, which visualizes data structures. It is designated for user-friendly visualization of algorithms. User-friendlyness is done in two ways - programmer of algorithm has much less graphics code to write (none ideally), and user - viewer should be pleased with what he sees.
|
guest ::
