Re: [boost] Boost Trie

From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-22 22:31:08

Hi,

On Sun, Mar 23, 2008 at 5:37 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

> chintan rao wrote:
> > I was thinking of implementing trie and various variation of tries,
> namely
> > Ternary trees, Suffix trees and DAWG(Directed Acyclic Word Graphs) , for
> > Google Soc.
>
> That's interesting.  Do you have a motivating application?

Till now i was gathering ideas here at the mailing list and other places.
Will have to prepare a final application.

> I last thought about tries when Boost.Flyweight was being discussed.
> Could your tries be used there?

 I have not looked into Boost.Flyweight but I suppose they can be used :).

At one time I was considering writing an Apache log file analysis
> program.  This would have used some sort of trie or similar structure
> to store the URLs (the aim is to be able to analyse very large logs in
> RAM).  At the time I was considering PATRICIA tries.

Some people had suggested PATRACIA tries. I looked into the algorithm and
added it to my todo list.
Actually even the DAWG idea was suggested by someone else too :). I also
looked in Digital Search Trees :).

> I also have some code that stores large numbers of very similar filenames:
>
> /photos/christmas_2007/img_3277.jpg
> /photos/christmas_2007/img_3278.jpg
> ....
>
> These are currently stored in a binary file which is mmap()ed.  The
> time to read the file is non-trivial and is bad for program start-up
> time.  So perhaps I need a trie that can be stored in the mmap()ed
> file, i.e. not using pointers, like the Boost.Interprocess containers do.
>
> > I was thinking something like this
> >
> > This is the abstract of the interface for trie
> > Interface:
> >     trie<type_2> something;
> >     trie[string key]=type2 value;  // O(key.size());
> >     value trie::delete(string key);       // O(key.size());
> >     trie::iterator trie::find(string key);         // O(key.size())'
> >     int trie::size()         // O(1) time. Gives the total no of
> elements in
> > the trie
> >     trie::iterator trie::begin()     //gives the beginning ie the
> > lexicographically least key :)
> >     trie::iterator trie::end()     //gives a iterator which is same as
> > x=x+trie.size();
> >     string trie::get_key(iterator x) gets the key pointed to by iterator
> x;
> >
> >     trie::iterator x;            //worst case O(height of tree)
> >     x++; // traverses the tree left to right and goes to the "next" node
> >     x--; // traverses the tree right to left and goes to "prev" node
> >
> >     *x // referrences the value of the key x is pointing to.
> >     trie.delete(x) // deletes the key pointed to by x;
> >
> >     trie.count_prefix(string key) // counts the no of keys with prefix
> key
> >
> > Examples:
> >     trie::interator x;
> >     trie<vector<int> > t;
> >     t["hello"].push_back(9);
> >     t["eat"].push_back(10);
> >
> >     x=t.find("hello");
> >     x--; //or --x; x now points to "eat" since eat comes before "hello"
> > lexicographically;
> >     cout<<(*x)[0]<<endl;
> >
> >     x++;//or ++x, x now points to "hello";
> >
> >     x=t.end(); // or x++ will point to t.end().
> >
> >     do
> >     {
> >         x--;
> >         int size=(*x).size();
> >         cout<<t.get_key(x)<<endl;
> >         for(int j=0;j<size;j++)
> >             cout<<(*x)[j]<<" ";
> >         cout<<endl;
> >     }
> >     while(x!=t.begin());
> >
> > Please suggest changes to the interface and other things.
>

>
> I think you should be able to make it (almost) identical to std::map's
> interface.  You should certainly use std::map as your starting point,
> and only deviate from it when you have a good reason to do so.
>
Should be easily possible :).

>
>
> Regards,  Phil.
>
Regards,
Chintan

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