host ::
přihlásit
Digitální repozitář
Hledej
Nový záznam
Nápověda
O repozitáři
Hlavní stránka
>
Vysokoškolské kvalifikační práce
>
Diplomové práce
> Algoritmy pro vyhledání nejdelšího shodného prefixu
Informace
Soubory
Název:
Algoritmy pro vyhledání nejdelšího shodného prefixu
Překlad názvu:
Longest Prefix Match Algorithms
Autoři:
Sedlář, František
;
Matoušek, Jiří
(oponent) ;
Tobola, Jiří
(vedoucí práce)
Typ dokumentu:
Diplomové práce
Rok:
2013
Jazyk:
cze
Nakladatel:
Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt:
[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.
Klíčová slova:
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
;
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
Instituce:
Vysoké učení technické v Brně (
web
)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT.
Původní záznam:
http://hdl.handle.net/11012/53506
Trvalý odkaz NUŠL:
http://www.nusl.cz/ntk/nusl-236363
Záznam je zařazen do těchto sbírek:
Školství
>
Veřejné vysoké školy
>
Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce
>
Diplomové práce
Záznam vytvořen dne 2016-06-03, naposledy upraven 2022-09-04.
Podobné záznamy
Není přiložen dokument
Exportovat ve formátu
DC
,
NUŠL
,
RIS
Sdílet