Re: Looking for symbol table hashing algorithm

Peter Wilson <peter.r.wilson@boeing.com>
20 Jul 1998 17:02:52 -0400

          From comp.compilers

Related articles
[12 earlier articles]
Re: Looking for symbol table hashing algorithm scott@basis.com (1998-07-10)
Re: Looking for symbol table hashing algorithm henry@spsystems.net (1998-07-10)
Re: Looking for symbol table hashing algorithm chase@naturalbridge.com (David Chase) (1998-07-10)
Re: Looking for symbol table hashing algorithm dietz@interaccess.com (Paul Dietz) (1998-07-11)
Re: Looking for symbol table hashing algorithm scottdaniels@earthlink.net (Scott David Daniels) (1998-07-13)
Re: Looking for symbol table hashing algorithm buzzard@world.std.com (1998-07-13)
Re: Looking for symbol table hashing algorithm peter.r.wilson@boeing.com (Peter Wilson) (1998-07-20)
| List of all articles for this month |

From: Peter Wilson <peter.r.wilson@boeing.com>
Newsgroups: comp.compilers
Date: 20 Jul 1998 17:02:52 -0400
Organization: Compilers Central
References: 98-07-030 98-07-045 98-07-084 98-07-117
Keywords: symbols, practice

Sean T Barrett wrote:
> The latest version of "Algorithms in C" offers a data structure called
> the "Ternary Search Tree", which searches down the letters of a symbol
> progressively, and looks relatively straightforward to implement, but
> I've never tried it, and it's new enough that I've never heard anyone
> else mention trying it. It cites this paper:
>
> J. Bentley and R. Sedgewick, "Sorting and Searching Strings", Eighth
> Symposium on Discrete Algorithms, New Orleans, January, 1997.


        Bentley and Sedgewick have an article on the same data structure as
"Ternary Search Trees" in Dr. Dobb's Journal, April 1998, pages 20-25.
Several algorithms are described and illustrated in terms of C code.


        I have used the ternary tree structure in an interpreter I am
writing, but coded in Java rather than C. I have not tried any time or
space comparisons with other methods/structures, except to note that the
ternary tree appears to be faster than my original choice of a binary
tree. The authors note that in some places their code is "subtle". It
did take me more than one try to get the algorithms working properly in
Java.


Peter W.
peter.r.wilson@boeing.com
--


Post a followup to this message

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