|
|
Longest Prefix Match Algorithms
Weigner, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
The speed of computer network is increasing. One of the basic tasks which has to be solved by the network devices is longest prefix match. Many algorithms are able to solve this task but it's necessary to solve it very fast because of increasing transfer speed and the routing standard IPv6. This standard has longer addresses and it's necessary to search prefixes in much bigger sets. The thesis describes present algorithms that solve the problem. These are confronted with new algorithm HashTreeBitmap which is also described in the work. On the tests is documented that this algorithm is able to cope with high demands which are placed on it.
|
|
|
Morphological Analyser Implemented as FSAs
Maršová, Eliška ; Otrusina, Lubomír (referee) ; Smrž, Pavel (advisor)
This thesis deals with analysis of czech language and tries to enlarge limited derivative extension of morphologic analysator MA. Author describes actual state of this program and defines ways to find word formation connections, which serves to create derivation rules, which helps to automatically enrich knowledge of czech word formation. Illustrates how are similiar data grouped to create derivation patterns, which will make future work with new words easier. In the end, outcomes are sumarized and direction of possible future evolution is described.
|
|
|
Longest Prefix Match Algorithms
Skačan, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with the algorithms for longest prefix match (LPM), which is the basic operation of the packet classification and of the routing in the IP computer networks. It is introduced the necessary theory and the analysis of the chosen algorithms - Trie, Tree Bitmap, Shape Shifting Tree and Multi-match. These methods were closely described and they were implemented in the programming language Python. Within the implemented algorithms were performed tests and simulations considering their memory demands with the aim to identify the best method for prefix collections about the size of tens to thousands rules.
|
|
|
Generation of Binary Prefix Tree According to Probabilistic Parameters
Ženčák, Tomáš ; Kučera, Jan (referee) ; Matoušek, Jiří (advisor)
The goal of this work is to create a prefix set generator which will be capable of generating a prefix set from parameters specified in the ClassBench toolset. This work describes a possible approach to generation, as well as the final algorithm for prefix set generation. The resulting generator is able to generate prefix sets whose average deviation from the target parameters is typically orders of magnitude lower than the deviation of sets generated by ClassBench.
|
|
|
Hardware Acceleration of Longest Prefix Match
Kekely, Lukáš ; Tobola, Jiří (referee) ; Kořenek, Jan (advisor)
This bachelor's thesis describes design and implementation of hardware architecture for longest prefix match in order to achieve high throughput, which is required in today's high-speed computer networks. It is focused on IPv4 as-well-as IPv6 networks. Designed hardware architecture has throughput 75 Gbps on the shortest IPv4 and IPv6 packets. Performance of designed architecture is also compared with performance of chosen algorithms, which are used in nowadays commercial devices. These algorithms are: Tree Bitmap, Shape-Shifting Trie and Binary Search on Prefixes. All algorithms were implemented in C language using multi-threaded processing.
|
|
|
Detection of Dynamic Network Applications
Juránek, Michal ; Kaštil, Jan (referee) ; Tobola, Jiří (advisor)
This thesis describes methods of detection of simple voice communications of encrypted VoIP calls between two Skype clients. The elements of network and its communication principles are described. Three approaches to classification are analyzed. The first approach performs the classification by content of network packets using Pearson's chi2 test of goodness of fit, the second approach by characteristics of network flows by means of naive Bayesian classification. The third approach describes ways of detecting signaling messages. The detector application is implemented on the basis of chosen methods.
|
|
| |
|
|
Hierarchical compression
Kreibichová, Lenka ; Lánský, Jan (advisor) ; Dvořák, Tomáš (referee)
The most of existing text compression methods is based on the same base concept. First the Input text is divided into sequence of text units. These text units cat be single symbols, syllables or words. When compressing large text files, searching for redundancies over longer text units is usually more effective than searching over the shorter ones. But if we choose words as base units we cannot anymore catch redundancies over symbols and syllables. In this paper we propose a new text compression method called Hierarchical compresssion. It constructs hierarchical grammar to store redundancies over syllables, words and upper levels of text. The code of the text then consists of code of this grammer. We proposed a strategy for constructing hierarchical grammar for concrete input text and we proposed an effective way how to encode it. Above mentioned our proposed method is compared with some other common methods of text compression.
|
|
|
Generation of Binary Prefix Tree According to Probabilistic Parameters
Ženčák, Tomáš ; Kučera, Jan (referee) ; Matoušek, Jiří (advisor)
The goal of this work is to create a prefix set generator which will be capable of generating a prefix set from parameters specified in the ClassBench toolset. This work describes a possible approach to generation, as well as the final algorithm for prefix set generation. The resulting generator is able to generate prefix sets whose average deviation from the target parameters is typically orders of magnitude lower than the deviation of sets generated by ClassBench.
|
|
|
Slovak Pattern-based Morphology
Klocok, Andrej ; Dytrych, Jaroslav (referee) ; Smrž, Pavel (advisor)
Theaimofthisthesisistogetacquaintedwithmethodsofmorphologicalanalysis,representation of data of morphological dictionaries, creation of system based on technical patterns for flective morphology of Slovak language. From this system is derived a morphological analyzer, which lemmatizes input words, determines their pattern and a morphological tag, a tool for comparison and evaluation of stemmers, which evaluates stemmers based on a derivative dictionary, a tool for reconstruction of diacritics, which was created as an auxiliary tool. In the last chapters of thesis, individual tools are assessed, morphological analyzer is compared with available alternative,two implementations of Slovak stemmers are evaluated by the tool for stemmer evaluation and the further development of tools is indicated.
|
guest ::
