Re: [boost] [spirit] Ternary Search Tree (TST) revisited

From: rasmus ekman (m11048_at_[hidden])
Date: 2006-05-23 10:05:06

Joel de Guzman wrote:
 >
 > As many of you might not know, there's a nice TST(*)
 > implementation in the Spirit CVS written by Steve Rowe

 > I would want to use it as the basis for Spirit-2's symbol
 > table. The objective is to optimize the code and do some
 > benchmarks with it.

You may want to look at http://www.abc.se/~re/code/tst
It's not finished, but may be usable in present state.

The unfinished interface bit is: defining subkey iterators, and rewrite the
imprecise matching algorithms as nonmember functions.

I define the TST containers as Associative Sorted with internal structure
in the keys - the keys are Forward Containers.
(hence the name Structured Containers, but this may be an overstatement,
suggestions welcome)

So iterators should perhaps use a variant of segmented iterators
- though not for performance purposes.

I haven't found time to finish it (I just use it as is),
but with some suggestions for interface and implementation I could perhaps
get going again. The implementation is needlessly messy in spots,
as I tried to do without Boost.Iterator and MPL.

> (*)
> Ternary Search Tree implementation. The data structure is faster than
> hashing for many typical search problems especially when the search
> interface is iterator based. Searching for a string of length k in a
> ternary search tree with n strings will require at most O(log n+k)
> character comparisons. TSTs are many times faster than hash tables
> for unsuccessful searches 

I have not found this to be generally true, at least not the "many times faster" claim,
at least not for the implementations I've seen.
"About as fast as hashed containers" is a more reasonable statement.
Please see http://www.abc.se/~re/code/tst/tst_docs/tst_perf.html

        re