commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Rob Oxspring" <roxspr...@apache.org>
Subject Re: [Collections] [SUBMIT] Trie
Date Thu, 05 Dec 2002 10:15:45 GMT
----- Original Message -----
From: "Stephen Colebourne" <scolebourne@btopenworld.com>
To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Sent: Thursday, December 05, 2002 12:13 AM
Subject: Re: [Collections] [SUBMIT] Trie


> Hi,
> I've taken a quick look at the code here, and that all looks fine.
>
> Unfortunately, I don't really know what I'm looking at! What I mean is that
> I've never heard of a 'Trie' before, and am thus wondering as to why I would
> use it, and is it general enough to be in [collections].

I only learned about them a few months back - this seems to be a good place to start:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie.html

>
> In the past we have had discussions about Tree implementations (and I have
> coded some before). This may be related, as the Trie appears to be a
> recursive structure.
>
> Perhaps, some use cases as to why a Trie is useful, especially in a
> general/server environment would be useful. Thanks.

The link above mentions spell checking, and I have plans to use something along these lines
for looking up appropriate automatic
completions for a given string (ie, getting all terms beginning with the given string).  If
you're after more server oriented use
the following suggests using a variation for fast IP lookups

http://search.cpan.org/author/PLONKA/Net-Patricia-1.010/Patricia.pm

Basically anywhere where access performance is important and the data doesn't change much
is a candidate for a Trie based lookup.

My gut feeling is that the class would be useful but I can't say how generally, or how widely
applicable this implementation is...
and I'm not expecting to get round to making use of the structure for a while yet.

On a side note, a couple of the Exception constructors used in the submission need to be dropped
to remain Java 1.3 compatible.

Just my 2p.

Rob

>
> Stephen
>
> ----- Original Message -----
> From: "Rich Dougherty" <rich@rd.gen.nz>
> To: <commons-dev@jakarta.apache.org>
> Sent: Monday, December 02, 2002 7:36 AM
> Subject: [Collections] [SUBMIT] Trie
>
>
> > Hi
> >
> > I've written an implementation for a trie which I'd like to
> > contribute. I've attached a simple implementation and a test
> > case. Here's the interface:
> >
> > /**
> >  *
> >  * A trie is a tree data structure for storing objects. It extends the
> >  * {@link Map} interface and provides two methods to efficiently
> >  * retrieve entries that partially match a key.
> >  *
> >  * A trie usually has a restricted set of objects which can be used
> >  * as keys. Traditionally, it is indexed by {@link String}s, however
> >  * this interface tries to be more general.
> >  *
> >  * @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
> >  * @see http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie.html
> >  * @see http://www.nist.gov/dads/HTML/trie.html
> >  */
> > public interface Trie extends Map {
> >
> >     /**
> >      * Gets all the entries that have keys which start with a given
> >      * prefix.
> >      *
> >      * For example, in a trie that uses {@link String}s for keys, this
> >      * might return all the entries whose keys start with a certain
> >      * string. If the trie contained entries with the keys {"an",
> >      * "ant", "all", "allot", "alloy", "aloe", "are", "ate", "be"}
> >      * then <code>prefixEntrySet("al") </code> would return {"all",
> >      * "allot", "alloy", "aloe"}.
> >      *
> >      * @param keyPrefix The prefix of the keys.
> >      * @return The set of matching {@link Map.Entry}s.
> >      */
> >     public Set prefixEntrySet(Object keyPrefix);
> >
> >     /**
> >      * Get the entry with the longest key that is a prefix of the
> >      * given value.
> >      *
> >      * For example, in a trie that uses {@link String}s for keys, this
> >      * might return the entry with the key that is the longest prefix
> >      * of the given value. If the trie contained entries with the keys
> >      * {"an", "ant", "all", "allot", "alloy", "aloe", "are", "ate",
> >      * "be"} then <code>getLongest("allotment")</code> would return
> >      * "allot".
> >      *
> >      * @param key The key to look for.
> >      * @return The best match, or <code>null</code> if there wasn't
> >      *  one.
> >      */
> >     public Map.Entry getLongest(Object key);
> >
> > }
> >
> > It isn't 100% polished, but I'm happy that it passes the tests! (The
> > Collections test suite is excellent.) Any feedback is appreciated.
> >
> > Regards
> > Rich Dougherty
> >
> >
>
>
> ----------------------------------------------------------------------------
> ----
>
>
> > --
> > To unsubscribe, e-mail:
> <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> > For additional commands, e-mail:
> <mailto:commons-dev-help@jakarta.apache.org>
>
>
> --
> To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>
>
>
>


--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message