R
rasmus ekman
Hi,
I've refreshed my Ternary search tree implementation at
http://abc.se/~re/code/tst/
It should now be usable. It compiles cleanly with Comeau's online compiler,
g++ 3.4.3, and MSVC 7.1. Some tests are included (some tests not portable).
There are wrapper classes that will work as (nearly) drop-in replacements
for set, map, multiset, multimap, or the unordered_* counterparts.
----
Ternary search trees were described by Bentley and Sedgewick
in DDJ 1994/04, see also http://www.cs.princeton.edu/~rs/strings/
for a more theoretical article and C code sketch.
If you don't know about TST's, it's worth checking out,
as it is useful as a dictionary container.
A TST allows advanced key searches, currently:
- prefix match,
- longest match (tokenizing input over the dictionary),
- neighbour search (eg for mispelt words), and
- wildcard search: "b?nd" finds "band", "bend", "bind", "bond", etc.
and it offers lookup speed similar to hash maps.
Some additions will be made in the future (interface for advanced key searches),
but the present state is (I think) not worse than other public versions.
I'd be grateful for comments on interface, docs and implementation.
It's not quite finished, so any suggestions to make it better is appreciated.
Or just use it and mail me on failure (or follow-up in comp.lang.c++).
If someone is interested (and I survive the shock), I could move it
to eg Sourceforge for easier access.
Cheers,
re
I've refreshed my Ternary search tree implementation at
http://abc.se/~re/code/tst/
It should now be usable. It compiles cleanly with Comeau's online compiler,
g++ 3.4.3, and MSVC 7.1. Some tests are included (some tests not portable).
There are wrapper classes that will work as (nearly) drop-in replacements
for set, map, multiset, multimap, or the unordered_* counterparts.
----
Ternary search trees were described by Bentley and Sedgewick
in DDJ 1994/04, see also http://www.cs.princeton.edu/~rs/strings/
for a more theoretical article and C code sketch.
If you don't know about TST's, it's worth checking out,
as it is useful as a dictionary container.
A TST allows advanced key searches, currently:
- prefix match,
- longest match (tokenizing input over the dictionary),
- neighbour search (eg for mispelt words), and
- wildcard search: "b?nd" finds "band", "bend", "bind", "bond", etc.
and it offers lookup speed similar to hash maps.
Some additions will be made in the future (interface for advanced key searches),
but the present state is (I think) not worse than other public versions.
I'd be grateful for comments on interface, docs and implementation.
It's not quite finished, so any suggestions to make it better is appreciated.
Or just use it and mail me on failure (or follow-up in comp.lang.c++).
If someone is interested (and I survive the shock), I could move it
to eg Sourceforge for easier access.
Cheers,
re