A LETTER-ORIENTED PERFECT HASHING SCHEME BASED UPON SPARSE TABLE COMPRESSION

Abstract

In this paper, a new letter-oriented perfect hashing scheme based on Ziegler's row displacement method is presented. A unique n-tuple from a given set of static letter-oriented key words can be extracted by a heuristic algorithm. Then the extracted distinct n-tuples are associated with a 0/1 sparse matrix. Using a sparse matrix compression technique, a perfect hashing function on the key words is then constructed.