|
|
Comparing Speed of the Modern Systems for Regular Expression Matching
Trávníček, Jan ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This thesis describes how to compare the speed of modern tools for regular expressions matching. To compare the speed of each tool is used set of regular expressions from the Snort - Intrusion Detection System, which are specified in the PCRE notation. These regular expressions are evaluated by difeerent tools and the results are compared with each other. In this work is also solved difeerence between mathematical and practical perspective on the term of regular expression and transfer Perl regular expressions in POSIX regular expressions.
|
|
|
Aproximate String Matching
Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the problem of approximate string matching, ie. string matching allowing errors. Initially, we will define the problem itself and demonstrate variety of it's applications, followed by short survey of different approaches to cope with this problem. The remaining part of the work is focused on algorithms based on the use of deterministic finite automatons. Main algorithms in this area will be presented. Those will be implemented in Python programming language and thoroughly compared in series of experiments.
|
|
|
Efficient Algorithms for Finite Automata
Hruška, Martin ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
Nondeterministic finite automata are used in many areas of computer science, including, but not limited to, formal verification, the design of digital circuits or for the representation of a regular language. Their advantages over deterministic finite automata is that they may represent a language in even exponentially conciser way. However, this advantage may be lost if a naive approach to some operations is taken, in particular for checking language inclusion of a pair of automata, the naive implementation of which performs an explicit determinization of one of the automata. Recently, several new techniques for this operation that avoid explicit determinization (using the so-called antichains or bisimulation up to congruence) have been proposed. The main goal of the presented work is to efficiently implement these techniques as a new extension of the VATA library. The implementation has been evaluated and is superior to other implementations in over 90% of tested cases by the factor of 2 to 100.
|
|
|
Morphological Analyser Implemented as FSAs
Bezák, Jakub ; Schwarz, Petr (referee) ; Smrž, Pavel (advisor)
The aim of this paper is to introduce to its reader the field of morphemics and morphemic analysis of slovak language using morphemic analyser and to signify the difference from other world languages. In this text it is also explained the importance of finding base form of words while analysing slovak texts. Other part analyses the optimal storage of large dictionaries using finite state automata minimization. The end contains the comparison between various forms of implementation.
|
|
|
Implementation of the Pattern Matching Unit in the FPGA
Košař, Vlastimil ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This term project focuses on algorithms for pattern matching used in modern IDS. The main focus is on regular expression matching. It deals with methods based on deterministic and nondeterministic finite automata, hybrid methods and with method based on regular expressions as programing langue for specialised processors. Implementation of pattern matching units based on some of described methodologies is described in next part. Methodology for resource consumption estimation is also described. Developed software system for unit generation is described in the next part. In the final part results are presented and discused.
|
|
| |
|
|
Fast Regular Expression Matching Using FPGA
Kaštil, Jan ; Martínek, Tomáš (referee) ; Kořenek, Jan (advisor)
The thesis explains several algorithms for pattern matching. Algorithms work in both software and hardware. A part of the thesis is dedicated to extensions of finite automatons. The second part explains hashing and introduces concept of perfect hashing and CRC. The thesis also includes a suggestion of possible structure of a pattern matching unit based on deterministic finite automatons in FPGA. Experiments for determining the structure and size of resulting automatons were done in this thesis.
|
|
|
Lexical Analyzer for Multiprocesor Computers
Otáhal, Jiří ; Goldefus, Filip (referee) ; Čermák, Martin (advisor)
Aim of this thesis is to invent method, which should accelerate speed of the analysis of source texts with multiprocessor computers. For this purpose application runs multiple process in Unix system. Each undergoing process analyzes exact partition in source file and then closes itself. Outcome of this process are internal structures, which presents exact partition. Inter-code is sequentially built from the structures which are subsequently interpreted. This kind of parallel analysis achieves acceleration of speed on the contrary of typical sequential analysis.
|
|
|
Machine Learning for Formal Language Model Inference
Bardonek, Petr ; Kocman, Radim (referee) ; Křivka, Zbyněk (advisor)
This bachelor thesis deals with the formal language model inference, which is a science discipline on the research field of artificial intelligence. The aim is to create an appliaction that allows the automatic inference of model, such as the finite state machine, for an unknown formal language from the set of the strings of the unknown formal language using the modified machine learning method.
|
|
| |
guest ::
