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