From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-24 21:30:10
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 <
> > 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
> > 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
> > 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
> > array look for the child node's address become too large. Trie for
> > 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
> > 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" )
Chintan Rao H
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk