Efficient improvement of Brain-Tharp's algorithm

Abstract

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 analysed 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.