|
|
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.
|
|
|
Algorithm Visualisation
Vranec, Maroš ; Senft, Martin (advisor) ; Kučera, Luděk (referee)
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.
|
|
|
Suffix Array for Large Alphabet
Šesták, Radovan ; Lánský, Jan (advisor) ; Senft, Martin (referee)
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.
|
|
|
Suffix data structures construction algorithms
Šedek, Jindřich ; Dvořák, Tomáš (advisor) ; Senft, Martin (referee)
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].
|
|
|
Data mining of the database of Consulting centre for metabolism disorders
Senft, Martin ; Ivánek, Jiří (advisor) ; Musil, Vladimír (referee)
This thesis applies the data mining method of decision rules on data from Consulting centre for Metabolism disorders from University hospital Pilsen. As a tool is used the system LISp-Miner, developed at University of Economics, Prague. Decision rules found are evaluated by a specialist. The main parts of this thesis are followings: an overview on main data mining methods and results evalutation methods, description of the data mining method application on data and description and evaluation of results.
|
|
|
Compact directed acyclic word graph in a sliding window
Filip, Ondřej ; Dvořák, Tomáš (advisor) ; Senft, Martin (referee)
Compact directed acyclic word graph (CDAWG) is the space-efficient version of a text-indexing data structure called suffix tree. The goal of this work is an implementation and comparison of algorithms constructing CDAWG for text in a sliding window. Sliding window is favorable in cases when the index structure cannot be kept in memory for the whole indexed data. One exact move of the sliding window may be performed in linear time with respect to the length of the window. An approximative algorithm requiring only amortized constant time per one move has been developed, too. However, in this thesis, the correctness of this algorithm has been disproved.
|
|
|
Mariáš Card Game Trainer
Malý, Dominik ; Senft, Martin (advisor) ; Bílý, Tomáš (referee)
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.
|
|
|
Data mining of the database of Consulting centre for metabolism disorders
Senft, Martin ; Ivánek, Jiří (advisor) ; Musil, Vladimír (referee)
This thesis applies the data mining method of decision rules on data from Consulting centre for Metabolism disorders from University hospital Pilsen. As a tool is used the system LISp-Miner, developed at University of Economics, Prague. Decision rules found are evaluated by a specialist. The main parts of this thesis are followings: an overview on main data mining methods and results evalutation methods, description of the data mining method application on data and description and evaluation of results.
|
|
|
Suffix Graphs and Lossless Data Compression
Senft, Martin ; Dvořák, Tomáš (advisor) ; Dvorský, Jiří (referee) ; Smyth, William F. (referee)
Title: Suffix Graphs and Lossless Data Compression Author: Martin Senft Department: Department of Software and Computer Science Education Supervisor of the doctoral thesis: doc. RNDr. Tomáš Dvorˇák, CSc., Depart- ment of Software and Computer Science Education Abstract: Suffix tree and its variants are widely studied data structures that enable an efficient solution to a number of string problems, but also serve for implementation of data compression algorithms. This work explores the opposite approach: design of compression methods, based entirely on prop- erties of suffix graphs. We describe a unified construction algorithm for suf- fix trie, suffix tree, DAWG and CDAWG, accompanied by analysis of implicit suffix link simulation that yields two practical alternatives. Since the com- pression applications require maintaining text in the sliding window, an in- depth discussionof slidingsuffixgraphsisneeded. Fillinggapsin previously published proofs, we verify that suffix tree is capable of perfect sliding in amortised constant time. On the other hand, we show that this is not the case with CDAWG, thus resolving a problem of Inenaga et al. Building on these investigations,we describea family of data compression methods,based on a description of suffix tree construction for the string to be compressed. While some of...
|
|
|
Compact directed acyclic word graph in a sliding window
Filip, Ondřej ; Dvořák, Tomáš (advisor) ; Senft, Martin (referee)
Compact directed acyclic word graph (CDAWG) is the space-efficient version of a text-indexing data structure called suffix tree. The goal of this work is an implementation and comparison of algorithms constructing CDAWG for text in a sliding window. Sliding window is favorable in cases when the index structure cannot be kept in memory for the whole indexed data. One exact move of the sliding window may be performed in linear time with respect to the length of the window. An approximative algorithm requiring only amortized constant time per one move has been developed, too. However, in this thesis, the correctness of this algorithm has been disproved.
|
guest ::
RSS feed.