Prev: Nimbus JTabbedPane shuffles tabs
Next: Loopholes in java Encapsulation ?
From: Tom Anderson on 1 Jul 2010 23:42
Hi all,

I want to store some things, each filed under a string key. I then want to
look those things up with other strings, finding the thing whose key is
the longest available prefix of the lookup string.

So, if i store:

/products -> foo
/products/fruit -> bar

Then lookups go like:

/products/furniture/chairs -> foo
/products/fruit/bananas -> bar

Am i right in thinking that there's nothing in the standard library that
does this? I'm writing something that uses the NavigableMap methods on
TreeMap to do it, but it's a bit grim, and not guaranteed to be as
efficient as it could be.

Am i further right in thinking that there's nothing in Apache's Commons
Collections or Google's Guava Collections that does this?

Is there any reasonable open-source library that does?

If i write this myself, is there a data structure better than a Patricia
tree for it?

Cheers,
tom

--
Rapid oxidation is the new black. -- some Mike
From: John B. Matthews on 2 Jul 2010 00:25
In article <alpine.DEB.1.10.1007020423470.29330(a)urchin.earth.li>,
Tom Anderson <twic(a)urchin.earth.li> wrote:

> I want to store some things, each filed under a string key. I then want to
> look those things up with other strings, finding the thing whose key is
> the longest available prefix of the lookup string.
>
> So, if i store:
>
> /products -> foo
> /products/fruit -> bar
>
> Then lookups go like:
>
> /products/furniture/chairs -> foo
> /products/fruit/bananas -> bar
>
> Am i right in thinking that there's nothing in the standard library that
> does this? I'm writing something that uses the NavigableMap methods on
> TreeMap to do it, but it's a bit grim, and not guaranteed to be as
> efficient as it could be.
>
> Am i further right in thinking that there's nothing in Apache's Commons
> Collections or Google's Guava Collections that does this?
>
> Is there any reasonable open-source library that does?

Have you seen this?

<http://code.google.com/p/patricia-trie/>

> If i write this myself, is there a data structure better than a
> Patricia tree for it?

--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
From: markspace on 2 Jul 2010 00:27
Tom Anderson wrote:

> Is there any reasonable open-source library that does?


I think this Radix Tree does what you want (it's the same thing as a
Patricia tree):

http://code.google.com/p/radixtree/
From: Eric Sosman on 2 Jul 2010 08:49
On 7/1/2010 11:42 PM, Tom Anderson wrote:
> Hi all,
>
> I want to store some things, each filed under a string key. I then want
> to look those things up with other strings, finding the thing whose key
> is the longest available prefix of the lookup string.
>
> So, if i store:
>
> /products -> foo
> /products/fruit -> bar
>
> Then lookups go like:
>
> /products/furniture/chairs -> foo
> /products/fruit/bananas -> bar

If you add "/products/fuzz -> baz" to the collection, what
should a lookup on "/products/f" return?

> If i write this myself, is there a data structure better than a Patricia
> tree for it?

The scale of the problem depends on whether a key's "words" must
match in their entirety or only partially. If it's a "word-by-word"
discipline (so /products/f yields foo), I think an ordinary multi-way
tree would be fine; no need for anything as fancy as Patricia. If
/products/f matches both /products/fruit and /products/fuzz, something
trickier may be needed (at the least, you've got to decide what to do
about the ambiguity).

--
Eric Sosman
esosman(a)ieee-dot-org.invalid
From: Roedy Green on 4 Jul 2010 06:16
On Fri, 2 Jul 2010 04:42:31 +0100, Tom Anderson <twic(a)urchin.earth.li>
wrote, quoted or indirectly quoted someone who said :

>I want to store some things, each filed under a string key. I then want to
>look those things up with other strings, finding the thing whose key is
>the longest available prefix of the lookup string.

here are three approaches:

1. use SQL

2. use a TreeMap. Find entry before and after the lookup and analyse.

3. use a HashMap. Keep chopping the key till you get a match on
lookup.
--
Roedy Green Canadian Mind Products
http://mindprod.com

There is no harm in being sometimes wrong especially if one is promptly found out.
~ John Maynard Keynes (born: 1883-06-05 died: 1946-04-21 at age: 62)
 |  Next  |  Last
Pages: 1 2
Prev: Nimbus JTabbedPane shuffles tabs
Next: Loopholes in java Encapsulation ?