On Mon, Mar 24, 2008 at 4:44 PM, Jeff Flinn <TriumphSprint2000@hotmail.com> 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