Re: Minimal Perfect Hashing and Cichelli's algorithm

taj@vanbc.wimsey.com (Taj Khattra)
11 Apr 1996 23:36:57 -0400

          From comp.compilers
Related articles
Minimal Perfect Hashing and Cichelli's algorithm CSPT@giraffe.ru.ac.za (Pat Terry) (1996-04-10)
Re: Minimal Perfect Hashing and Cichelli's algorithm taj@vanbc.wimsey.com (1996-04-11)
Hashing for Keywords? (was: Minimal Perfect Hashing and Cichelli's alg p.froehlich@amc.cube.net (1996-04-29)
| List of all articles for this month |
From: taj@vanbc.wimsey.com (Taj Khattra)
Newsgroups: comp.compilers
Date: 11 Apr 1996 23:36:57 -0400
Organization: Wimsey Information Services
References: 96-04-055
Keywords: symbols

Pat Terry (CSPT@giraffe.ru.ac.za) wrote:
: Since this subject has come up again, it may be worth noting that a
: nice little algorithm was developed for constructing such functions by
: Richard Cichelli way back in about 1979, one which has been extended
: and played with by several others.


For "large" keyword sets (certainly larger than the keyword sets of most
programming languages) it may be worthwhile to explore the algorithm
described in [CHM92] which is a probabilistic method using random graphs
that works very fast in practice. It also has the benefit of being order
preserving.


[CHM92] Z.J. Czech, G. Havas, and B.S. Majewski. An optimal algorithm
                for generating minimal perfect hash functions. Information
                Processing Letters, 43(5):257-264, October 1992.


-taj


--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.