----- Original Message ----- From: "Stephen Colebourne" <[EMAIL PROTECTED]> To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]> 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" <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > 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:[EMAIL PROTECTED]";>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:[EMAIL PROTECTED]> > > For additional commands, e-mail: > <mailto:[EMAIL PROTECTED]> > > > -- > To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> > For additional commands, e-mail: <mailto:[EMAIL PROTECTED]> > > > -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
