Re: Looking for symbol table hashing algorithm

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
--

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