commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jeff Varszegi <>
Subject Re: [Collections] [SUBMIT] Trie
Date Fri, 06 Dec 2002 04:06:23 GMT
Yes, I definitely think a trie implementation is a good thing to have.  I can see myself maybe
using it on a project coming up.  I am interested in gauging the relative performance of the
cut that was submitted vs. a purely String-oriented trie.  It seems to me from poking around
Web that the main uses for tries tend to be string-related-- can we maybe make a quick, somewhat
comprehensive list of uses for tries?

Would it be useful to have a trie that would index on the tail ends of strings in reverse,
supporting quick searches for stuff 'ending in'?

Are there any situations where it would be valuable to index on all n-to-last-character
subsequences of entries, or would the overhead just be too tremendous for that to be useful?
mean, can a trie be used to implement fast lookups of any occurrence of a subsequence?)

Just getting fast type-ahead for GUI applications makes it a definite target for inclusion
in my
book.  If it doesn't make it into Collections it will make it into my private util lib.

Nice work, Rich.


--- "Craig R. McClanahan" <> wrote:
> FWIW, there are at least two Jakarta products that I'm involved in (Tomcat
> and Struts) that have exactly the path-mapping use case that was described
> for the Trie class.  And, conveniently, they both already dependd on
> [collections] so it would be very convenient to have Trie added here.
> It will be very interesting to experiment with the relative speed of using
> a Trie in these cases versus the current algorithms (which clearly need
> some optimizations).
> So, an inactive-committer (to collections) +1 from me for including this.
> Craig McClanahan
> --
> To unsubscribe, e-mail:   <>
> For additional commands, e-mail: <>

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message