Re: [boost] Boost Trie

From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-24 11:53:42

On Mon, Mar 24, 2008 at 4:44 PM, Jeff Flinn <TriumphSprint2000_at_[hidden]>
wrote:

> John Maddock wrote:
> > chintan rao wrote:
> >> Hi,
> >> I would like to know if there is Trie implementation in Boost.
> >> If not is it going to implemented soon?
> >
> > No it's one of those things we're currently missing.
>
> I think the boost spirit symbol class is implemented as a trie, albeit

> incomplete... you can add items, and search for them, but not remove
> them. IIRC, there was discussion on the spirit mailing list regarding a
> more generalized version.

I had looked into. Seems like and old discussion. It dated back to 2005....
I had no idea how to follow it up. Do they use a generalized version,for
which
they used a TST according to the thread link given by Martin Wille in reply
to my post )
or do they do they version of tries specific to strings. Did they implement
a Patricia Trie?

Anyway, generally speaking ........
A generalized version will have to use Ternary Search Tree otherwise direct
array look for the child node's address become too large. Trie for strings
itself is space in efficient. One has to use PATRICIA tries to really
optimize it . There are other techniques like DAWG which do make the tries
somewhat space efficient...

Jeff Flinn
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>