Re: [boost] Boost Trie

From: Martin Wille (mw8329_at_[hidden])
Date: 2008-03-24 13:25:30

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?

Regards,
m