laba-3ec@web-3g.berkeley.edu (Adrian J Ho) (02/19/90)
Does anyone have any references to adaptive perfect hashing algorithms? I'm writing a PostScript-like interpreter and I'd like to speed up dictionary lookups radically (especially since I'm expecting HUGE dictionaries). What I'm basically looking for is the ability to generate a perfect hash function (a la gperf) on the fly. Obviously, I'm not going to call it every time the user adds a new definition, so the speed of the algorithm is not too important (wouldn't mind having my cake and eating it too, though). Also, does anyone have any C code that implements the algorithms? I'd rather not re-invent the wheel if at all possible, and wading through the gperf code isn't very smart right when homework's starting to pile up. PS. I heard rumors that the paper alluded to in the gperf docs ("Implementation Details of GNU gperf", v2.0) that describes "the high-level description of the data structures and algorithms used to implement gperf" has been released. Can anyone confirm this, and if so, how can I go about getting a copy? Please email all replies to me, as I don't read these newsgroups regularly. I'll post a summary after an appropriate length of time. Thanks in advance. ----------------------------------------------------------------------------- Adrian J Ho adrianho@cory.berkeley.edu University of California, Berkeley adrianho@soda.berkeley.edu
schmidt@crimee.ics.uci.edu (Doug Schmidt) (02/19/90)
In article <1990Feb18.233444.7345@agate.berkeley.edu>, laba-3ec@web-3g (Adrian J Ho) writes: >PS. I heard rumors that the paper alluded to in the gperf docs >("Implementation Details of GNU gperf", v2.0) that describes "the high-level >description of the data structures and algorithms used to implement gperf" >has been released. Can anyone confirm this, and if so, how can I go about >getting a copy? Sure, you can get a quasi-legible copy via anonymous ftp from ics.uci.edu (128.195.1.1), in a file called gperf.tex. It is quasi-legible since you'll need to run it through LaTeX and a I didn't include the bibtex file nor one of the special figures (it seems to break everyone's dvi driver anyway). However, the main algorithm is described in detail. The final copy of this paper will be published in the upcoming USENIX C++ Conference Workshop proceedings, available after the middle of April, I'd guess. If anyone has any comments or suggests about the paper please let me know, there's still time to make revisions! Doug -- A monk asked Kegon, ``How does an enlightened | schmidt@ics.uci.edu (ARPA) one return to the ordinary world?'' Kegon replied, | office: (714) 856-4043 ``A broken mirror never reflects again; fallen flowers never go back to the old branches.''