Re: Looking things up by string prefix
On 7/4/2010 12:59 PM, Tom Anderson wrote:
On Fri, 2 Jul 2010, Eric Sosman wrote:
On 7/1/2010 11:42 PM, Tom Anderson 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
If you add "/products/fuzz -> baz" to the collection, what
should a lookup on "/products/f" return?
foo. Neither of the other keys is a prefix of the search term.
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).
I evidently haven't explained this clearly. A lookup with /products/f
would never match either /products/fruit or /products/fuzz as entries,
because neither is a prefix of the lookup term.
What i'm trying to do is a bit (okay, a lot) like servlet mapping. If i
set up a mapping for /user/editProfile/*, then i want to catch requests
for /user/editProfile/jim, /user/editProfile/bob, etc.
Okay. I don't know what's already out there and ready-written,
but if I were going to write such a thing from scratch I'd probably
come up with something like (just typed in; not compiled or tested)
class Node {
/** Mapping if we match this far and no further */
private final Target target;
/** Links to deeper Nodes. */
private final Map<String,Node> links;
Node(Target target) {
this.target = target;
this.links = new HashMap<String,Node>();
}
void setLink(String key, Node dest) {
links.put(key, dest);
}
Node getLink(String key) {
return links.get(key);
}
Target match(Iterator<String> keys) {
if (! keys.hasNext())
return null;
Node next = getLink(keys.next());
Target t = (next == null) ? target : next.match(keys);
return (t == null) ? target : t;
}
}
The internal Map might be something lighter-weight if the "degrees"
of the Nodes are expected to be small, but that's the idea. It's a
lot like traversing a directory tree, with the added fillip of a
default value for incomplete matches.
--
Eric Sosman
esosman@ieee-dot-org.invalid