Wyszukiwanie pozycyjne - algorytmy i struktury

• Autorzy: Śmietana, M.
• Języki publikacji: PL

Abstrakty

PL

Praca ta zbiera i systematyzuje zagadnienia związane z problemem wyszukiwania pozycyjnego i pokazuje możliwości, jakie w tym zakresie powstają przy stosowaniu nowoczesnych struktur danych, takich jak binarne drzewa poszukiwań cyfrowych, binarne drzewa trie i binarne drzewa patricia. Dodatkowo zawiera praktyczne wskazówki kiedy warto stosować wyszukiwanie pozycyjne, a kiedy należy zastanowić się nad alternatywnymi metodami takimi jak: funkcje mieszające, poszukiwanie indeksowane kluczem, drzewa TST (ternary searching tree), drzewa pozycyjne wielokierunkowe. Opisywane w pracy algorytmy wyszukiwania pozycyjnego oraz budowania drzew pozycyjnych przedstawiono za pomocą diagramów UML. Metody wyszukiwania pozycyjnego są zarówno dyskutowane teoretycznie pod względem złożoności czasowej i pamięciowej jak i badane empirycznie.

Słowa kluczowe

PL

drzewo trie z upakowaniem poziomów; drzewo Patricia; funkcje mieszające; tablice mieszające; drzewa TST; drzewo pozycyjne; poszukiwanie indeksowane kluczem

• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2004
• Tom: R. 4, nr 6
• Strony: 13-26
• Opis fizyczny: Bibliogr. 4 poz., rys., tab.

Twórcy

autor

Śmietana, M.

• Akademia Górniczo-Hutnicza Kraków, Al. Mickiewicza 30

Bibliografia

• [1] Flajolet P., On the performance analysis of extendible hashing and trie search, Acta Informatica 20 1983.
• [2] Morrison D., PATRICIA - Practical Algorithm to Retrieve Information Coded In Alfanumeric’, Journal of the ACM, tom 15, numer 4, str. 514-534., X 1968.
• [3] Sedgewick R., Van Wyk C.J., Algortymy w C++. Podstawy, dane strukturalne, sortowanie, wyszukiwanie, Wydawnictwo RM, Warszawa 1999.
• [4] Wirth N., Algorytmy + struktury danych = programy, WNT, Warszawa 1989.