guest ::
login
Digital Repository
Search
Submit
Help
About
Home
>
Academic theses (ETDs)
>
Master’s theses
> Algoritmy pro vyhledání nejdelšího shodného prefixu
Information
Files
Original title:
Algoritmy pro vyhledání nejdelšího shodného prefixu
Translated title:
Longest Prefix Match Algorithms
Authors:
Sedlář, František
;
Matoušek, Jiří
(referee) ;
Tobola, Jiří
(advisor)
Document type:
Master’s theses
Year:
2013
Language:
cze
Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract:
[cze]
[eng]
Tato diplomová práce nejprve uvádí čtenáře do problematiky vyhledávání nejdelších shodných prefixů. Analyzuje a popisuje vybrané algoritmy se zaměřením na jejich rychlost, paměťovou náročnost a vhodnost pro hardwarovou implementaci. Na základě získaných poznatků představuje nový algoritmus Generic Hash Tree Bitmap. Ten je mnohonásobně rychlejší než jiné používané metody, zatímco jeho paměťové nároky jsou mnohdy nižší. Implementace algoritmu se stala součástí knihovny Netbench.
This master's thesis explains basics of the longest prefix match (LPM) problem. It analyzes and describes chosen LPM algorithms considering their speed, memory requirements and an ability to implement them in hardware. On the basis of former findings it proposes a new algorithm Generic Hash Tree Bitmap. It is much faster than many other approaches, while its memory requirements are even lower. An implementation of the proposed algorithm has become a part of the Netbench library.
Keywords:
Binary Search on Intervals
;
Binary Search on Prefixes
;
Controlled Prefix Expansion
;
Generic Hash Tree Bitmap
;
Hash Tree Bitmap
;
LC Trie
;
longest prefix match
;
LPM
;
Lulea Compressed Trie
;
Shape Shifting Tree
;
Tree Bitmap
;
trie
;
binární vyhledávání na intervalech
;
binární vyhledávání na prefixech
;
Controlled Prefix Expansion
;
Generic Hash Tree Bitmap
;
Hash Tree Bitmap
;
LC Trie
;
Lulea Compressed Trie
;
nejdelší shodný prefix
;
Shape Shifting Tree
;
Tree Bitmap
;
trie
Institution:
Brno University of Technology (
web
)
Document availability information:
Fulltext is available in the Brno University of Technology Digital Library.
Original record:
http://hdl.handle.net/11012/53506
Permalink:
http://www.nusl.cz/ntk/nusl-236363
The record appears in these collections:
Universities and colleges
>
Public universities
>
Brno University of Technology
Academic theses (ETDs)
>
Master’s theses
Record created 2016-06-03, last modified 2022-09-04
Similar records
No fulltext
Export as
DC
,
NUŠL
,
RIS
Share