Geodesic
Efficient Improvement of Brain-Tharp's Algorithm
Yugoslav journal of operations research, Tome 9 (1999) no. 2, p. 235 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

In this paper we present possible improvement of the best known perfect hashing algorithm. A comparison of the proposed algorithm with other known important perfect hashing algorithms in addition to Brain-Tharp's algorithm is also given. The Brain-Tharp's algorithm is the best known in the special class of algorithms that can be used to form ordered minimal perfect hash functions for very large word lists in terms of function building efficiency, pattern collision avoidance and retrieval function complexity. However, building a perfect hash function by the Brain-Tharp's algorithm is still extremely slow. In this paper we analyzed important features of Brain-Tharp's algorithm and proposed three solutions to improve the total processing time of the packing phase. The proposed techniques are validated empirically. The improvement factor is close to 2 on the example of the standard UNIX dictionary.
Classification : 68W05 68W10
Keywords: Algorithms, file structures, perfect hashing, physical design. 
@article{YJOR_1999_9_2_a6,
     author = {Dejan Simi\'c and Du\v{s}an Star\v{c}evi\'c},
     title = {Efficient {Improvement} of {Brain-Tharp's} {Algorithm}},
     journal = {Yugoslav journal of operations research},
     pages = {235 },
     year = {1999},
     volume = {9},
     number = {2},
     zbl = {1009.68181},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a6/}
}
TY  - JOUR
AU  - Dejan Simić
AU  - Dušan Starčević
TI  - Efficient Improvement of Brain-Tharp's Algorithm
JO  - Yugoslav journal of operations research
PY  - 1999
SP  - 235 
VL  - 9
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a6/
LA  - en
ID  - YJOR_1999_9_2_a6
ER  - 
%0 Journal Article
%A Dejan Simić
%A Dušan Starčević
%T Efficient Improvement of Brain-Tharp's Algorithm
%J Yugoslav journal of operations research
%D 1999
%P 235 
%V 9
%N 2
%U http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a6/
%G en
%F YJOR_1999_9_2_a6
Dejan Simić; Dušan Starčević. Efficient Improvement of Brain-Tharp's Algorithm. Yugoslav journal of operations research, Tome 9 (1999) no. 2, p. 235 . http://geodesic.mathdoc.fr/item/YJOR_1999_9_2_a6/