Re: [boost] Boost Trie

From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-24 21:30:10

Hi,

On Mon, Mar 24, 2008 at 10:55 PM, Martin Wille <mw8329_at_[hidden]> wrote:

> chintan rao wrote:
> > 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.
>
> Spirit isn't limited to strings and the TST implementation is templated
> on the "character" type. It should work with any sequential key.
>
>
>                                                         Did they implement
> > a Patricia Trie?
>
> No. Spirit's TST node class contains only an instance of a single CharT.
>
>
> > 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...
>
> "optimize" implies an optimization goal. As with other data structures,
> you can't optimize them all in a single implementation. What
> optimization goal(s) do you have in mind?

PATRICIA Tries optimize space. I don't know about how much it improves  the
time efficiency over normal tries as one could be using TST in it to
conserve space. But as far i remember a person #boost channel reported some
thing like 2x speed over std::map.

DAWG does retain the time efficiency of a normal trie and also optimizes
space by merging common subtrees. But it again depends on how one decides to
implement it.. Ie using a TST or no TST. But there is an added time required
to build a DAWG from a trie. ( one internet source reported it as "160,000
words in about 2 minutes" )

Regards,
Chintan Rao H