adrianho@cory.Berkeley.EDU (Adrian J Ho) (02/28/90)
For those of you who've just tuned in 8-), I posted a request recently asking for sources and/or algorithms for adaptive perfect hashing (ie. re-perfect-hashing on the fly). Thus far, I've only had one reply; for those of you who've missed it, here's Doug Schmidt's posting: 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.'' Of course, the problem is that gperf only does static perfect hashing, so I'll probably have to tear gperf apart, figure out exactly which code does what, and then work from there. Alas, academic pressure precludes doing that right now, but I'd love to hear from anyone out there who's doing it right now. Thanks for the info, Doug! ----------------------------------------------------------------------------- Adrian J Ho adrianho@cory.berkeley.edu University of California, Berkeley adrianho@soda.berkeley.edu ajho@ocf.berkeley.edu
oz@yunexus.UUCP (Ozan Yigit) (03/01/90)
In article <1990Feb27.234244.24879@agate.berkeley.edu> adrianho@cory.Berkeley.EDU (Adrian J Ho) writes: >Of course, the problem is that gperf only does static perfect hashing, so >I'll probably have to tear gperf apart, figure out exactly which code does >what, and then work from there. Alas, academic pressure precludes doing >that right now, but I'd love to hear from anyone out there who's doing it >right now. The algorithm was described by R.J. Cichelli in The January 1980 issue of Communications of the ACM under the title "Minimal Perfect Hash Functions made Simple." Also see "More On Minimal Perfect Hash tables" by Curtis Cook and R. Oldehoeft, a Colorado State University Technical Report. A very early implementation of this algorithm, (before gperf was ever written) was done by Charlie Hanever of GenRad, I think around 1984 or 1985. [I still have it someplace]. If I recall correctly, there was also some discussion about "external perfect hashing" in one of the ACM Trans. on Database Systems. There is also a UofCalgary (I think) tech report with bit more implementation detail. I can dig it out if you really want it. oz -- There are two kinds of fool. Internet: oz@nexus.yorku.ca One says, "This is old, and therefore good" Uucp: uunet!utai!yunexus!oz And one says "This is new, and therefore Better" Bitnet: oz@[yulibra|yuyetti] John Brunner (The Shockwave Rider) Phonet: +1 416 736-5257x3976