|[12 earlier articles]|
|Re: Looking for symbol table hashing algorithm firstname.lastname@example.org (1998-07-10)|
|Re: Looking for symbol table hashing algorithm email@example.com (1998-07-10)|
|Re: Looking for symbol table hashing algorithm firstname.lastname@example.org (David Chase) (1998-07-10)|
|Re: Looking for symbol table hashing algorithm email@example.com (Paul Dietz) (1998-07-11)|
|Re: Looking for symbol table hashing algorithm firstname.lastname@example.org (Scott David Daniels) (1998-07-13)|
|Re: Looking for symbol table hashing algorithm email@example.com (1998-07-13)|
|Re: Looking for symbol table hashing algorithm firstname.lastname@example.org (Peter Wilson) (1998-07-20)|
|From:||Peter Wilson <email@example.com>|
|Date:||20 Jul 1998 17:02:52 -0400|
|References:||98-07-030 98-07-045 98-07-084 98-07-117|
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
Return to the
Search the comp.compilers archives again.